ED Mathématiques et Informatique
Impossibility results for universal graphs
by Amaury JACQUES (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
The defense will take place at 14h30 - Amphithéâtre 351 Cours de la libération, LaBRI, Université de Bordeaux, 33405 Talence
in front of the jury composed of
- Cyril GAVOILLE - Professeur des universités - Université de Bordeaux - Directeur de these
- Nicolas NISSE - Directeur de recherche - Centre Inria d'Université Côte d'Azur - Rapporteur
- Édouard BONNET - Chargé de recherche - LIP, ENS de Lyon, CNRS - Rapporteur
- Arnaud LABOUREL - Maître de conférences - LIS, Aix-Marseille Université - Examinateur
- Caroline BROSSE - Maîtresse de conférences - LIFO, Université d'Orléans - Examinateur
- François PELLEGRINI - Professeur des universités - Université de Bordeaux - Examinateur
In this thesis we focused on graph representations through the problem of universal graphs. A graph is an abstraction used to represent interconnections between objects, these objects are called vertices, and the connections between them are called edges. A classical way to represent graphs is by using an adjacency matrix or by using adjacency lists of the vertices. These classical representations are the basis of graph algorithms, fundamental to many domains such as telecommunications, electronics or computer science. However in some particular contexts such as distributed algorithms, constraints on space and communication lead to the use of more compact representations and that are said to be implicit. Labeling schemes address this particular problem. An adjacency labeling scheme is, for a graph family, an assignment of labels for every vertex of the graphs of the family such that, for a pair of labels, it is possible to determine if the corresponding vertices are adjacent or not. The objective is to minimize the size of these labels. We focused on this problem in more details through a corresponding problem, the induced-universal graph with the minimal number of vertices. An induced-universal graph for a graph family is a graph that contains every graph of the family as an induced subgraph, in other words it is possible to find every graph of the family by selecting a subset of the universal graph's vertices and the edges between them. The main results of this thesis relate to the impossibility of constructing induced-universal graphs for some families of graphs using fewer than a certain number of vertices. These fairly general results enable us to provide lower bounds for families based on their characteristics, such as the number of graphs in the family or the presence of unions of complete graphs of a given size in the family. We also studied the number of graphs required to improve these lower bounds, this was achieved using a construction of induced-universal graphs for small families of graphs, in particular minor-closed subfamilies such as subfamilies of planar graphs. We also present construction of induced-universal graphs for various families, such as stars forests and unions of complete graphs. For the latter, our construction is optimal in terms of the number of vertices. Finally, we present complexity results for minimal-size induced-universal graphs and generalize these results to other types of universal graphs.
ED Sciences Physiques et de l'Ingénieur
Numerical simulations of Brownian motion in complex environments
by Juliette LACHEREZ (Laboratoire Ondes et Matière d'Aquitaine)
The defense will take place at 14h15 - Salle A Université de Bordeaux, Bâtiment A29, 351 cours de la Libération, 33400 Talence
in front of the jury composed of
- Thomas SALEZ - Directeur de recherche - Université de Bordeaux - Directeur de these
- Chantal VALERIANI - Professeure associée - Universidad Complutense de Madrid - Rapporteur
- Demian LEVIS - Professeur associé - Universitat de Barcelona - Rapporteur
- Christine GRAUBY-HEYWANG - Professeure des universités - Université de Bordeaux - Examinateur
- Marco ELLERO - Professeur - Basque center for Applied Mathematics - Examinateur
There are phenomena in physics that recur across many systems, yet whose exact, formal description is never truly achieved. Brownian motion, the process by which small particles explore the space available to them under the thermal agitation of the surrounding fluid's molecules, is one such notion. Since its observation in 1827, followed by its theoretical formalisation and experimental confirmation in a very simple idealised case in the early 1900s, the scientific community has continually deepened its understanding of the interactions between Brownian processes and confinement, whether rigid or deformable. To this are added viscous flows, the particle's own activity in the case of a living organism, and hydrodynamic interactions between particles. Each of these areas of study, however, presents limitations: the coupling between confined mobility and interface deformability remains poorly quantified, the combined effect of crowding and wall proximity on diffusion is rarely treated as a whole, and the extension of classical dispersion theories to active solutes had, until now, remained largely open. My doctoral work draws on numerical tools to advance on these three fronts. I present a theoretical and numerical study of Brownian motion near a soft, fluctuating interface, an analysis of how diffusion is modified by the presence of other colloids and a nearby wall, and the extension of Taylor-Aris dispersion theory for a solute in flow to active solutes. These developments allow for a finer understanding of microbiological systems where confinement, sometimes itself fluctuating, drastically alters mobility, where activity is inherent, and where crowding is the rule rather than the exception. Having isolated the effects specific to each of these elements, their coupling becomes feasible to study, by comparison, real experimental systems.