Random combinatorial structures with low dependencies: existence and enumeration.

Tesis doctoral de Guillem Perarnau Llobet

In this thesis we study different problems in combinatorics and in graph theory by means of the probabilistic method. This method, introduced by erdí¶s, has become an extremely powerful tool to provide existential proofs for certain problems in different mathematical branches where other methods had failed utterly. one of its main concerns is to study the behavior of random variables. In particular, one common situation arises when these random variables count the number of bad events that occur in a combinatorial structure. The idea of the poisson paradigm is to estimate the probability of these bad events not happening at the same time when the dependencies among them are weak or rare. If this is the case, this probability should behave similarly as in the case where all the events are mutually independent. This idea gets reflected in several well-known tools, such as the lovász local lemma or suen inequality. the goal of this thesis is to study these techniques by setting new versions or refining the existing ones for particular cases, as well as providing new applications of them for different problems in combinatorics and graph theory. Next, we enumerate the main contributions of this thesis. the first part of this thesis extends a result of erdí¶s and spencer on latin transversals [1]. They showed that an integer matrix such that no number appears many times, admits a latin transversal. This is equivalent to study rainbow matchings of edge-colored complete bipartite graphs. Under the same hypothesis of [1], we provide enumerating results on such rainbow matchings. the second part of the thesis deals with identifying codes, a set of vertices such that all vertices in the graph have distinct neighborhood within the code. We provide bounds on the size of a minimal identifying code in terms of the degree parameters and partially answer a question of foucaud et al. [2]. On a different chapter of the thesis, we show that any dense enough graph has a very large spanning subgraph that admits a small identifying code. In some cases, proving the existence of a certain object is trivial. However, the same techniques allow us to obtain enumerative results. the study of permutation patterns is a good example of that. In the third part of the thesis we devise a new approach in order to estimate how many permutations of given length avoid a consecutive copy of a given pattern. In particular, we provide upper and lower bounds for them. One of the consequences derived from our approach is a proof of the cmp conjecture, stated by elizalde and noy [3] as well as some new results on the behavior of most of the patterns. In the last part of this thesis, we focus on the lonely runner conjecture, posed independently by wills and cusick and that has multiple applications in different mathematical fields. this well-known conjecture states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a moment where all of them are far enough from the origin. We improve the result of chen [4] on the gap of loneliness by studying the time when two runners are close to the origin. We also show an invisible runner type result, extending a result of czerwinski and grytczuk [5]. [1] p. Erdos and j. H. Spencer, lopsided lovász local lemma and latin transversals, discrete appl. Math. 30 (1991), no. 2-3, 151¿154. [2] f. Foucaud, r. Klasing, a. Kosowski, and a. Raspaud, on the size of identifying codes in triangle-free graphs, discrete appl. Math. 160 (2012), no. 10-11, 1532¿1546. [3] s. Elizalde and m. Noy, consecutive patterns in permutations, adv. In appl. Math. 30 (2003), 110¿125. [4] y. G. Chen, view-obstruction problems in n-dimensional euclidean space and a generalization of them, acta math. Sinica 37 (1994), no. 4, 551¿562. [5] s. Czerwinski and j. Grytczuk, invisible runners in ¿nite ¿elds, inform. Process. Lett. 108 (2008), no. 2, 64¿67.

Datos académicos de la tesis doctoral «Random combinatorial structures with low dependencies: existence and enumeration.«

• Título de la tesis:  Random combinatorial structures with low dependencies: existence and enumeration.
• Autor:  Guillem Perarnau Llobet
• Universidad:  Politécnica de catalunya
• Fecha de lectura de la tesis:  01/10/2013

Dirección y tribunal

• Director de la tesis
  • Oriol Serra Albó
• Tribunal
  • Presidente del tribunal: josep Díaz cort
  • gábor Tardos (vocal)
  • (vocal)
  • (vocal)