Random combinatorial structures with low dependencies : existence and enumeration

ADVERTIMENT . La consulta d’aquesta tesi queda condicionada a l’acceptació de les següents condicions d'ús: La difusió d’aquesta tesi per mitjà del servei TDX (www.tesisenxarxa.net) ha estat autoritzada pels titulars dels drets de propietat intel·lectual únicament per a usos privats emmarcats en activitats d’investigació i docència. No s’autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d’un lloc aliè al servei TDX. No s’autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. ADVERTENCIA. La consulta de esta tesis queda condicionada a la aceptación de las siguientes condiciones de uso: La difusión de esta tesis por medio del servicio TDR (www.tesisenred.net) ha sido autorizada por los titulares de los derechos de propiedad intelectual únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro ni su difusión y puesta a disposición desde un sitio ajeno al servicio TDR. No se autoriza la presentación de su contenido en una ventana o marco ajeno a TDR (framing). Esta reserva de derechos afecta tanto al resumen de presentación de la tesis como a sus contenidos. En la utilización o cita de partes de la tesis es obligado indicar el nombre de la persona autora. WARNING. On having consulted this thesis you’re accepting the following use conditions: Spreading this thesis by the TDX (www.tesisenxarxa.net) service has been authorized by the titular of the intellectual property rights only for private uses placed in investigation and teaching activities. Reproduction with lucrative aims is not authorized neither its spreading and availability from a site foreign to the TDX service. Introducing its content in a window or frame foreign to the TDX service is not authorized (framing). This rights affect to the presentation summary of the thesis as well as to its contents. In the using or citation of parts of the thesis it’s obliged to indicate the name of the author Programa de Doctorat de Matemàtica Aplicada Random Combinatorial Structures with low dependencies: existence and enumeration by Guillem Perarnau Llobet PhD dissertation Advisor: Oriol Serra Albó Barcelona, July 2013 A l'Elena, Acknowledgements v Acknowledgments: This thesis is the result of a trip that, during these last years, allowed me to discover a new fascinating area. There are many people who have accompanied me and to whom I own an enormous part of this work. Their wise advice, contagious joy and unconditional support made this thesis possible. First of all, I want to thank my advisor Oriol Serra. He has transmitted me his pure enthusiasm for knowledge, music and specially maths. Whenever I needed his advice for a new problem, he has put everything aside to discuss it, just with the help of some coee. I will never forget the excitement on his face each time I claimed I had a new proof for that problem that didn't want to work. This thesis has a huge debt to his broad point of view and lucid ideas. With all his virtues and (not many) defects, I could not imagine anyone better to lead me all these years. I also want to thank all my coauthors; in particular, Florent Foucaud, for all the shared moments playing board games and enjoying vins et fromages , Dieter Mitsche, with whom I learned more than he could imagine and Giorgis Petridis, an excellent person from who I got many useful advises. I would also like to specially thank Josep Díaz for sharing many blackboard discussions and never losing the hope in defeating a problem. My gratitude also to Tibor Szabó and all the people in the Freie Universität, who make me feel that Berlin is a second home for me, and to Gábor Tardos for thoroughly checking this document, for his kind hospitality and for showing me Hungarian history in Budapest. I want to give my gratitude to the nonprot help and many comments provided by colleagues and anonymous referees who enormously contributed in increasing the quality of this thesis. Specially, many thanks to Marc Noy for introducing me to permutation patterns and for our nice discussions about them. I also want to thank all the people I have met all along these years in conferences, schools, workshops . . . . I would never be able to enumerate them all, but specially thanks to Andrzej, Aline, Anita, Asaf, Fiona, Henning, Jan, Kaska, Katherine, Mima, Marko, Nico, Reza, Roman, Ross, Tomas, Xavier, Will . . . . Thanks for the amazing moments we shared either discussing problems or learning how to toast in many languages. Vull agrair al Department MA4 i al grup COMBGRAPH l'oportunitat de realitzar la tesi, així com el nançament per tal poder viatjar i formar-me com a matemàtic i com a persona. Agrair en especial l'energia transmesa per l'Anna Lladó i a en Josep M. Aroca, per fer que la meva experiència com a docent fos immillorable. També vull donar les gràcies a tota la gent que algun dia m'ha preguntat, però . . . i de què va el teu doctorat? , i aquells que han despertat la meva curiositat en la ciència i en les matemàtiques, especialment al Toni Hernàndez i al Sebastià Xambó. Tant en l'àmbit personal com professional, vull agrair a l'Arnau el seu esforç pel que faci falta, ja intentant trobar un problema de comú interés on treballar junts o convencent-me per fer un últim mojito. De gran suport també han estat l'Adrià, la Cris, l'Inma, la Laura, el Víctor, les múltiples vetllades renegant dels nostres doctorats i els bons moments compartits. Gran part d'aquesta tesi li dec a la gent amb qui he compartit el dia a dia durant aquests anys vi Acknowledgements i que han passat a ser molt més que excompanys de fatigues. A l'Àngela per ser una persona excel · lent, a les bromes de l'Aida, a la mejor amiga Cris, als comentaris del Marconi, al Morgan per fer-me riure com ningú, a les converses amb el Vena, al PD, a l'Èric, al Teixi, al Romain, a l'Hèctor i a tants d'altres que han passat pel despatx. Gràcies a la terrasseta del Poblesec del Joan i la Núria, a la vida al piset amb el Gerard i el Sergi, a les tardes de Flohmarkt amb el Iol i la Júlia i a tanta altra gent que m'ha acompanyat durant aquests anys: Georgina, Gina, Guille, Javi, Jordi, Jud, Lara, Maria, Núria, Sergi, Tere . . . Vull agrair a la meva família, avis, oncles i cosins, a aquells que hi són i a aquells que ja no, el suport sempre incondicional. Als meus pares, Tiu i Pere, per tot l'afecte que m'han donat, per haver fet de mi el que sóc, per haver-me ensenyat que la perseverança dóna els seus fruits i per intentar que sigui una mica menys desastre; sincerament, moltes gràcies. Al Martí, per tots els moments compartits d'ençà que érem petits, per ser tant bon amic com germà i pels seus rotllos de físic. Ja per acabar, gràcies a tu, Elena, per fer-me sentir cada dia més afortunat, per les tardes de sofà, pels records passats, pels plans futurs i perquè n'estic convençut que junts podem arribar més lluny . Abstract vii Random Combinatorial Structures with low dependencies: existence and enumeration Abstract: In this thesis we study dierent problems in combinatorics and in graph theory by means of the probabilistic method. This method was introduced by Erd®s and its rst applications are found in Ramsey Theory and graph colorings. It has become an extremely powerful tool to provide existential proofs for certain problems in dierent 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 reected in several wellknown tools, such as the Lovász Local Lemma [52] or Suen inequality [82]. The goal of this thesis is to study these techniques by setting new versions or rening the existing ones for particular cases, as well as providing new applications of them for dierent problems in combinatorics and graph theory. Next, we enumerate the main contributions of this thesis. The rst part of this thesis extends a result of Erd®s and Spencer on latin transversals [53]. There, the authors 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 [53], we provide enumerating results on such rainbow matchings. Our techniques are based on the framework devised by Lu and Szekely [98]. The second part of the thesis deals with identifying codes. An identifying code is a set of vertices such that all vertices in the graph have distinct neighborhood within the set. 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. [61]. By studying graphs with girth at least 5 and large minimum degree, we are able to estimate the size of a minimum code for random regular graphs. On a dierent 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 [50] 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 [127] and Cusick [41] and that has multiple applications in dierent mathematical elds. This wellknown conjecture states that for any set of runners running along the unit circle with constant dierent 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 [35] on the gap of loneliness by studying the time when two runners are close to the origin. We also extend the invisible runner result of Czerwi«ski and Grytczuk [44]. CHAPTER 1 Introduction The probabilistic method was initiated by Paul Erd®s and it has been one of the most powerful and widely used techniques to deal with combinatorial problems. During the last 60 years it has been developed and has provided existential proofs for certain problems in dierent mathematical branches where other methods had failed utterly. For instance, one may nd multiple applications of it in mathematical elds like number theory, linear algebra, geometry or analysis. In particular, it is also one of the most used tools in algorithmics, connecting combinatorics with computer science. Topics like the study of randomized algorithms or property testing are good examples of that. The probabilistic method relies on proving that a statement is true by setting a probability space and showing that the probability of this statement is strictly positive. Whereas many combinatorial proofs provide constructions of such objects in an explicit way, the probabilistic method gives only existential proofs. This is one of the reasons why this method proves to be so powerful to attack some problems where classical combinatorial arguments do not provide any interesting information. Recently, some constructive methods have been devised to give a randomized algorithm that nds the desired object and that run in polynomial time with high probability. When such algorithm exists, it is also interesting to study how to derandomize it to provide a deterministic algorithm. On this section we will comment some of these techniques. When considering random combinatorial objects, most of their combinatorial properties can be expressed as a function of dierent random variables, f(X1, . . . , XN) . One of the main concerns of the probabilistic method is to study the behavior of these random variables f(X1, . . . , XN) by understanding each random variable Xi as well as the interplay among them. For instance, one can look at the expected value of f(X1, . . . , XN) . In many situations, we want to know how likely is that f(X1, . . . , XN) lies close to its expected value. For this reason, there is a bunch of probabilistic tools to deal with concentration of random variables around their expected value, also known as large deviation inequalities. Nonetheless, in this thesis we will focus in the problem of estimating the probability that f(X1, . . . , XN) = 0 . One common situation in the probabilistic method arises when the existence of the desired structure can be expressed in terms of the avoidance of certain set of bad 1 2 events A={A1, . . . , AN} from the probability space. For instance, a proper coloring can be understood as a random coloring that avoids the events dened by monochromatic edges. This motivates the denition of the following function f(X1, . . . , XN) = X=X1+···+XN , where Xi is the indicator random variable of the event Ai∈ A . Then, X counts the number of bad events in a particular instance of the probability space and the probability that X= 0 is exactly the probability that no bad event from A occurs. This property turns to be very useful. For example, the existence of at least one object satisfying our restrictions can be ensured by bounding this probability away from zero. The study of the probability that X= 0 is not only related to existential results, but also to enumeration. Suppose that each element of our space appears with equal probability, that is, we have a uniform distribution. Then, the size of the probability space times the probability that a random object satises X= 0 , provides the exact number of elements of this space that fulll the desired property dened by the avoidance of A . In many cases it is hard to exactly compute the probability that X= 0 , even for small probability spaces. However, meaningful asymptotic estimations can be given when the size of the probability space is large. Some applications of this idea will be seen in dierent parts of the thesis. Let us focus in the tools we are going to use to bound Pr(X= 0) . If the random variables Xi are nonnegative and mutually independent, it is easy to compute such probability, Pr(X= 0) = Pr N \ i=1{Xi= 0}!= N Y i=1 (1 −Pr(Xi6= 0)) ∼e−E(X). (1.1) In particular, the distribution of the number of bad events that are satised, X , can be approximated by a Poisson random variable with parameter E(X) . Obviously, if the random variables are highly dependent this estimation can be far from being correct. Intuitively speaking, a high correlation among the variables will force Pr(X= 0) to deviate from the estimation of (1.1). Consider the following experiment. Flip just one coin and for all i∈[N] , set Xi= 1 if tail appears and Xi= 0 otherwise. It is clear that Pr(X= 0) = 1/2 , while the estimation in (1.1) gives e−N/2 , which can be arbitrarily small. This suggests that we do not have a general intuition to rely on when computing the probability that no bad event is satised. Nevertheless, the estimation in (1.1) of such probability is useful when the dependencies among the random variables Xi are weak, meaning that each Xi is mutually independent to large sets of random variables; or when the join probabilities are close to the product of the individual ones. The Poisson Paradigm states that, when there are few dependencies among the events in A or these dependencies are weak, the probability of these bad events not happening at the same time should behave similar to the estimation in (1.1). As a paradigm, this is not always working but provides an intuition under some circumstances on what may be the truth. The exact conditions under which we can ensure that the Poisson Paradigm is satised, may change depending on the techniques used and can be either local or global on the set of events A . In this chapter, we will overview some of them. For a detailed explanation of the techniques and the conditions they require to be applied, we refer the reader to Section 2.2.2. Let us start by introducing a well known tool to provide existential proofs of combinatorial objects, the Lovász Local Lemma (LLL). The local lemma was settled by Lovász and Erd®s in Chapter 1. Introduction 3 1975 (see [52]) to show the existence of 3 -colorings in hypergraphs under some local restrictions on the hyperedges. Since then, it has been a useful tool for solving a great diversity of problems. As seen before, if A is a nite set of mutually independent events, each with probability strictly less than one, then the probability that no event occurs is always strictly positive. The LLL allows us to slightly relax the independence condition. In order to apply it, the set A must satisfy the following conditions: for every event Ai∈ A , if the set of all the events but Di are mutually independent from Ai , then the sum of the probabilities of the events in Di is not too large. If this condition is satised, then the probability that none of the events holds is strictly positive under some specic quantication provided by the LLL. Because of this conditions, one can imagine the local lemma as a local union bound. The union bound implies that for every set of events A such that PN i=1 Pr(Ai)<1 , we have Pr(∩N i=1Ai)>0 . The conditions needed to apply the local lemma, can be understood as a local version of the union bound. The local lemma, not only gives the existence of these structures without bad events, but also provides and explicit exponential lower bound for it. In many cases, this bound is asymptotically tight. The power of the local lemma lies in the fact that it provides the existence of elements which have exponentially small density in a large space of combinatorial objects. Observe that some other probabilistic techniques, such as the rst or the second moment, typically show the existence of elements that have constant density in the space. As we will see in the forthcoming chapters, the local lemma takes advantage of the locality of certain dened properties in combinatorial structures. For instance, this tool is of particular interest when analyzing graphs with bounded maximum degree. In most of the applications it is useful to study the dependency graph of the set A (see Denition 2.6) that captures the dependencies among the events. However, in order to illustrate the statement of the local lemma, we introduce a simplied version of it, known as the symmetric local lemma, for which the dependency graph is implicitly dened in the statement. Let A be a set of events such that Pr(Ai) = p for every Ai∈ A , Suppose that each event is mutually independent from all but at most d other events. If, ep(d+ 1) ≤1, (1.2) then, Pr(∩N i=1Ai)>0 . The constant e in (1.2) cannot be improved as showed by Shearer [119]. Gebauer, Szabó and Tardos [69] proved that the local lemma is also tight in the context of k -CNF formulas [69]. Their proof is based on the lopsided version of the Lovász Local Lemma, which was introduced by Erd®s and Spencer [53] in the context of latin transversals of square integer matrices. In this lopsided version, the condition of mutual independence to build the dependency graph, is relaxed for events that are positively correlated, obtaining a lopsidependency graph (see Denition 2.8). We will make use of this version in the Chapter 3 of this thesis. However, one of the main drawbacks of the local lemma is that it just takes into account the number of dependencies among the events, but not the strength of these dependencies. For instance, if A is a set of almost independent events one would expect to be able to derive a lower bound on Pr(X= 0) similar to (1.1). Unfortunately, the local lemma is not able to 4 provide such a result. As we will see in Section 2.2.2.3, we have other tools that allow us to give a meaningful upper bound on the probability of X= 0 , even in the case where there are no mutually independent events. While the local lemma is useful to provide existential results, it does not give the means to construct an object that satises the desired property. In this direction, Moser and Tardos [108, 109] propose an algorithmic version of the Lovász Local Lemma, following earlier work by Beck [14] and by Molloy and Reed [104]. This version provides randomized algorithms to nd objects for which the standard version of the Lovász Local Lemma can prove their existence. Moreover, the algorithm is ecient; it runs in almost linear time in average. This has been a real breakthrough in the area. The method, also known as entropy compression has been useful to improve certain results where the non constructive version of the local lemma had been already applied earlier [75, 56]. Although upper bounds on the probability of avoiding a set of events A at the same time do not provide existential results of any kind, for some applications, like enumeration, they are particularly useful. Some applications of it will be seen in Chapters 3 and 6. Janson [81] introduced a useful inequality, which can be also thought as a concentration inequality (see [8, Theorem 8.7.2]), that we can use to bound from above the probability that X= 0 . Here, in contrast with the local lemma, pairwise join probabilities have an important role. However, this inequality can be applied just to a certain type of events which, in particular, should be positively correlated (see Theorem 2.15 for the complete statement). Suen [123] propose a similar version of this inequality where the particular setting of the Janson inequality is not required anymore. This allows us to study any setting, even if the nature of the dependencies is not clear. As Janson inequality, Suen inequality is also sensible to the dierent pairwise relations among events by taking into account the probabilities Pr(Ai∩Aj) , when Ai and Aj are not mutually independent. Since it is stated in a wider context, obviously, Suen inequality is not as strong as Janson inequality and can be used only in the cases where the dependencies among events are neither very numerous nor very strong. This inequality is particularly useful for some cases where dependencies are bounded. Some nice examples of the use of this inequality can be found in [66, 24]. Another good reference of it is the paper of Janson [82]. In fact, if the dependencies are strong, both Janson and Suen inequalities can be worse than the simple application of the second moment method. A promising contribution was made by Lu and Székely [97, 98]. There, the authors consider a dierent version of the dependency graph, the socalled ε near dependency graphs (see Denition 2.9), and adapt the local lemma to give an upper bound for Pr(X= 0) instead of a lower bound. Although it is not easy to show that a graph is an ε near dependency graph, the authors provide a good example by considering the problem of nding a perfect matching in the complete graph that avoids a family of bad partial matchings. This example is closely related to the lopsidependency graph dened in [53]. By means of their approach, Lu and Székely manage to count the number of regular graphs, latin rectangles or permutations without k cycles. As in the case of the local lemma, this last approach does not consider pairwise join probabilities. Chapter 1. Introduction 5 However, the denition of ε near dependency graphs, reduces the number of dependencies to be considered, similarly as in the lopsided case, and can be very useful in some cases. In conclusion, these tools provide upper and lower bounds for the probability that a certain set of bad events do not occur. Therefore, they can approximate the number of congurations that avoid all these bad events. Hence, they do not just provide existence results, but also enumerative ones. Some of the material in this thesis has been already published or is to appear in journals [62, 115, 112]. Most of the remaining material has also been published as a preprint in the ArXiv server [63, 114], and is currently submitted for publication. The contributions have also been presented in several conferences and workshops. This thesis addresses dierent problems in which the above framework tools are thoroughly exploited: Rainbow matchings of edge colored complete bipartite graphs (Chapter 3), Identifying codes in graphs (Chapters 4 and 5), Consecutive pattern avoiding in permutations (Chapter 6) and the Lonely Runner Conjecture (Chapter 7). In what remains of this chapter, we briey review each problem of the thesis with an small introduction of the topic, the statement of the main results and some comments on the techniques used to prove them. 1.1 Rainbow Perfect Matchings in Complete Bipartite Graphs A subgraph H of an edgecolored graph G is rainbow if no color appears twice in the edges of H . In particular, we will focus in rainbow perfect matchings of an edgecolored complete bipartite graph Kn,n . This case is of particular interest due to the connexion with latin transversals in integer matrices. Recall that a latin transversal is a set of n positions of an n×n matrix, no two in the same row nor the same column, that contain all dierent elements. Our work is motivated by the following longstanding conjecture of Ryser on the existence of latin transversals in latin squares: Conjecture 1.1 (Ryser Conjecture [118]) . Every latin square of odd size admits a latin transversal. This conjecture was extended by Stein [121] to n×n integer matrices containing n copies of each element in {1, . . . , n} . An interesting approach on Stein's conjecture was given by Erd®s and Spencer [53]. Theorem 1.2 ([53]) . Let A be an integer matrix. If every entry in A appears at most n−1 4e times, then A has a latin transversal. In Chapter 3 we study the number of rainbow matchings in a given edgecoloring of Kn,n , where every color appears at most some number of times, thus extending Theorem 1.2. The techniques used to derive these bounds are inspired by the framework devised by Lu and 6 1.1. Rainbow Perfect Matchings in Complete Bipartite Graphs Székely [98] to obtain asymptotic enumeration results using the Lovász Local Lemma. The main result in Chapter 3 is the following theorem. Theorem 1.3. Given an edgecoloring of Kn,n such that no color appears more than n/k times, k≥13.66 , let t be the number of pairs of nonincident edges that have the same color. Then, the number of rainbow perfect matchings is at most exp −1−3 k−60 k2t n(n−1)n!, and at least exp −1 + 16 kt n(n−1)n!. Observe that the dependency on t is natural, since a coloring in which all pairs of monochromatic edges are mutually incident ( t= 0 ) has n! rainbow perfect matchings. Any proper edgecoloring where each color appears exactly n/k times, satises t∼n3/2k . Corollary 1.4. Given a proper edgecoloring of Kn,n in which each color appears exactly n/k times, k≥13.66 , the number of rainbow perfect matchings is at most γ2(k)nn! and at least γ1(k)nn! for some constants 0< γ1(k)< γ2(k)<1 which depend only on k . The second part of Chapter 3 is devoted to the study of the existence of rainbow perfect matchings in random edgecolorings. We restrict ourselves to colorings with a xed number s=kn of colors and we dene two natural random models that t with this condition: the uniform random model, Cu(n, s) , and the regular random model, Cr(n, s) . Analogous results to the one in Theorem 1.3 can be proved for these random models. Proposition 1.5. The expected number of rainbow perfect matchings in an edgecoloring of Kn,n chosen at random from the Cu(n, s) (or the Cr(n, s) ) with s=kn colors, k > 1 , is exp −k(k−1) ln k−1 k+ 1+o(1)n2 sn!. For k= 1 , the expected number is exp (−(1 + o(1))n)n!. Since the edgecoloring is chosen at random, the probability that a perfect matching selected at random is rainbow, is more concentrated than in the case of arbitrary edgecolorings. Finally, we show that in the Cu(n, s) model, an edgecoloring has a rainbow perfect matching with high probability. Theorem 1.6. An edgecoloring of Kn,n chosen at random from the Cu(n, s) with s≥n colors, contains a rainbow perfect matching with high probability. This result can be easily extended to the Cr(n, s) using the same ideas. In particular, this implies that the conjecture posed by Stein is true for almost all edgecolorings. The results of Chapter 3 are joint work with Oriol Serra and can be found in [115]. Chapter 1. Introduction 7 1.2 Bounds for identifying codes in terms of degree parameters Given a graph G , an identifying code C is a dominating set such that for any two vertices, their neighborhoods within C are nonempty and distinct. This property can be used to distinguish all vertices of the graph from each other. Unlike dominating sets, not every graph can have an identifying code. In fact, it is easy to check that a graph has a identifying code if and only if there are no two adjacent vertices connected to the same set of vertices. For the sake of simplicity, throughout the section we will assume that G admits an identifying code. Motivated by the applications, given a graph G we want to study the smallest size of an identifying code, also called the identifying number of G and denoted by γ ID (G) . The following bounds are known for this number, log2(n+ 1) ≤γ ID (G)≤n . In Chapter 4, we provide bounds on the identifying number in terms of degree-.related graph parameters such as the minimum and maximum degree, denoted by d and ∆ respectively. We also focus on the case of d regular graphs. In the rst part of Chapter 4 we answer partially a question raised in [58] on the size of a minimum identifying code in a graph with bounded maximum degree. It was showed in [86] that if G has maximum degree ∆ , then γ ID (G)≥2n d+2 . While the proof of this result is straightforward, it does not seem so easy to provide a sharp upper bound. It was conjectured in [61] that the following upper bound holds. Conjecture 1.7 ([61]) . For any connected graph G with maximum degree ∆ , γ ID (G)≤n−n ∆+O(1) . Graphs with maximum degree ∆ that admit an identifying code of size n−n ∆ are known (see Section 4.5). Thus, if Conjecture 1.7 holds, it is best possible. It was showed in [59] that γ ID (G)≤n−n O(∆5) , and γ ID (G)≤n−n O(d3) when G is d -regular. In this thesis we prove an upper bound for γ ID (G) when G has bounded maximum degree. The exact statement of this result can be nd in Theorem 4.6. As corollaries of it, we have the following results. Corollary 1.8. For any connected graph G with maximum degree ∆ , γ ID (G)≤n−n O(∆3). In particular, Theorem 4.6 also allows us to prove an asymptotic version of the conjecture for dierent classes of graphs. Corollary 1.9 (Regular graphs) . For any connected d regular graph G , γ ID (G)≤n−n O(d). 8 1.3. Large spanning subgraphs admitting small identifying codes Corollary 1.10 (Graphs excluding complete graphs as minors) . Let G∆ be a the class of connected graphs that have maximum degree ∆ and exclude Kk as a minor. Then for every graph G∈ G∆ , γ ID (G)≤n−n c(k)d, for some constant c(k) that depends on k . The proof of the main theorem, uses the weighted version of Lovász Local Lemma to show the existence of an identifying code, together with standard concentration bounds, to show that the code, selected at random, is small enough. In order to understand the behavior of γ ID (G) for d regular graphs it is worthy to study typical d regular graphs. The second part of this Chapter is devoted to compute the value of γ ID (G) with high probability, for a d regular graph chosen uniformly at random. Identifying codes have been previously studied in two models of random graphs, the classic random graph model [66] and the model of random geometric graphs [110]. We will deal with random regular graphs through the so-called Conguration model (see Subsection 2.3.1). First, it is convenient to give an upper bound for the size of an identifying code in graphs with minimum degree d , when the girth of the graph is at least 5 . Theorem 1.11. For any graph G with minimum degree d and girth at least 5 , we have γ ID (G)≤(1 + od(1))3 log d 2dn . Since d regular graphs do not have many triangles and 4 cycles, one can adapt the proof to show the following. Theorem 1.12. Let G be a d regular graph chosen uniformly at random, d≥3 . With high probability, we have γ ID (G) = log d+O(log log d) dn . The results of Chapter 4 are joint work with Florent Foucaud and can be found in [62]. 1.3 Large spanning subgraphs admitting small identifying codes Consider any graph parameter that is not monotone with respect to graph inclusion. Given a graph G , a natural problem in this context is to study the minimum value of this parameter over all spanning subgraphs of G . In particular, how many edge deletions are sucient in order to obtain from G a graph with optimal value of the parameter? Herein, we study this question with respect to the identifying code number of a graph, a parameter introduced in Section 1.2. There are very dense graphs that have a huge identifying code number; sparse graphs, such as trees and planar graphs, also have a linear identifying code number [117]. On the other hand, one can also nd sparse and dense graphs with logarithmic identifying code number [106, 66], which is the smallest it can be. Chapter 1. Introduction 9 This motivates the following question: Given any suciently dense graph, can we delete a small number of edges to get a spanning subgraph with a small identifying code? This question is related to the notion of resilience of a graph with respect to a graph property P [122]. Despite being dense, the random graph G(n, p) (for 0<p<1 ) has a logarithmic size identifying code, as with high probability, γ ID (G(n, p)) = (1 + o(1)) 2 log n log (1/q), where q=p2+ (1 −p)2 [66]. Comparing this result with the examples of dense graphs with high identifying code number, one can guess that, in a dense graph, the lack of structure implies the existence of a small identifying code number. The following theorem, formalizes this idea. Theorem 1.13. For every graph G on n vertices with maximum degree ∆ = ω(1) and minimum degree d≥66 log ∆ , there exists a subset of edges F⊂E(G) of size |F|=O(nlog ∆) , such that γ ID (G\F) = Onlog ∆ d. The next theorem shows that Theorem 1.13 cannot be improved much. Theorem 1.14. For every d≥2 , there exists a d regular graph Gd n on n vertices with the following properties. 1. For every M≥0 , there exists a constant c > 0 such that for every set of edges F⊂E(Gd n) satisfying γ ID (Gn\F)≤Mnlog d d , the size of F is |F| ≥ cn log d . 2. For every spanning subgraph H of Gd n , γ ID (H)=Ωnlog d d . When d= Poly (∆) , Theorem 1.14 shows that Theorem 1.13 is asymptotically tight. Moreover, we also show that the hypothesis of Theorem 1.13 are necessary. There are graphs with bounded ∆ and graphs for which d≤log ∆/2 , such that all their spanning subgraphs have a linear identifying code number. Since the identifying code number is a nonmonotone property, we also consider the case where edges can be added instead of deleted in G . For such a case, analogous results are derived. In [12], the notion of a watching system has been introduced as a relaxation of identifying codes: in a watching system, code vertices (watchers) are allowed to identify any subset of their closed neighborhood, and several watchers can be placed in one vertex. Under the hypothesis of Theorem 1.13 and as a corollary of it, we can provide a watching system of size O(nlog ∆/d) . The results of Chapter 5 are joint work with Florent Foucaud and Oriol Serra, and can be found in [63]. 10 1.4. Consecutive pattern avoiding in permutations 1.4 Consecutive pattern avoiding in permutations A permutation π∈ Sn of length n contains σ∈ Sm of length m as a consecutive pattern if there exists a set of m consecutive elements in π that have the same relative order as the elements in σ . One interesting problem in the area of pattern avoidance in permutations is to determine the number of permutations in Sn that do not contain σ as a consecutive pattern. This problem was introduced by Elizalde and Noy in [50], where they completely determined the asymptotic enumeration of such permutations when m= 3 . For every σ∈ Sm , let αn(σ) be the number of permutations in Sn that avoid σ as a consecutive patterns. Elizalde [48] showed that the limit ρσ= lim n→∞αn(σ) n!1/n , exists, for any σ∈ Sm . In [50], the authors stress the importance of the monotone patterns, (1,2, . . . , m) and (m, . . . , 2,1) , in this problem and pose the following conjecture. Conjecture 1.15 (CMP conjecture [50]) . For every σ∈ Sm , ρσ≤ρ(1,2,...,m). Recently, this conjecture has been proved by Elizalde [49] using generating functions and the cluster method of Goulden and Jackson [71]. In Chapter 6 we study consecutive patterns in permutations using a completely dierent approach to the problem, based on the probabilistic tools we provide in Chapter 2. While our approach is not as precise as the generating function technique, it provides simpler alternative proofs of some known results, as the CMP conjecture, and allows us to obtain more general results. Our rst result gives an explicit upper bound for the number of permutations in Sn avoiding a given σ as a consecutive patterns, when σ is not monotone. Theorem 1.16. For every non monotone pattern σ∈ Sm , ρσ≤1−1 m!+O1 m2·m!. To prove this theorem we make use of Suen Inequality [123] since the number of dependencies in the set of bad events is small. By comparing the upper bound given by Theorem 1.16 with the result obtained by Elizalde and Noy [51] for monotone patterns we can give an alternative proof of the CMP conjecture as a corollary. Our proof works for any value of m≥5 , but does not provide meaningful results for the case m= 4 . Moreover, the probabilistic approach also allows us to estimate the dierence between the number of permutations avoiding the most and the second most avoided pattern. This last result has not been obtained by means of generating functions. Chapter 2. Background and Notation 17 nonnegative random variable X and t≥1 , Pr(X > tE(X)) ≤1 t. From it we can derive the following bound, known as Chebyshev inequality or simply the second moment method (e.g. see [8]). Lemma 2.1 (Chebyshev inequality) . For any random variable X and t > 0 , Pr(|X−E(X)| ≥ tσ(X)) ≤1 t2, (2.1) where σ2 is the variance of X . Observe that the upper bound on the probability is polynomial on t . Next, we will show that for the same deviation, an exponential bound can be achieved, by assuming some conditions on X . As we have already mentioned, the concentration of random variables is well studied in the case when X=f(X1, . . . , XN) and the variables Xi are independent. From now on, we will focus on the case where X=X1+···+XN . If the each random variable Xi follows a Bernoulli distribution with parameter pi , Xi∼ Be (pi) , then we can use the Cherno inequality to bound the tails. Lemma 2.2 (Cherno inequality, Corollary A.1.14 in [8]) . Let X1, . . . , XN be independent Bernoulli random variables and dene X=PN i=1 Xi . Then, for all ε > 0 , Pr(|X−E(X)| ≥ εE(X)) <2e−cεE(X), where cε= (1 + ε) log(1 + ε)−ε . The above inequality can also be deduced from Markov inequality. Similar results hold when the random variables Xi are bounded with probability one (see Hoeding inequality [79]). In particular, if the Bernoulli random variables are identically distributed, Xi∼ Be (p) , we can use a slightly better inequality. Lemma 2.3 (Cherno inequality for binomial distributions [9]) . Let X∼ Bin (N, p) be a Binomial random variable, then for all 0<ε<1 , 1. Pr(X≤(1 −ε)Np)<exp −ε2 2Np. 2. Pr(X≥(1 + ε)Np)<exp −ε2 3Np. 2.2.2 Avoiding a set of events and the Poisson Paradigm Let A={A1, . . . , AN} be a set of events in a nite probability space. As it has been seen in the previous chapter, in many cases the existence of a desired object can be expressed as the 18 2.2. The probabilistic method avoidance of all the events in A in a probability space that contains a large set of objects. The goal of this section is to show the basic probabilistic techniques to study the following probability, Pr N \ i=1 Ai!, (2.2) in dierent contexts. Recall that two events A1 and A2 are independent if Pr(A1∩A2) = Pr(A1) Pr(A2) . Then, we say that a set of of events A is pairwise independent if for any i6=j , Pr(Ai∩Aj) = Pr(Ai) Pr(Aj) . An event A is mutually independent from {Ai}j∈S if and only if Pr(A| ∩i∈S0Ai) = Pr(A) for any S0⊆S . A set of events A={A1, . . . , AN} is mutually independent if and only if Pr(∩i∈SAi) = Qi∈SPr(Ai) for any S⊆[N] . If A is mutually independent, we have Pr N \ i=1 Ai!= N Y i=1 (1 −Pr(Ai)) . (2.3) In general, the set A will not be mutually independent and it will not be straightforward to compute (2.2). The well known inclusionexclusion formula provides an exact way to get the desired probability. Pr N \ i=1 Ai!= 1 −Pr N [ i=1 Ai!= N X k=0 (−1)kX S∈([N] k) Pr \ j∈S Aj. (2.4) The main drawback of this expression is that, in general, it is hard to provide an explicit value for the joint probabilities Pr Tj∈SAj . This implies that for most of the problems, we will not be able to give an exact expression for (2.2). However, sometimes it suces to have a good enough estimation of such probabilities. From (2.4) we can derive the following bounds on (2.2), known as Bonferroni inequalities. For any 0≤m≤N/2 , we have Pr N \ i=1 Ai!≤ 2m X k=0 (−1)kX S∈([N] k) Pr \ j∈S Aj Pr N \ i=1 Ai!≥ 2m+1 X k=0 (−1)kX S∈([N] k) Pr \ j∈S Aj. These inequalities are specially useful in the case where the events are almost incompatible since then, the joint probabilities are small and they converge quickly to (2.2). A particular case of the Bonferroni inequalities is the union bound, which allows us to give a simple lower bound on (2.2), Pr N [ i=1 Ai!≤ N X i=1 Pr(Ai), Chapter 2. Background and Notation 19 also written as Pr N \ i=1 Ai!≥1− N X i=1 Pr(Ai). (2.5) The crucial fact that makes the union bound one of the most used inequalities in probabilistic combinatorics is that one does not need to care about the dependencies among the events in A to deduce a lower bound on (2.2). We will repeatedly use this bound all along the thesis. Even though this bound is sharp (consider a set of disjoint events), it is not a meaningful bound if most of the events in A have large intersection. The interested reader in Bonferronitype inequalities is referred to the book of Galambos and Simonelli [68]. The following inequality can be found there and slightly improves the union bound in the case where the events are not disjoint. Lemma 2.4 (Inequality I.11 from [68]) . For any tree T with vertex set V(T)=[N] , we have Pr N \ i=1 Ai!≥1− N X i=1 Pr(Ai) + X ij∈E(T) Pr(Ai∩Aj). (2.6) For any event Ai∈ A , it is interesting to consider its associated indicator random variable, Xi and, in particular, the following the random variable, X= N X i=1 Xi. (2.7) As we have already observed in the previous chapter, recall that the expression in (2.2) is equivalent to Pr(X= 0) . Notice that one can upper bound the previous probability using a concentration inequality on the variable X . The probability that X= 0 is at most the probability that X deviates E(X) from E(X) . If no assumption on the events in A is done, we can use the second moment method. By setting t=E(X)/σ(X) in Lemma 2.1, we get the following corollary. Lemma 2.5. For any random variable X with E(X)6= 0 , Pr(X= 0) ≤σ2(X) E(X)2. By showing that σ(X)/E(X)→0 , we know that with high probability, X6= 0 . In a general context, Equation (2.5) as well as Lemma 2.5 are tight. Nevertheless, as we explained in the previous chapter, better bounds can be provided if we assume that the set A has a small number of dependences or these dependences are weak. If one of these conditions holds, intuitively speaking, the probability that any of the events in A holds, is similar to the case when the events are mutually independent (see (2.3)). 2.2.2.1 Dependency graph To show that good approximations of (2.2) can be given under certain conditions, the denition of an underlying structure that captures the mutual independence among the elements of A , the 20 2.2. The probabilistic method socalled dependency graph, is of special interest. Denition 2.6. A graph H=H(A) is a dependency graph for the set of events A={A1, . . . , AN} if V(H) = [N] , and if i∈[N] is not connected to S⊆[N]\{i} , then Pr(Ai| ∩j∈SAj) = Pr(Ai). (2.8) As a consequence, if H is a dependency graph for A , each stable set S⊆V(H) indexes a set of mutually independent events, that is, Pr(∩i∈SAi) = Qi∈SPr(Ai) . Observe that the denition of H is not unique but the property of being a dependence graph of A is monotone by subgraph inclusion. In particular, the complete graph KN is always a dependency graph for A but we will be interested in studying edgeminimal dependency graphs. Thus, each time we use a dependency graph for a set A , we must specify its set of edges. For the sake of convenience, we will denote by µ the expected number of events from A that are satised µ=E(X) = N X i=1 Pr(Ai). In order to control the dependencies among the events in A , the following two parameters are usually associated to the dependency graph H . To measure the global eect of the dependencies, we consider ∆∗=X ij∈E(H) Pr(Ai∩Aj), and for the local one, δ∗= max 1≤i≤NX j:ij∈E(H) Pr(Aj), where E(H) denotes the edge set of H . Let us now state a useful result that provides a good dependency graph if the set of events A satises a certain property. Observation 2.7 (The Mutual Independence Principle [105]) . Let Y={Y1,...YM} be a set of independent random experiments. Suppose that A={A1, . . . , AN} is a set of events where each Ai is determined by a subset of experiments indexed by Fi⊆[M] . For any i∈[N] and S⊂[N] , Ai is mutually independent from {Aj}j∈S if Fi∩(∪j∈SFj) = ∅ . Equivalently, the graph with vertex set [N] where ij is an edge if and only if F1∩F26=∅ , is a dependency graph for the set of events A . Some other special types of dependency graphs will be used in this work. Erd®s and Spencer [53] introduced the notion of lopsidependency. Denition 2.8. A graph H is a lopsidependency graph (also known in the literature as negative dependency graph [98]) for the set of events A if V(H) = [N] and, if i∈[N] and S⊆[N]\{i} share no edges, then Pr(Ai| ∩j∈SAj)≤Pr(Ai). (2.9) Chapter 2. Background and Notation 21 Observe that any dependency graph for A is also a lopsidependency graph. The idea behind this denition is that positive correlation among events increases the variance and thus, it increases the probability that X= 0 . For that reason, if we want to give a lower bound on (2.2), positively correlated events do not need to be counted as depending events. To provide upper bounds on (2.2), it is worthy to set the notion of positive dependency. This was recently introduced by Lu and Székely [97, 98] in the context of events dened by matchings in complete graphs or complete bipartite graphs. Denition 2.9. For any ε > 0 , a graph H is an ε -near positive dependency graph for the set of events A={A1, . . . , AN} if V(H) = [N] , and the following conditions are satised: i) Pr(Ai∩Aj) = 0 for each ij ∈E(H) , and ii) if i∈[N] and S⊆[N]\{i} share no edges, then Pr(Ai| ∩j∈SAj)≥(1 −ε) Pr(Ai). (2.10) Condition i) implies that only incompatible events can be connected. Condition ii) says that the nonoccurrence of any set of nonneighbors can not shrink the probability of Ai too much. Thus the event Ai is almost negatively correlated from the events in the set S . The intuitive idea behind this dependency graph is that the only bad dependencies when upper bounding (2.2) are given by positively correlated events events that are negative correlated and compatible with a given one, should not be considered. like in the denition of lopsidependency, is that, when , the 2.2.2.2 Lower bounds and the Lovász Local Lemma In this subsection we will show how to bound from below the probability in (2.2), conditioned to the structure of a dependency graph for A . The classical tool for such a purpose is the Lovász Local Lemma which was introduced by Erd®s and Lovász [52] in 1973. All along this subsection we will consider that H is a dependency graph for A , unless otherwise stated. Let us begin by giving its standard version. Lemma 2.10 (Lovász Local Lemma (LLL)) . Let A={A1, . . . , AN} be a set of events and let H be a dependency graph for A . If there exist some constants x1, x2, . . . , xN∈(0,1) such that Pr (Ai)≤xiY j:ij∈E(H) (1 −xj), (2.11) for each i∈[N] , then, for each T⊂[N]\{i} we have Pr Ai|\ j∈T Aj≤xi. 22 2.2. The probabilistic method In particular, for each pair S, T ⊂[N] of disjoint sets we have Pr \ i∈S Ai|\ j∈T Aj≥Y i∈S (1 −xi), (2.12) and Pr N \ i=1 Ai!> N Y i=1 (1 −xi). (2.13) The same lemma can be also stated when H is a lopsidependency graph. This was noticed by Erd®s and Spencer [53]. Lemma 2.11 (Lopsided Lovász Local Lemma (LLLL)) . Let A={A1, . . . , AN} be a set of events and let H be a lopsidependency graph for A . If there exist some constants x1, x2, . . . , xN∈(0,1) such that Pr (Ai)≤xiY j:ij∈E(H) (1 −xj), (2.14) for each i∈[N] , then, for each T⊂[N]\{i} we have Pr Ai|\ j∈T Aj≤xi. In particular, for each pair S, T ⊂[N] of disjoint sets we have Pr \ i∈S Ai|\ j∈T Aj≥Y i∈S (1 −xi), (2.15) and Pr N \ i=1 Ai!> N Y i=1 (1 −xi). (2.16) Next, we present a symmetric version that can be easily derived from Lemma 2.10 and which can be used when all the events in A play the same role. Lemma 2.12 (Symmetric Lovász Local Lemma) . Let A={A1, . . . , AN} be a set of events and let H be a dependency graph for A . If Pr(Ai) = p for each i∈[N] , H has maximum degree ∆ = ∆(H) , and ep(∆ + 1) ≤1, (2.17) where e≈2.718 , then Pr N \ i=1 Ai!≥(1 −ep)N. Chapter 2. Background and Notation 23 Observe that condition (2.17) is very similar to the condition eδ∗≤1 . The following version of the local lemma is also a corollary from Lemma 2.10. It can be used in the case we can assign a weight to each event in A and set the value of xi as a function of the corresponding weight. Lemma 2.13 (Weighted Lovász Local Lemma [105]) . Let A={A1, . . . , AN} be a set of events and let H be a dependency graph for A . If there exist some integer weights t1, . . . , tN≥1 and a real p≤1 4 such that for each i∈[N] : •Pr(Ai)≤pti , and •Pj:ij∈E(H)(2p)tj≤ti 2 , then Pr N \ i=1 Ai!≥ N Y i=1 (1 −(2p)ti). (2.18) By giving a total order on the set A we can derive a directed version of the local lemma. One particular case was proposed by Peres and Yuval [116] in the context of lacunary integer sequences. Lemma 2.14 (Onesided Local Lemma [116]) . Let A={A1, . . . , AN} be a set of events and let H be a dependency graph for A . If there exist some real numbers x1, x2, . . . , xN∈(0,1) such that for each i∈[N] there is an integer 0< m(i)≤i such that Pr Ai|\ k<m(i) Ak≤xi i−1 Y j=m(i) (1 −xj). (2.19) Then, Pr N \ i=1 Ai!≥ N Y i=1 (1 −xi). (2.20) 2.2.2.3 Upper bounds We can bound (2.2) from above by using standard concentration inequalities, around the expected value of X , as showed in Lemma 2.5. However, these bounds are far from being tight when X is the sum of almost independent variables. Here we present some of them that will be used in this thesis. Janson inequality [81] is a good tool to deal with that kind of problems when the elements of A are some special type of positively correlated events. Although we will not use it explicitly in this work we think it is worthy to state it in order to compare it with Suen inequality. 24 2.2. The probabilistic method Theorem 2.15 (Janson Inequality [81]) . Choose B1, . . . , BN subsets of a nite set Ω . Let S⊆Ω where each element ω∈Ω belongs to S independently with some probability. Dene the events Ai∈ A for any i∈[N] as Bi⊆S and let H be the dependency graph for A where ij is an edge if and only if Bi∩Bj6=∅ . Then, Pr N \ i=1 Ai!≤e−µ+∆∗. Moreover, if ∆∗≥µ , Pr N \ i=1 Ai!≤e−µ2/2∆∗. (2.21) Observe that in this case, an edgeminimal dependency graph H is given by ij ∈E(H) if and only if Bi∩Bj6=∅ . Janson [81] also gave an interesting oneway large deviation inequality extending the previous one. A bound with the same spirit was proposed by Suen in [123], although we refer the interested reader to the nice paper of Janson [82]. Theorem 2.16 (Suen Inequality, Theorem 2 in [82]) . Let A={A1, . . . , AN} be a set of events and let H be a dependency graph for A . Then, Pr N \ i=1 Ai!≤e−µ+∆∗e2δ∗ . (2.22) Since δ∗>0 , Suen inequality is always worse than Janson inequality. Moreover, it is useless if ∆∗e2δ∗≥µ which happens to be the case for many problems where the dependency graph contain many edges or has a large maximum degree. Nevertheless, it is much more general since no assumptions on the set of events A is done. Thus, it will be extremely useful for (locally) sparse dependency graphs. One important remark that will carry some consequences in Chapter 6 is the fact that Suen inequality takes into account the pairwise join probabilities among sets of mutually depending events. That makes the inequality sensitive to the relation among pairs of events. On the other hand, the local lemma is our main tool to provide a lower bound on 2.2 when there are not many dependences in A . Unfortunately, it can not distinguish the dierent nature of the dependencies among events, but just the number of local dependencies. Finally, as we suggested in Subsection 2.2.2.1, we will show how to use ε -near positive dependency graphs to provide upper bounds on (2.2). Theorem 2.17 (Lu and Székely [98]) . Let A={A1, . . . , AN} be a set of events with an ε -nearpositive dependency graph H . Then, Pr N \ i=1 Ai!≤ N Y i=1 (1 −(1 −ε) Pr(Ai)) ≤e−(1−ε)µ. Chapter 2. Background and Notation 25 The main drawback of this approach is that, typically, it is hard to prove the conditions needed for a ε -near-positive dependency graph. In the case that such graph can be settled, Theorem 2.17 provides a meaningful upper bound for (2.2) even when there are many dependencies among the events. A good example of that will be showed in Chapter 3. 2.3 Models of Random Combinatorial Structures The idea behind the proofs that use the probabilistic combinatorics is to set a probability space on a nite set of combinatorial objects and to show that an object with the desired condition exists with some probability. For this reason, it is crucial to study dierent models of combinatorial structures where the previous techniques can be applied. In Chapter 6 we will study a problem in permutations. For this reason it is worthy to consider the following model of random permutations. A permutation π= (π1, . . . , πn) is an ordering of the set [n] . The symmetric group on n elements, denoted by Sn , is the set of n! permutations of length n . For any sequence of distinct positive real numbers X= (x1, . . . , xm) , we dene the standardization of X , st(x1, . . . , xm) = σ∈ Sm such that xi< xj if and only if σi< σj , that is the permutation on m elements that maintains the same relative order. For instance, the sequence (3,8,4,1) standardizes to st(3,8,4,1) = (2,4,3,1) . A permutation π selected uniformly at random from Sn satises the following useful property: for each integer m > 0 , every set of positions i1, . . . , im and every σ∈ Sm , Pr(st(πi1, . . . , πim) = σ) = 1 m!. For the sake of convenience, we introduce the following model that generates each permutation of Sn with equal probability. Let Z1, . . . , Zn be independent uniform random variables in (0,1) and let π= st(Z1, . . . , Zn) . Observe that with probability exactly one all the random variables are dierent and thus, π is well dened almost surely. This model is of special interest since we can exploit the independence property to study random permutations. 2.3.1 Models of Random Graphs We devote this subsection to briey review some models of random graphs that will appear throughout the thesis. Let us rst introduce the standard model of random graphs. The Erd®sRényi random graph model, denoted as G(n, p) , is the probability space over the set of all labeled graphs on n vertices, where a given graph G∈G(n, p) appears with probability Pr(G) = p|E(G)|(1 −p)(n 2)−|E(G)|. All the graphs with the same number of edges have the same probability to appear. In particular, in G(n, 1/2) each labeled graph on n vertices appears with the same probability, 2−(n 2) . Besides, a 26 2.3. Models of Random Combinatorial Structures random instance of G(n, p) can be obtained by placing each edge independently with probability p . These independence is very useful when analyzing the behavior of random graphs. Although we will not study the Erd®sRényi model of random graphs, we will often refer to it as example. An comprehensive study of random graphs and their main parameters can be found in the monographs of Bollobás [23] and Janson, uczak and Ruci«ski [83]. We also recommend the Chapter 10 from the book of Alon and Spencer [8] for a nice introduction to the topic. One of the goals of Chapter 4 is the study of identifying codes on random regular graphs. Thus, we want to set an easy to handle model, G(n, d) , that provides d regular graphs on n vertices with a uniform distribution. Unfortunately, it is not known how to explicitly generate a uniformly random sample in G(n, d) . One of the most common techniques to study random d regular graphs is to set a probability space over a larger class of multigraphs denoted by G∗(n, d) . This is known as the Conguration Model [15, 22]. In this model, a d regular multigraph on n vertices is obtained by selecting some perfect matching of Knd at random (see [129] for further reference). We will only consider cases where nd is even, as otherwise there does not exist any d regular graph on n vertices. In the Conguration Model, the set of vertices in Knd is partitioned into n cells of size d and each cell Wv is associated to a vertex v of the random regular graph. An edge e of a perfect matching of Knd induces either a loop in v (if it connects two elements of Wv ) or an edge between v and u (if it connects a vertex from Wv to a vertex in Wu ). This model produces dierent multigraphs with dierent probability, depending on the number of loops and multiedges. Since every d regular graph on n vertices has neither loops nor multiedges, each of them is produced with the same probability. It is showed in [129] that the probability the Conguration Model generates a simple graph satises Pr G is simple = (1 + o(1))e1−d2 4 if d=o(√n). (2.23) Thus, for constant d any property that holds with probability tending to 1 for G∗(n, d) as n→ ∞ , will also hold with probability tending to 1 for G(n, d) . If d→+∞ when n→+∞ , one must show that the statements in G∗(n, d) hold with high probability; in particular, with probability large enough to beat (2.23). In this case, another useful tool for such values of d is the Switching method (see [102, 93, 39, 113]). Finally we introduce another model of random graphs that generalizes the Erd®sRényi model. Let G be a labeled graph and p < 1 , then the graph Gp is an element from a probability space over the spanning subgraphs of G , where each labeled subgraph H⊆G appears with probability Pr(G) = p|E(H)|(1 −p)|E(G)|−|E(H)|. As before, an element H of this probability space can be modeled by deleting each edge from G independently with probability 1−p . A wellknown instance of this model is the classical Erd®sRényi random graph G(n, p) , where G=Kn . Many results that are showed in the Erd®s Rényi model G(d, p) can be translated to the Gp model, provided that G has minimum degree at least d . The model Gp has been widely studied [37, 65, 91, 92]. Alon [3] generalized this Chapter 3. Rainbow Perfect Matchings in Complete Bipartite Graphs 33 they have one common edge and they are compatible. Erd®s and Spencer [53] showed that H0 is a lopsidependency graph for M . By Theorem 3 in [98] we have that H is also a lopsidependency graph for the set of events AM with M∈ M . The following lower bound can be obtained in a similar way to Lu and Székely [98, Lemma 2]. Lemma 3.9. Given an edgecoloring of Kn,n where each color appears at most n/k times and an arbitrary color c , let M0=M1∪M2 be a set of matchings, where the elements of M1 are single edges with color c and the elements of M2 are monochromatic pairs of nonincident edges. We denote by m0 the size of M0 . If k≥13.66 and n > 40000 , then for every disjoint sets S, T ⊆[m0] Pr  \ i∈S Ai|\ j∈T Aj ≥e−(1+20/k)Pi∈SPr(Ai). (3.2) In particular, if S= [m0] and T=∅ , we have Pr m0 \ i=1 Ai!≥e−(1+20/k)µ, (3.3) where µ=Pm0 i=1 Pr(Ai) . Moreover, if the color c does not appear in E(Kn,n) , for every constant k≥10.93 and n > 200 , Pr m0 \ i=1 Ai!≥e−(1+16/k)µ. (3.4) Proof . Set AM0={A1, . . . , Am0} , where Ai=AM for some M∈ M0 . Since each color does not appear many times, we have |M1| ≤ n/k . Each of the n2 edges belongs to at most n/k −1 matchings in M2 . Thus, |M2| ≤ n2(n/k −1) 2=n2(n−k) 2k. If M∈ M1 , we have p1= Pr(AM) = 1/n whereas if M∈ M2 , p2= Pr(AM) = 1 n(n−1) . Therefore, µ=|M1| n+|M2| n(n−1) ≤n 2k, (3.5) if n is large enough with respect to k . Let us set t=|M1|/n + 4/k . If no edge is colored with color c , that is |M1|= 0 , we have t= 4/k . Then it can be checked that for every k≥10.93 n≥200 and p≤p2 pe(1+4t)t<1−e−(1+4t)p. (3.6) If |M1|>0 , then t≤5/k and for every k≥13.66 , n > 40000 and p≤p1 , (3.6) is also satised. In both cases, we can choose xi∈(Pr(Ai)e(1+4t)t,1−e−(1+4t) Pr(Ai)) for each i∈[m0] . Observe that the maximum number of matchings in M2 that are incompatible with a given matching M 34 3.2. Asymptotic enumeration of rainbow matchings is at most 2|M|n(n−1)/k : given a matching M∈ M2 , there are at most 2|M|n possibilities to select an edge e incident to either some edge in M , and at most n/k −1 choices for a second edge f with the same color than e . Hence, for any i∈[m0] , we have that X ij∈E(H) Pr(Aj)≤ |M1|· 1 n+4n(n−1) k·1 n(n−1) =t . Using the previous inequalities, for any i∈[m0] , we have Pr(Ai)< xie−(1+4t)t< xiY ij∈E(H) e−(1+4t) Pr(Aj)< xiY ij∈E(H) (1 −xj). (3.7) Let H0 be the graph on the set of events indexed by M0 , where two vertices are adjacent if the corresponding matchings are incompatible. By Theorem 3 in [98], H0 is a lopsidependency graph for M0 . Hence, we can use the Lopsided version of the Local Lemma (see Lemma 2.11), in particular (2.15) and (2.16), to nish the proof of the lemma. 3.2.2 Upper bound To provide an upper bound on the number of rainbow matchings we use the new enumeration tool provided by Lu and Székely in [98] (see Theorem 2.17 in Chapter 2). For such a purpose, we must set a ε nearpositive dependency graph H (see Denition 2.9 in Chapter 2). Lu and Székely [98] showed that an ε nearpositive dependency can be constructed using a family of matchings M . Unfortunately, the conditions of [98, Theorem 4] which would provide an upper bound for our case, do not apply to our family M of matchings. We give instead a direct proof for the upper bound which is inspired by their approach. Lemma 3.10. With the hypothesis of Lemma 3.9, the rainbow dependency graph H is an ε  nearpositive dependency graph with ε= 1 −e−(3/k+60/k2+o(1)) . Proof . Set AM={A1, . . . , Am} , where Ai=Ae,f for some {e, f}∈M . The rainbow dependency graph H for AM , clearly satises condition i) in the denition of ε near dependency graph, since two adjacent events contain incident edges and a matching is composed by a set of nonincident edges. For condition ii) we want to show that, for each i and each I ⊆ {j|ij 6∈ E(H), j 6=i} , we have the inequality Pr(Ai|B)≥(1 −ε) Pr(Ai), where B=∩j∈IAj . This is equivalent to show that Pr(B|Ai)≥(1 −ε) Pr(B). Let {a1, . . . , an} and {b1, . . . , bn} be the vertices of the two sides of the bipartite graph Kn,n . By symmetry, we may assume that Ai consists of the event related to the 2 matching {an−1bn−1, anbn} . Then {Aj:j∈ I} consists of some events related to the 2 matchings that coincide with {an−1bn−1, anbn} in exactly one edge , indexed by I1 ; and some events related to the 2 matchings in Kn0,n0=Kn,n −{an−1, an, bn−1, bn} , where n0=n−2 , indexed by I2 . The edge-coloring in Kn,n induces an edge coloring in Kn0,n0 where each color appears at most n0/k0 times, where Chapter 3. Rainbow Perfect Matchings in Complete Bipartite Graphs 35 k0=k(1 −2/n) . Consider now the probability space of random matchings of Kn0,n0 and let us dene the following event B0=∩j∈IA0 j , where A0 j is the event that the edges in Kn0,n0 corresponding to Aj are included in the random matching. Observe that if j∈ I1 then A0 j corresponds to only one edge while if j∈ I2 then it corresponds to two edges. Thus, Pr(B|Ai) = Pr(B0). (3.8) For convenience, we may split the event B corresponding to ∩j∈IAj in several events depending on the perfect matching containing {an−1br, anbs} . For any r, s ∈[n] , r6=s , let Cr,s denote the event related to the 2 matching {an−1br, anbs} . Dene Ir,s ⊂ I as the maximal subset of indices in I , whose corresponding edges meet none of the two vertices br, bs . Set Br,s =∩j∈Ir,s Aj . Let us show that Pr(B)≤1 n(n−1) X r6=s Pr(B0 r,s), (3.9) where, as before, B0 r,s =∩j∈Ir,s A0 j . We note that, by the denition of Br,s , we have B∩Cr,s =Br,s ∩Cr,s . Thus, Pr(B) = X r6=s Pr(B∩Cr,s) = X r6=s Pr(Br,s ∩Cr,s). We claim that for any r, s ∈[n] , r6=s , Pr(Br,s|Cr,s)≤Pr(Br,s|Cn−1,n). If Ir,s ⊆ I2 , by the denition of I2 none of the perfect matchings involved in ∩j∈I2Aj meets vertices in {an−1an, bn−1bn} . In this case, for all r, s , r6=s , Pr(Br,s|Cr,s) = Pr(Br,s|Cn−1,n). Suppose then that Ir,s∩I16=∅ . If some event indexed in I1 corresponds to a matching containing the edge anbn (or an−1bn−1 ) and s6=n (or r6=n−1 ), we have Pr(Br,s|Cr,s)=0, Otherwise, we have Pr(Br,s|Cr,s) = Pr(Br,s|Cn−1,n) as before. Moreover, we observe that Pr(Br,s|Cn−1,n) = Pr(B0 r,s) . Therefore Pr(B) = X r6=s Pr(Br,s|Cr,s) Pr(Cr,s)≤1 n(n−1) X r6=s Pr(Br,s|Cn−1,n) = 1 n(n−1) X r6=s Pr(B0 r,s), giving inequality (3.9). Let MI be the set of matchings corresponding to the events A0 j for j∈ I . By applying Lemma 3.9 with k0 , M0=MI , S=I \Ir,s and T=Ir,s , we obtain Pr(B0) = Pr(B0 r,s) Pr(∩j∈SA0 j|B0 r,s)≥Pr(B0 r,s)e−(1+20/k+o(1)) Pi∈SPr(Ai), (3.10) 36 3.2. Asymptotic enumeration of rainbow matchings for any r, s , r6=s , where xj are given in the proof of the lemma. By combining (3.8) with (3.10) we get n(n−1) Pr(B|Ai)≥X r6=s Pr(Br,s)e−(1+20/k+o(1)) Pi∈SPr(Ai). (3.11) Now we give a uniform bound on Pi∈SPr(Ai) . Recall that S=I \Ir,s is the subset of indices in I , whose corresponding edges are incident to either br or bs . We consider the following two sets: S1=I1\Ir,s and S2=I2\Ir,s . The size of both sets can be bounded independently of r and s by |S1| ≤ n k |S2| ≤ 2n0n0 k0−1≤2n(n−1) k. Then we have X i∈S Pr(Ai)≤|S1| n+|S2| n(n−1) ≤3/k . (3.12) By using (3.11) with (3.12) and (3.9) we get Pr(B|Ai)≥e−(3/k+60/k2+o(1)) 1 n(n−1) X r6=s Pr(Br,s)≥e−(3/k+60/k2+o(1)) Pr(B). (3.13) Therefore, ε= 1 −e−(3/k+60/k2+o(1)) , satises the conclusion of the lemma. Now we are able to prove Theorem 3.4. Proof of Theorem 3.4 . Set AM={A1, . . . , Am} , where Ai=Ae,f for some {e, f}∈M . By Lemma 3.10, the graph H from Denition 3.8 is an ε nearpositive dependency graph with ε= 1−e−(3/k+60/k2+o(1)) . It follows from Theorem 2.17 that the probability of having a rainbow perfect matching is upper bounded by Pr m \ i=1 Ai!≤ m Y i=1 (1 −(1 −ε) Pr(Ai)) ≤e−(1−)µ. By plugging in our value of ε and by using e−(3/k+60/k2+o(1)) ≥1−3 k−60 k2+o(1) we obtain Pr m \ i=1 Ai!≤e−(1−3/k−60/k2+o(1))µ. Combining this upper bound with the lower bound obtained directly from (3.4) in Lemma 3.9 we obtain exp −1 + 16 kµ≤Pr m \ i=1 Ai!≤exp −1−3 k−60 k2+o(1)µ. This proves the theorem. Chapter 3. Rainbow Perfect Matchings in Complete Bipartite Graphs 37 Observe that when k is suciently large, the asymptotic estimation coincides with the one obtained by assuming that the bad events Ai are mutually independent. 3.3 Random colorings In this section we will analyze the existence of rainbow perfect matchings in random edge colorings of Kn,n . Recall that, in the uniform random coloring model Cu(n, s) , each edge of Kn,n is given a color uniformly and independently chosen from a set of s colors, i.e. every possible coloring with at most s colors appears with the same probability. In the regular random coloring model Cr(n, s) a coloring is chosen uniformly at random among all colorings of E(Kn,n) with equitable color classes of size n2/s . Let us give a set up for this model. Consider two sets A and B each with n2 points. Partition A in s cells C1, . . . , Cs , each with n2/s elements, representing the dierent colors. Let B represent the edges of Kn,n . A perfect matching between the points of A and B induces an equitable edgecoloring of the entire graph. The probability space Cr(n, s) of colorings is settled by choosing such a perfect matching uniformly at random. Let us show that Cr(n, s) is a uniform model for the set of equitable edgecolorings of Kn,n Lemma 3.11. Every equitable edgecoloring with s colors has the same probability in the Cr(n, s) model. Proof . We show that every equitable edgecoloring arises from the same number of perfect matchings from A to B . Let C be an equitable edgecoloring of Kn,n . Let Ei⊂B be the set of edges that have color i under C . We have |Ei|=n2/s and there are (n2/s)! perfect matchings from Ci to Ei assigning color i to the edges in Ei . Therefore, there are exactly ((n2/s)!)s perfect matchings from A to B giving rise to the edgecoloring C . This number does not depend on C . We consider these two models since they simulate the worst situation among the colorings admitted in Theorem 3.4: the bounds on the probability that a perfect matching is rainbow only depends on the size of M , and this set has its largest cardinality when there are few colors and the number of occurrences of each of them is maximized. This means that there are exactly s=nk colors with n/k occurrences each. Observe that in both random models, the expected size of each color class is also n/k . In this sense, they are congruous to the hypothesis of Theorem 3.4. Proof of Proposition 3.6 . Consider an edgecoloring obtained using the Cu(n, s) model and let M denote a xed perfect matching of Kn,n . If XM is the random variable indicating that M is rainbow, then Pr(XM= 1) = s s·s−1 s·s−2 s·. . . ·s−(n−1) s = n−1 Y i=0 1−i s. (3.14) 38 3.3. Random colorings For s=n we can get directly from (3.14) Pr(XM= 1) = n! nn=e−(2+o(1))µ. Assume s>n . By writing (1 −x) = exp (log (1 −x)) for 0<x<1 , we have Pr(XM= 1) = n−1 Y i=0 exp log 1−i s = exp n−1 X i=0 log 1−i s! = exp Zn 0 log 1−x sdx +e1(n, s), where e1(n, s) is the error term obtained from replacing the sum for the integral. Since log 1−i s is decreasing, we have n X i=1 log 1−i s≤Zn 0 log 1−x sdx ≤ n−1 X i=0 log 1−i s. Thus, the error term can be bounded by e1(n, s)≤ n−1 X i=0 log 1−i s−Zn 0 log 1−x sdx (3.15) ≤ n−1 X i=0 log 1−i s− n X i=1 log 1−i s =log 1−n s = log k k−1=O(1) , where k=s/n . Also, Zn 0 log 1−x sdx =−(s−n) log s−n s−n . (3.16) Using µ∼n 2k , we get Pr(XM= 1) = exp −(k−1) log k−1 k+ 1n+e1(n, s) = exp −2k(k−1) log k−1 k+1+o(1)µ, proving the rst part of the proposition for the Cu(n, s) model. Now we study the probability that a xed perfect matching M is rainbow in the Cr(n, s) model. According to the construction of the Cr(n, s) model, the probability of M being rainbow is Chapter 3. Rainbow Perfect Matchings in Complete Bipartite Graphs 39 Pr(XM= 1) = n2 n2·n2−n2 s n2−1·n2−2n2 s n2−2·. . . ·n2−(n−1)n2 s n2−(n−1) = n−1 Y i=0 1−i(n2−s) s(n2−i) = exp n−1 X i=0 log 1−i(n2−s) s(n2−i)! = exp Zn 0 log 1−x(n2−s) s(n2−x)dx +e2(n, s), where e2(n, s) is the error term obtained from replacing the sum for the integral. If s=n we have Zn 0 log 1−x(n−1) (n2−x)dx =−n(n−1) log n n−1, which, by using the Taylor expansion of the logarithm, gives Pr(XM= 1) = e−(2+o(1))µ. By analogous arguments to those in (3.15), we can bound the error e2(n, s) = O(1) . In the case where s>n , and using k=s/n , we have Zn 0 log 1−x(n2−s) s(n2−x)dx =−(k−1) log k−1 k−(n−1) log n−1 nn =−(k−1) log k−1 k+1+o(1)n . Hence Pr(XM= 1) = exp −2k(k−1) log k−1 k+1+o(1)µ. Note that, for both models of random edgecolorings, the probability that a xed perfect matching is rainbow is asymptotically the same. Observe that for the two random models we obtain the exact asymptotic value of the probability, while bounds provided by Theorem 3.4 (when the size |M| of the set of bad events is maximum) are probably not sharp, although consistent with the values for the random models. We nally observe that for both models, when k= 1 we have Pr(XM= 1) = e−(2+o(1))µ , while if k→+∞ , then Pr(XM= 1) →e−µ since 2k1−(k−1) log k k−1= 1 + O1 k. This reects the idea that, when k is large, the number of bad events decreases and the model behaves as though they were independent. 40 3.4. Existence of rainbow perfect matchings 3.4 Existence of rainbow perfect matchings The aim of this section is to prove that with high probability there exists a rainbow perfect matching for any edge coloring of E(Kn,n) with s≥n colors. We only consider the Cu(n, s) model, but the results can be adapted to the Cr(n, s) model as well. The number of rainbow perfect matchings is counted by X=PMXM , which, according to Proposition 3.6, has expected value E(X) = E(X) = Pr(XM= 1)n! = exp −2k(k−1) log k−1 k+1+o(1)µn!. Recall that µ is the expected size of M , the set of pairs of non incident monochromatic edges. In order to have a rainbow perfect matching we just need to show that X6= 0 . Proof of Theorem 3.7 . To show that there exists some rainbow perfect matching w.h.p. we will use the second moment method, in particular Lemma 2.5. Observe that in our case X= 0 is equivalent to the nonexistence of rainbow perfect matchings. Therefore, we need to compute σ2(X) and show that it is asymptotically smaller than E(X)2 . Note that E(X2) = X (M,N) E(XMXN). Let M and N denote two perfect matchings of Kn,n with |M∩N|=z . Then E(XMXN) = Pr(XM= 1) Pr(XN= 1 |XM= 1) . If XM= 1 , we know that the edges of M∩N are rainbow. In the remaining n−z edges to color, we must avoid the z colors that appear in M∩N . Thus, Pr(XN= 1 |XM= 1) = n−1 Y i=z1−i s∼exp α(z)z2 2sPr(XM= 1) . (3.17) where 1≤α(z)≤2 , as can be derived from (3.16). Observe that the events XM= 1 and XN= 1 are positively correlated. For any perfect matching M and any integer z , such that 0≤z≤n , we claim that there exist at most n ze−1(n−z)! + 1 perfect matchings N such that |M∩N|=z . We can assume that M is given by the identity and N by a permutation π∈ Sn . There are n z ways of choosing which edges of M will be shared by N , i.e. the set I={i:π(i) = i} . In order that π corresponds to a matching N with exactly z common edges with M , its restriction to [n]\ I must be a derangement. It is well known that the proportion of derangements among all the permutations of length n−z is n−z X i=0 (−1)i i!≤e−1+1 (n−z)! . Therefore there are at most e−1(n−z)! + 1 ways to complete the perfect matching concluding our claim. Hence, E(X2) = n! n X z=0 n ze−1(n−z)! + 1Pr(XM= 1) Pr(XN= 1 |XM= 1). Chapter 3. Rainbow Perfect Matchings in Complete Bipartite Graphs 41 Since σ2(X) = E(X2)−E(X)2 , σ2(X) E(X)2=n!Pn z=0 n ze−1(n−z)! + 1Pr(XM= 1) Pr(XN= 1 |XM= 1) (n! Pr(XM= 1))2−1 =e−1 n X z=0 1 z!1 + e (n−z)!Pr(XN= 1 |XM= 1) Pr(XM= 1) −1. By the sake of simplicity, let us dene f(s) = n X z=0 1 z!1 + e (n−z)!Pr(XN= 1 |XM= 1) Pr(XM= 1) . Then, using (3.17) f(s)≤ n X z=0 1 z!1 + e (n−z)!exp α(z)z2 2s ≤∞ X z=0 1 z!exp α(z)z2 2s+e n! n X z=0 n zexp α(z)z2 2s =∞ X z=0 1 z! ∞ X t=0 1 t!α(z)z2 2st +e n! n X z=0 n z∞ X t=0 1 t!α(z)z2 2st =∞ X t=0 ats−t, where at=1 2tt!P∞ z=0 (α(z)z2)t z!+e n!Pn z=0 n z(α(z)z2)t . Observe that a0=e1 + 2n n! . Since s≤n2 , f(s)≤e+Os−1. Observe that s≥n , otherwise, Pr(XM= 1) = 0 in the Equation (3.14). Hence, σ2(X) E(X)2=e−1f(s)−1 = Os−1→0. This concludes the proof. Corollary 3.12. For any ε > 0 , an equitable edgecoloring of Kn,n with s colors, s≥n , contains more than (1 −ε)c(k)nn! rainbow perfect matchings with probability at least 1−O(ε−2s−1) . Proof . It follows from the proof of Theorem 3.7 that Pr(X > (1 −ε)E(X)) ≤σ2(X) ε2E(X)2= Oε−2s−1→0 . 3.5 Concluding remarks and open questions 1 Theorem 3.4 provides upper and lower bounds for the number of rainbow perfect matchings of a given edgecoloring of Kn,n such that the number of occurrences of each color is at most n/k and 42 3.5. Concluding remarks and open questions k≥13.66 . It is probably not true that each such edgecoloring contains e−(1+o(1))c(k)µn! rainbow perfect matchings, where c(k) is dened in Proposition 3.6. However, it would be interesting to see how tight are these upper and lower bounds c1(k) and c2(k) provided in Theorem 3.4 by showing extremal examples. 2 One interesting question is how far can k be pushed down in order to still have an exponentially fraction of rainbow perfect matchings. Question 3.13. Which is the minimum value k0>1 such that any edgecoloring of Kn,n where any color appears at most n/k0 times, has at least cnn! , for some c > 0 . Determining the smallest value of k with this property may shed some additional light on the open conjectures on latin transversals. Corollary 3.12 shows that almost all equitable edgecolorings with n colors contain an exponential fraction of perfect matchings that are rainbow. In the same spirit, Wanless [126, Section 3] denes the function f(n) to be the minimum number of latin transversals among all the latin squares of order n (case k= 1 ). Notice that f(2n)=0 and Ryser's conjecture states that f(2n+ 1) >0 for any n≥0 . As far as we know, this function has not been studied yet. Recently, the constant 4e≈10.87 has been improved to 256/27 ≈9.48 by Bissacot et al. [20]. Their proof uses a Cluster version of the local lemma. Thus, it is possible that the same techniques we used in this chapter could be applied to extend our result up to a better constant. 3 When s=n , the proof of Theorem 3.7 shows that the probability that a random coloring in Cu(n, s) has no rainbow perfect matchings is Pr(Cu(n, s) has no rainbow perfect matching ) = On−1. (3.18) The proportion of Latin squares among the set of square matrices with n symbols is of the order of e−(1+o(1))2n2 , so that this estimation falls short to prove an asymptotic version of the original conjecture of Ryser. We have provided a probabilistic approach to the problem by showing that every equi n square admits a latin transversal with high probability. Even if there are some almost sure results on Latin squares (see e.g.[101, 32]), and some results on generating random latin squares [80, 103], to our knowledge there are no random models for latin squares, which could set the way to such an asymptotic version of the conjectures of Ryser or Brualdi on the existence of latin transversals in latin squares. 4 The following example shows how to construct exponentially many latin squares (in general edgecolorings of K2k,2k with 2k colors) which have no rainbow perfect matchings. Let k be odd. Choose two arbitrary colorings α1, α2 of Kk,k with colors {a1, ...ak} and two arbitrary colorings β1, β2 of Kk,k with colors {b1, ..., bk} . Let {A1∪A2, B1∪B2} be the stable sets of K=K2k,2k with |Ai|=|Bi|=k and use αi for the edges connecting Ai with Bi , i= 1,2 , and βi for the edges connecting Ai with Bj , i6=j . Suppose that the resulting edgecolored graph has a rainbow perfect matching M . Since M must use the k colors a1, . . . , ak , we may assume that it uses at least (k+ 1)/2 of these colors from the subgraph K[A1, B1] induced by A1∪B1 . But then each of the subgraphs K[A1, B2] and K[A2, B1] can only use (k−1)/2 colors b1, . . . , bk and some color bi can not be used in the perfect matching, contradicting that M is rainbow. Chapter 4. Bounds for identifying codes in terms of degree parameters 49 Theorem 4.6. Let G be a twinfree graph on n vertices having maximum degree ∆≥3 . Then, γ ID (G)≤n−nf(G)2 103∆ . Proof . Let F be the set of forced vertices of G , and V0=V(G)\F . Note that |V0|=nf(G) . By the denition of a forced vertex, any identifying code must contain all vertices of F . In this proof, we rst build a set S in a random manner by choosing vertices from V0 . Then we exhibit some bad congurations  if none of those occurs, the set C=F∪(V0\S) is an identifying code of G . Using the Weighted Local Lemma, we compute a lower bound on the (nonzero) probability that none of these bad events occurs. Finally, we use the Cherno bound to show that with nonzero probability, the size of S is also large enough for our purposes. This shows that such a good large set S exists, and it can be used to build an identifying code that has a suciently small size. Let p=p(∆) be a probability which will be determined later. We build the set S⊆V0 such that each vertex of V0 independently belongs to S with probability p . Therefore the random variable |S| follows a binomial distribution Bin( nf(G) , p ) and has expected value E(|S|) = pnf(G) . Let us now dene the set A of bad events of size N . These are of four types. An illustration of these events is given in Figure 4.2. • Type B j ( 2≤j≤2∆ −2 ): for each pair {u, v} of adjacent vertices, let Bj u,v be the event that |(N[u]⊕N[v])|=j and (N[u]⊕N[v]) ⊆S . • Type C j ( 3≤j≤2∆ ): for each pair {u, v} of vertices in V0 at distance two from each other, let Cj u,v be the event that |(N[u]⊕N[v])|=j and (N[u]⊕N[v]) ⊆S . • Type D: for each pair {u, v} of false twins in V0 , let Du,v be the event that (N[u]⊕N[v]) = {u, v} ⊆ S . • Type E j ( 2≤j≤∆+1 ): for each vertex u∈V0 , let Ej u be the event that |N[u]|=j and N[u]⊆S . For the sake of simplicity, we refer to the events of type Bj , Cj and Ej as events of type B , C and E respectively whenever the size of the symmetric dierence is not relevant. Events of type B1 u,v are not dened since then |N[u]⊕N[v]|= 1 and F belongs to the code, so they never happen. Observe that the events Cj u,v and Du,v are just dened over the pairs of vertices in V0 because if either u or v belongs to F , the event does not happen. If no event of type B occurs, all pairs of adjacent vertices are separated by V(G)\S . If no event of type C or D occurs, all pairs of vertices at distance 2 from each other are separated. If no event of type E occurs, V(G)\S is a dominating set of G . Thus by Observation 4.3, if no event of type B , C , D or E occurs, then V(G)\S is an identifying code of G . Let V(Ai) denote the set of vertices that must belong to set S so that Ai holds (see Figure 4.2, where the sets V(Ai) are the ones inside the dashed circles). We will say that a vertex v∈V(G) participates to Ai , if v∈V(Ai) . We dene the weight ti of each event Ai∈ A as |V(Ai)| . For 50 4.2. Upper bounds on the identifying code number u v ... ... ... (a) Event Bj u,v u v ... ... ... (b) Event Cj u,v u v ... (c) Event Du,v u ... (d) Event Ej u Figure 4.2: The bad events. The vertices in dashed circles belong to set S . j≥2 and for T∈ {Bj, Cj, D, Ej,} , let tT be the weight of an event of type T (for an event Ai∈ A of type T , ti=tT ). We have the following, tBj=j , tCj=j , tD= 2 , and tEj=j . Some vertex x can participate to at most ∆(∆ −1) events of type B : supposing x∈V(Bj u,v) and u is adjacent to x , there are at most ∆ ways to choose u , and at most ∆−1 ways to choose v among N(u)\ {x} . Observe that if x=u or x=v , then x /∈V(Bu,v) (see Figure 4.2(a)). Similarly x can participate to at most ∆2(∆−1) events of type C : for some event Cj u,v , there are at most ∆(∆ −1) possibilities if x=u or x=v and at most ∆(∆ −1)2 if u or v is a neighbour of x . Vertex x can participate to at most ∆−1 events Du,v since x can have at most ∆−1 false twins. Finally, a vertex x can participate to at most ∆+1 events of type E since if it participates to some event Ej u , then u∈N[x] . For each type T of events ( T∈ {Bj, Cj, D, Ej} ) and any vertex v∈V(G) , let us dene g(v, T) to be the number of events Ai of type T such that v∈V(Ai) . Hence, 2∆−2 X j=2 g(v, Bj)≤∆(∆ −1) , 2∆ X j=3 g(v, Cj)≤∆2(∆ −1) , g(v, D)≤∆−1, and ∆+1 X j=2 g(v, Ej)≤∆+1. (4.1) Let us call A ic the event that no event of A occurs. Using the Weighted Local Lemma, we want to show that Pr(A ic )>0 . First of all we need to set a dependency graph H for the set of events A . Recall that V(H)=[N] . For any i, j ∈[N] , we will have ij ∈E(H) if and only V(Ai)∩V(Aj) = ∅ . Observe that for any event Ai and any set T⊆ {j:i6∼ j} , we have Pr(Ai| ∩j∈TAj) = Pr(Ai) , since the vertices are included in S with independent probabilities. This means that Ai is mutually independent from the set of all events Aj for which V(Ai)∩V(Aj) = ∅ . Thus, our graph H matches Denition 2.6 and is a dependency graph for A . Chapter 4. Bounds for identifying codes in terms of degree parameters 51 In order to apply the Weighted Local Lemma (Lemma 2.13), the following conditions must hold for each event Ai∈ A , X ij∈E(H) (2p)tj≤ti 2. The latter conditions are implied by the following ones (for each event Ai∈ A ), 2∆−2 X j=2 X v∈V(Ai) g(v, Bj)(2p)tBj+ 2∆ X j=3 X v∈V(Ai) g(v, Cj)(2p)tCj +X v∈V(Ai) g(v, D)(2p)tD+ ∆+1 X j=2 X v∈V(Ai) g(v, Ej)(2p)tEj≤ti 2. Which are implied by ti·max v∈V(Ai)   2∆−2 X j=2 g(v, Bj)(2p)tBj   +ti·max v∈V(Ai)   2∆ X j=3 g(v, Cj)(2p)tCj   +ti·max v∈V(Ai)g(v, D)(2p)tD+ti·max v∈V(Ai)   ∆+1 X j=2 g(v, Ej)(2p)tEj  ≤ti 2. Using the bounds of Inequalities (4.1) and noting that for p≤1/4 and any j , (2p)tBj≤(2p)2 , (2p)tCj≤(2p)3 and (2p)tEj≤(2p)2 , for any event Ai this equation is implied by (∆+1)(2p)2+∆(∆−1)(2p)2+∆2(∆−1)(2p)3+(∆−1)(2p)2= 4∆2p2+8∆3p3+4∆p2−8∆2p3≤1 2. (4.2) Hence, we x p=1 k∆ where k is a constant to be determined later. Equation (4.2) holds for k≥3.68 for all ∆≥3 . In fact, in the following steps of the proof, we will assume that k≥30 , and so Equation (4.2) will be satised for any ∆≥3 . Since p≤1 4 and Pr(Ai)≤pti by the denition of ti and the choice of S , the Weighted Local Lemma can be applied. Let NT be the number of events of type T , where T∈Bj, Cj, D, Ej, . By Lemma 2.13 we have Pr(A ic )≥ 2∆−2 Y j=2 NBj Y i=1 (1 −(2p)tBj) 2∆ Y j=3 NCj Y i=1 (1 −(2p)tCj) ND Y i=1 (1 −(2p)tD) ∆+1 Y j=2 NEj Y i=1 (1 −(2p)tEj). Note that P2∆−2 j=2 NBj≤n∆ 2 since there is exactly one event type Bj u,v for each edge uv ∈E(G) and at most n∆ 2 edges in G . We also have that P2∆ j=3 NCj is at most the number of pairs of vertices in V0 at distance 2 from each other. This is also at most the number of paths of length 2 with both endpoints in V0 , which is upper-bounded by nf(G)∆(∆−1) 2 . Moreover, ND is the number of pairs of false twins in V0 , which is at most nf(G)∆−1 2 by Proposition 4.5. Finally, P∆+1 j=2 NEj=nf(G) since by denition there exists exactly one event Ej u for each vertex of u∈V0 . Hence, we have Pr(A ic )≥(1 −(2p)2)n∆ 2(1 −(2p)3) nf(G)∆(∆−1) 2(1 −(2p)2) nf(G)(∆−1) 2(1 −(2p)2)nf(G). 52 4.2. Upper bounds on the identifying code number Note that in Lemma 2.13, since p≤1 4 and (1 −x)≥e−(2 log 2)x in x∈[0,1/2] , we have Pr N \ i=1 Ai!≥exp −(2 log 2) N X i=1 (2p)ti!. (4.3) Since p=1 k∆ , we obtain Pr(A ic )≥exp −(2 log 2)(2p)2∆ 2+f(G)∆(∆ −1)2p 2+f(G)(∆ −1) 2+f(G)n ≥exp −4 log 2 k2∆1 + 2f(G) k+f(G) + 2f(G) ∆n. Since f(G)≤1 and it is assumed that k≥30 , one can check that for any ∆≥3 , Pr(A ic )≥exp −164 log 2 15k2∆n. Note that this bound could be strengthened by assuming ∆ to be large enough. Indeed, here the term 2f(G) ∆ can be as high as 2 3 when ∆=3 and f(G) = 1 , but can be chosen to be as low as desired by assuming ∆ to be larger. However we aim to give a bound for any ∆≥3 , hence we use the weaker bound presented here. The Weighted Local Lemma shows that the set S has the desired properties with probability Pr(A ic )>0 , implying that such a set exists. Note that we have no guarantee on the size of S . In fact, if S=∅ then V(G)\S=V(G) is always an identifying code. Therefore we need to estimate the probability that |S| is far below its expected size. In order to do this, we use the Cherno bound of Theorem 2.3 by putting a=nf(G) c∆ where c is a constant to be determined. Let A big be the event that |S|−np > −nf(G) c∆ . We obtain Pr(A big )≤exp   −nf(G) c∆2 2pnf(G)   = exp −kf(G) 2c2∆n. Now we have Pr(A ic and A big )=1−Pr(A ic or A big ) ≥1−Pr(A ic )−Pr(A big ) = 1 −(1 −Pr(A ic )) −Pr(A big ) = Pr(A ic )−Pr(A big ) ≥exp −164 log 2 15k2∆n−exp −kf(G) 2c2∆n. Thus, Pr(A ic and A big )>0 if c < q15 328 log 2 ·k3/2f(G)1/2 . We (arbitrarily) set c=k3/2f(G)1/2 √22 log 2 in order to fulll this condition. Chapter 4. Bounds for identifying codes in terms of degree parameters 53 Now we have to check that A big implies that S is still large enough. |S| ≥ E(|S|)−nf(G) c∆ =nf(G) k∆−nf(G) c∆ =1 k−√22 log 2 k3/2f(G)1/2nf(G) ∆. (4.4) Since |S| must be positive, from Equation (4.4) we need k3/2f(G)1/2>√22 log 2 k , which leads to k=a0 f(G) for a0>22 log 2 . Using all our previous assumptions, by derivating the expression of |S| , one can check that |S| is maximized when a0=99 log 2 2 . Hence we set k=99 log 2 2f(G) . Remark that under this condition and since f(G)≤1 , we have k≥34 and our assumption following Equation (4.2) that k≥30 , is fullled. Now, with a0=99 log 2 2 , we can see that |S| ≥ 1 k−1 cnf(G) ∆=a1/2 0−√22 log 2 a3/2 0 f(G)2 ∆n=2 297 log 2 f(G)2 ∆n≥f(G)2 103∆ n . Hence nally the identifying code C=V\S has size |C| ≤ n−nf(G)2 103∆ . Note that for regular graphs, f(G)=1 , since the existence of a forced vertex implies the existence of two vertices with distinct degrees. We obtain the following result. Corollary 4.7 (Graphs with constant proportion of nonforced vertices) . Let G be a twinfree graph on n vertices with maximum degree ∆≥3 and f(G) = 1 α for some constant α≥1 . Then, γ ID (G)≤n−n 103α2∆. In particular if G is d regular, γ ID (G)≤n−n 103d. The next proposition will be proved in the next subsection. Proposition 4.8. Let G be a graph on n vertices and of maximum degree ∆ . Then, f(G)≥1 ∆+1 . Using it, we obtain the following general result. Corollary 4.9 (General case) . Let G be a twinfree graph on n vertices having maximum degree ∆≥3 . Then, γ ID (G)≤n−n 103∆(∆ + 1)2=n−n O(∆3). 54 4.2. Upper bounds on the identifying code number The next proposition will be proved in the next subsection as well. Proposition 4.10. Let G be a graph having no k -clique. Then, there exists a constant γ(k) depending only on k , such that f(G)≥1 γ(k). This leads to the following extension of Corollary 4.7, where c(k)≤103γ(k)2 . Corollary 4.11 (Graphs with bounded clique number) . There exists an integer ∆0 such that for each twinfree graph G on n vertices having maximum degree ∆≥∆0 and clique number smaller than k , we have γ ID (G)≤n−n c(k)∆ , for some constant c(k) depending only on k . In particular this applies to trianglefree graphs, planar graphs, or more generally, graphs of bounded genus. We remark here that the previous corollaries support Conjecture 4.2. They also lead us to think that the diculty of the problem lies in studying the set of forced vertices. 4.2.3 Bounding the number of nonforced vertices Here, we prove the lower bounds for function f(G) of the statement of Theorem 4.6. The following lemma was rst proved in [16], and a proof can be found in [59] (as [16] is not accessible). Lemma 4.12 ([16]) . If G is a nite twinfree graph without isolated vertices, then for every vertex u of G , there is a vertex v∈N[u] such that V(G)\{v} is an identifying code of G . Let us now prove Proposition 4.8. Proof of Proposition 4.8 . Observe that a vertex v of G is not forced only if V(G)\ {v} is an identifying code of G . Hence, by Lemma 4.12, the set S of nonforced vertices is a dominating set of G , and thus |S| ≥ n ∆+1 . Note that Proposition 4.8 is tight. Indeed, consider the graph Ak on 2k vertices dened in [59] as follows: V(Ak) = {x1, . . . , x2k} and E(Ak) = {xixj,|i−j| ≤ k−1} . Ak can be seen as the (k−1) th power of the path P2k . Construct now the graph Bk by adding a universal vertex x (i.e. x is adjacent to all vertices of Ak ) in the graph Ak . One can check that all vertices from Bk but x are forced. This graph has n= 2k+ 1 vertices, maximum degree 2k and exactly 1 = n ∆+1 nonforced vertex. Taking all forced vertices gives a minimum identifying code of this graph. However, note that since for a xed even value of ∆ , we know only one such graph, it is not enough to give a counterexample to Conjecture 4.2. Indeed in this case the size of the code is n−1 = n−n ∆+1 =n−n ∆+1 n−1=n−n ∆+ 1 . Chapter 4. Bounds for identifying codes in terms of degree parameters 55 x1x2x3x4 x5 x6 x7 x8 x Figure 4.3: The graph B4 . Observe that the graph Bk contains two cliques of k vertices. In fact, we can improve the bound of Proposition 4.8 for graphs having no large cliques. Let us rst introduce an auxiliary structure that will be needed in order to prove this result. Let G be a twinfree graph. We dene a partial order  over the set of vertices of G such that uv if N[u]⊆N[v] . We construct an oriented graph H(G) on V(G) as a subgraph of the Hasse diagram of poset (V(G),) . The arc set of H(G) is the set of all arcs −→ uv where there exists some vertex x such that N[v] = N[u]∪{x} . Then x is uv forced, and we note x=f(−→ uv) . For a vertex v of V(G) , we dene the set F(v) as the union of v itself and the set of all predecessors and successors of v in H(G) . Observe that H(G) has no directed cycle since it represents a partial order, and thus predecessors and successors are welldened. Lemma 4.13. Let G be a graph having no k -clique. Then for each vertex u , |F(u)| ≤ β(k) , where β(k) is a function depending only on k . Proof . First of all, we prove that the maximum in-degree of H(G) is at most 2k−3 , and its out-degree is at most k−2 . Let u be a vertex of G . Suppose u has 2k−2 in-neighbours in H(G) . Since for each in-neighbour v of u , |N[u]⊕N[v]|= 1 in G , each of them is nonadjacent in G to at most one of the other in-neighbours (in the worst case the in-neighbours of u induce in G a clique of 2k−2 vertices minus the edges of a perfect matching). Hence they induce a clique of size at least k−1 in G . Together with vertex u , they form a k -clique in G , a contradiction. Now suppose u has k−1 out-neighbours in H(G) . Since for each out-neighbour v of u in H(G) , N[u]⊆N[v] in G , u and its out-neighbours form a k -clique in G , a contradiction. Now, consider the subgraph of H(G) induced by F(u) . We claim that the longest directed chain in this subgraph has at most k−1 vertices. Indeed, all the vertices of such a chain are pairwise adjacent in G . Since G is assumed not to have any k -cliques, there are at most k−1 vertices in a directed chain. Finally, we obtain that F(u) has size at most β(k) = Pk−2 i=0 (2k−3)i and the claim of the lemma follows. We now need to prove a few additional claims regarding the structure of H(G) . In the following claims, we suppose that G is a twinfree graph. 56 4.2. Upper bounds on the identifying code number Claim 4.14. Let s be a forced vertex in G with s=f(−→ uv) for some vertices u and v . If t is an in-neighbour of s in H(G) , then v=f(−→ ts) . Moreover, if v is forced with v=f(−→ xy) , then necessarily y=s . Proof . For the rst implication, suppose s has an in-neighbour t in H(G) . An illustration is provided in Figure 4.4. Since u6∼ s , then u6∼ t . Moreover, v6∼ t since s=f(−→ uv) . Since s∼v the claim follows. For the other implication, suppose there exist two vertices x, y such that v=f(−→ xy) . Hence y∼v but x6∼ v . Therefore u6∼ x (otherwise v would be adjacent to x too) and hence u6∼ y . Now the only vertex adjacent to v but not to u is s , so y=s . ut s=f(−→ uv) v=f(−→ ts) Figure 4.4: The situation of Claim 4.14. Arcs belong to H(G) . Full thin edges belong to G only, dashed edges are nonedges in G . Claim 4.15. Let s be a forced vertex in G with s=f(−→ uv) for some vertices u and v . Then s has at most one in-neighbour in H(G) . Proof . Suppose s has two distinct in-neighbours t and t0 in H(G) (see Figure 4.5 for an illustration). By Claim 4.14, v is both ts forced and t0s forced. But then N[t] = N[s]\{v}=N[t0] . Then t and t0 are twins, a contradiction since G is twinfree. utt0 s=f(−→ uv) v Figure 4.5: The situation of Claim 4.15. Arcs belong to H(G) . Full thin edges belong to G only, dashed edges are nonedges in G . Claim 4.16. Let s be a forced vertex in G with s=f(−→ uv) , and let t be a forced in-neighbour of s in H(G) with t=f(−→ xy) for some vertices u, v, x, y . Then x=v . Proof . Since t∼y , then s∼y too. But since t=f(−→ xy) , x∼s and x6∼ t . Now by Claim 4.14, v=f(−→ ts) , that is, v is the unique vertex such that v is adjacent to s , but not to t . Therefore x=v . We now obtain the following lemma using the previous claims. Lemma 4.17. Let s be a nonisolated sink in H(G) which is forced in G with s=f(−→ uv) for some vertices u and v . Then either s has a nonforced predecessor t in H(G) such that F(s)⊆F(t) , or there exists a nonforced vertex w(s) such that F(s)⊆NG[w(s)] . Moreover, if there are ` additional sinks {s1, . . . , s`} which are all nonisolated in H(G) and such that w(s) = w(s1) = . . . =w(s`) , then there exists a set of `+ 1 distinct vertices inducing a clique together with w(s) . Chapter 4. Bounds for identifying codes in terms of degree parameters 57 Proof . First of all, recall that H(G) has no directed circuits. Suppose s has a nonforced predecessor in H(G) and let t be one such predecessor having the shortest distance to s in H(G) . By Claim 4.15, predecessors of s are either successors or predecessors of t , and there is a directed path from t to s in H(G) . Hence F(s)⊆F(t) , which proves the rst part of the statement. Now suppose all predecessors of s=f(−→ uv) are forced. By Claim 4.15, s and its predecessors form a directed path {t0, . . . , tm, s} in H(G) (for an illustration, see Figure 4.6(a)). Note that by Claim 4.14, we have v=f(−−→ tms) . By our assumption we know that tm is forced, say tm= f(−−→ xvm) for some vertices x and vm . But now by Claim 4.16, x=v and tm=f(−−→ vvm) . Now, repeating these arguments for each other predecessor of s shows that there is a directed path {u, v, vm, . . . , v0} with tm=f(−−→ vvm) and for all i , 0≤i≤m−1 , ti=f(−−−→ vi+1vi) . In particular, t0=f(−−→ v1v0) . Observe also that for all i≥1 , vi=f(−−−→ ti−1ti) . By applying Claim 4.16 on vertices v1, v0 and t0 , if v0 is forced then t0 has an in-neighbour in H(G) , a contradiction  hence v0 is nonforced. Also note that, since v0∼t0 , then v0 is adjacent to all successors of t0 in H(G) , that is, to all elements of F(s) . Therefore, putting w(s) = v0 , we obtain the second part of the statement. For the last part, suppose there exists a set of ` additional forced sinks {s1, . . . , s`} which are nonisolated in H(G) and such that all their predecessors in H(G) are forced with w(si) = v0 for 1≤i≤` (for an illustration, see Figure 4.6(b)). For each such sink si , by the previous paragraph, the vertices of F(si) induce a directed path {ti 0, . . . , ti mi, si} in H(G) . Moreover we know that there is a vertex xi such that ti 0 is xiv0 forced. We claim that the set of vertices X={x1, . . . , x`} together with v0 and v1 , form a clique in G of `+ 2 vertices. We rst claim that for all i, j in {1, . . . , `} , xi6=tj 0 . If i=j , this is clear by our assumptions. Otherwise, suppose by contradiction, that xi=tj 0 for some i6=j in {1, . . . , `} . Then we claim that xj=ti 0 . Indeed, by the previous part of the proof, we know that f(−−→ xjv0) = tj 0=xi  hence xj6∼ xi . But since −−→ xiv0 is an arc in H(G) , we must have f(−−→ xiv0) = xj . Again, we know that f(−−→ xiv0) = ti 0 , hence xj=ti 0 . Let ti 1 denote the successor of ti 0 in the directed path from ti 0 to si in H(G) . We know from the previous part of the proof that f(−−→ ti 0ti 1) = xi=tj 0 . However since ti 0=xj we also know that f(−−→ ti 0v0) = xi . This implies that NG[v0] = NG[ti 1] , a contradiction since these two vertices are distinct and G is twinfree. Now, observe that the vertices of X must all be pairwise adjacent. All vertices of X are adjacent to v0 , and for each xi , N[v0] = N[xi]∪{ti 0} , hence xi is adjacent to all neighbours of v0 except ti 0 . But by the previous paragraph, we know that ti 06=xj for all j∈ {1, . . . , `} , hence xi is adjacent to all xj6=xi , j∈ {1, . . . , `} . For the same reason, each xi is adjacent to v1 . Hence, the vertices of X form a clique together with v0 and v1 . Finally, let us show that all the vertices of X are distinct: by contradiction, suppose that xi=xj for some i6=j , 1≤i, j ≤` . Since ti 0 is xiv0 forced and tj 0 is xjv0 forced, we have ti 0=tj 0 . Since si and sj are distinct, this means that si and sj have one predecessor in common. Hence their common predecessor which is nearest to si and sj , say t , has two out-neighbours. Let ti (respectively tj ) be the out-neighbour of t which is a predecessor of si (respectively sj )  see Figure 4.6(c) for an illustration. We know that there are two vertices yi, yj such that yi=f(−→ tti) and yj=f(−→ ttj) . First note that yi and yj are distinct: otherwise, we would have N[ti] = N[t]∪{yi}=N[t]∪{yj}=N[tj] and then ti, tj would be twins in G . Observe that since t6∼ yi and yi6=f(−→ ttj) , we have tj6∼ yi . We know that t is forced, in fact by the rst part of this proof, we also know that t=f(−−→ yizi) for some vertex zi . Hence zi∼t , and since N[t]⊆N[tj] , 58 4.2. Upper bounds on the identifying code number zi∼tj . But since tj6=f(−−→ yizi) , tj∼yi , a contradiction. Hence xi and xj are distinct, which completes the proof. v0=w(s) v1=f(−−→ t0t1) vm=f(−−−−→ tm−1tm) v=f(−−→ tms) u t0=f(−−→ v1v0) t1=f(−−→ v2v1) tm=f(−−→ vvm) s=f(−→ uv) (a) Vertex s and all its predecessors in H(G) are forced. v0 v1 x1 t1 0=f(−−→ x1v0) t1 m1 s1 x` t` 0=f(−−→ x`v0) t` m` s` ··· (b) Vertices v0, v1, x1,...,x` induce a clique in G . t=f(−−→ yizi) ti 0=tj 0 xi=xj ti yi=f(−→ tti) zi si tjyj=f(−→ ttj) sj (c) If xi=xj , the dotted edge yitj is both an edge and a nonedge of G . Figure 4.6: Three situations in the proof of Lemma 4.17. Arcs belong to H(G) . Full thin edges belong to G only, dashed edges are nonedges in G . Finally, let us recall and prove Proposition 4.10. Proposition. Let G be a graph having no k -clique. Then there exists a constant γ(k) depending only on k , such that f(G)≥1 γ(k) . Proof . To prove the result, we use H(G) to construct a set X={x1, . . . , x`} of nonforced vertices such that S` i=1 A(xi) = V(G) , where A(xi) is a set of at most γ(k) vertices. Then we have `≥n γ(k) vertices in X and the claim of the proposition follows. We now describe a procedure to build set X while considering each nonisolated sink of H(G) . We denote by s the currently considered sink. Case 1: Sink s is nonforced. Then we set A(s) to be F(s) together with all the vertices which Chapter 4. Bounds for identifying codes in terms of degree parameters 65 For the sake of contradiction, let m≤log d−clog log d dn for some c > 2 . Then, Pr (∩y∈YAy)≤exp −1−log d−clog log d dnexp (−log d−clog log d 1−2log d−clog log d d)! = exp −(1 + od(1)) nexp −log d−clog log d 1 + od(1)  = (1 + od(1))e−(log d)c dn. Note that if no set of size m dominates Y , neither will do a smaller one. So we have to look just at the sets of size m . The number of these sets can be bounded by n m≤nm m!≤en mm =de log d−clog log dlog d−clog log d dn = (1 + od(1)) de log dlog d−clog log d dn , where we have used m!≥m em . Let ADS be the event that G has a dominating set of size m . Applying the union bound, we have Pr(ADS)≤(1 + od(1)) de log dlog d−clog log d dn e−(log d)c dn = (1 + od(1)) exp log d−clog log d d(log d+ 1 −log log d)n−(log d)c dn = (1 + od(1)) exp (log d)2 d−(log d)c d+od(log d)2 dn−→ 0, since c > 2 . This shows that w.h.p. no set of size less than log d−2 log log d dn can dominate the whole graph and completes the proof. Since any identifying code is a dominating set, we obtain the following immediate corollary. Corollary 4.22. Let G∈G(n, d) , then, with high probability, γ ID (G)≥log d−2 log log d dn . Plugging together Theorems 4.20 and 4.21, we can provide the following result. Corollary 4.23. Let G∈G(n, d) , then, with high probability, log d−2 log log d dn≤γ ID (G)≤log d+ log log d+Od(1) dn . 66 4.5. Extremal constructions 4.5 Extremal constructions This section gathers some constructions which show the tightness of some of our upper bounds. Some of these constructions can be found in [58]. Construction 4.24. Given any dH regular multigraph H (without loops) on nH vertices, let C1(H) be the graph on n=nH(dH+ 1) and maximum degree ∆ = dH+ 1 constructed as follows. 1. Replace each vertex v of H by a clique K(v) of dH+ 1 vertices 2. For each vertex v of H , let N(v) = {v1, . . . , vdH} and K(v) = {k0(v), . . . , kdH(v)} . For each ki(v) but one ( 1≤i≤dH ), connect it with an edge in C1(H) , to a unique vertex of K(vi) , denoted f(ki(v)) . One can see that the graphs C1(H) given by Construction 4.24 are twinfree. Moreover, for each vertex v of H and for each 1≤i≤dH , note that f(ki(v)) is k0(v)ki(v) forced. Therefore C1(H) has dHnH=n−n ∆ forced vertices. In fact these forced vertices form an identifying code, therefore γ ID (C1(H)) = n−n ∆ . An example of this construction is given in Figure 4.7, where H is the hypercube of dimension 3, H3 , and the black vertices are those which belong to a minimum identifying code of C1(H3) . g e h b a d c f K(b) K(h) k0(b) k1(b) =f(k3(h)) k2(b) k3(b) k0(h) k2(h) k1(h) k3(h) =f(k1(b)) Figure 4.7: The graphs H3 and C1(H3) . The following construction is very similar, but yields regular graphs. Construction 4.25. [58] Given any dH regular multigraph H (without loops) on nH vertices, let C2(H) be the d regular graph on n=nHdH vertices (where d=dH ) constructed as follows. 1. Replace each vertex v of H by a clique K(v) of dH vertices. 2. For each vertex v of H , let N(v) = {v1, . . . , vdH} and K(v) = {k1(v), . . . , kdH(v)} . For each ki(v) ( 1≤i≤dH ), connect it with an edge in C2(H) , to a unique vertex of K(vi) , denoted f(ki(v)) . Chapter 4. Bounds for identifying codes in terms of degree parameters 67 Note that for some vertex v of H , in order to separate each pair of vertices ki(v), kj(v) of K(v) in C2(H) , either f(ki(v)) or f(kj(v)) must belong to any identifying code. Repeating this argument for each pair shows that at least d−1 such vertices are needed in the code. Since for any two cliques K(u) and K(v) , the set of these neighbours are disjoint, this shows that at least nH(d−1) vertices are needed in an identifying code of C2(H) . In fact it is easy to construct an identifying code of this size. This shows that despite the fact that C2(H) has no forced vertices, γ ID (C2(H)) = n−n d . An example of this construction is given in Figure 4.8, where H is the complete graph K5 , and the black vertices form a minimum identifying code of C2(K5) . Construction 4.24 and 4.25 are close to Sierpi«ski graphs, which were dened in [89]. Recently in [72], it has been showed that Sierpi«ski graphs are also extremal with respect to Conjecture 4.2, i.e. for any Sierpi«ski graph G on n vertices with maximum degree ∆ , γ ID (G) = n−n ∆ . a b c de K(a) K(e) k1(a) k2(a) k3(a) k4(a) =f(k1(e)) k2(e) k3(e) k4(e)k1(e) = f(k4(a)) Figure 4.8: The graphs K5 and C2(K5) . Construction 4.26. [58] Given an even number 2k and an integer d≥3 , we construct a twinfree d regular trianglefree graph C3(2k, d) on n= 2kd vertices as follows. 1. Let {c0, . . . , c2k−1} be a set of 2k vertices and add the edges of the perfect matching {c1c2, . . . , c2k−3c2k−2, c2k−1c0} . 2. For each even i ( 0≤i≤2k−2 ), build a copy K(i) of the complete bipartite graph Kd−1,d−1 . Join vertex ci to all vertices of one part of the bipartition of K(i) , and join vertex ci+1 to all other vertices of K(i) . Consider an identifying code of C3(2k, d) . Note that in each copy K(i) of Kd−1,d−1 , at least 2d−4 vertices belong to the code in order to separate the vertices being in the same part of the bipartition of K(i) . Now if exactly 2d−4 vertices of K(i) belong to the code, in order to separate the two remaining vertices, either ci or ci+1 belongs to the code. Hence for each odd i , at most three vertices from {ci, ci+1} ∪ V(K(i)) do not belong to a code of C3(2k, d) . On the other hand, taking all vertices ci such that i is even together with d−2 vertices of each part of the bipartition of each copy of Kd−1,d−1 yields an identifying code of this size. Hence γ ID (C3(2k, d)) = k+ 2k(d−2) = n−n 2d/3 . An example of this construction is given in Figure 4.9, where 2k= 8 , d= 3 , and the black vertices form a minimum identifying code of C3(8,3) . 68 4.6. Concluding remarks and open questions c0c1c2c3c4c5c6c7 K(0) Figure 4.9: The graph C3(8,3) . 4.6 Concluding remarks and open questions 1. Motivated by the graph Bk (see Figure 4.3), we ask the following question. Question 4.27. Does there exist a value of ∆ and an innite family of graphs with maximum degree ∆ having exactly n ∆+1 nonforced vertices? Answering this question in a positive way would provide a counterexample to Conjecture 4.2. Note that for the similar question where we replace ∆ + 1 by ∆ , the answer is positive by Construction 4.24 of Section 4.5. For any ∆ , this construction provides arbitrarily large graphs having exactly n ∆ nonforced vertices. 2. The main question that still needs to be answered is whether Conjecture 4.2 is true for every graph with maximum degree ∆ . We have showed that the conjecture is asymptotically true for every graph with a constant proportion of nonforced vertices (Corollary 4.7), which includes regular graphs or graphs with no clique of constant order as a minor (Corollary 4.11). An easier question is the following weaker version of Conjecture 4.2. Question 4.28. Is it true that for any nontrivial connected twinfree graph G of maximum degree ∆ , we have γ ID (G)≤n−n O(∆) ? Recall that we have examples with a large number of forced vertices. Thus, it is not true that any graph has a constant proportion of nonforced vertices. Thus, Theorem 4.6 does not suce to answer the previous question. Nonetheless, we believe that the same probabilistic approach could give a better result by understanding which is the role of the forced vertices in the proof of Theorem 4.6. In our proof, we do not use the set of forced vertices to identify the rest of the vertices. It is obvious that any identifying code will contain this set of vertices, but they also help to separate the other pairs. For instance, in graph the Bk (see Figure 4.3), the set of forced vertices V(Ak) is already an identifying code. 3. Consider a k coloring of G , χ:V(G)→[k] . For any set S⊆V(G) , we denote by χ(S) = Chapter 4. Bounds for identifying codes in terms of degree parameters 69 ∪v∈Sχ(v)⊆[k] , the set of colors in S . Then, χ is locally identifying , if it is proper and for any edge uv ∈E(G) , with N[u]6=N[v] , we have χ(N[u]) 6=χ(N[v]) . The locally identifying chromatic number of G , χlid(G) , is the minimum integer k such that G admits a locally identifying coloring. It was conjectured in [55] that for any graph G with maximum degree ∆ , χlid(G) = O(∆2). (4.7) In the same paper, the authors show that for such graphs, χlid(G) = O(∆3) . Using the technique displayed in the proof of Theorem 4.6, one can show that for any graph G with maximum degree ∆ , (4.7) holds. In [60], we provide a constructive proof to show that χlid(G)≤2∆2−3∆ + 3 . This bound cannot be improved much. Using the projective plane one can construct a graph H with maximum degree ∆ and χlid(H) = ∆2−∆+1 . 4. Note that Theorem 4.19 cannot be extended much in the sense that if we drop the condition on girth 5 , we know arbitrarily large d regular trianglefree graphs having large minimum identifying code number. For instance, Construction 4.26 of Section 4.5 provides a graph G which satises γ ID (G) = n−n d . Similarly, we cannot drop the minimum degree condition. Indeed it is known that any (∆ −1) -ary complete tree T∆,h of height h , which is of maximum degree ∆ , minimum degree 1 and has innite girth, also has a large identifying code number (i.e. γ ID (T∆,h) = n−n ∆−1+o∆(1) [17]). CHAPTER 5 Large spanning subgraphs admitting small identifying codes 5.1 Introduction Consider any graph parameter that is not monotone with respect to graph inclusion. Given a graph G , a natural problem in this context is to study the minimum value of this parameter over all spanning subgraphs of G . In particular, how many edge deletions are sucient in order to obtain from G a graph with nearoptimal value of the parameter? Herein, we use random methods to study this question with respect to the identifying code number of a graph, a well studied nonmonotone parameter. An identifying code of graph G is a set C of vertices which is a dominating set, and such that the closed neighborhood within C of each vertex v uniquely determines v . The basic notation on graph theory and a formal denition of identifying code can be found in Section 4.1 of the previous chapter. Recall that for every twinfree graph G on n vertices having at least one edge, we have dlog2(n+ 1)e ≤ γ ID (G)≤n−1. In view of the above lower bound, we say that an identifying code C of G is asymptotically optimal if |C| =O(log n). In this chapter we will deal with graphs that have a large identifying code number or that do not admit an identifying code, this is, they contain twins. Our goal will consist in slightly modifying such graphs in order to decrease their identifying code number and obtain an asymptotically optimal identifying code, unless its domination number prevents us from doing so. One of the reasons for a graph to have a large identifying code number is that it has a large domination number (this one being a monotone parameter under edge deletion). For instance, we need a linear size set in order to dominate all the vertices of a bounded degree graph. When this is the case, we cannot expect to decrease much the size of a minimum identifying code by deleting edges from G , as the deletion of edges cannot decrease the domination number. 71 72 5.1. Introduction However, there are many graphs with small domination number where the identifying code number is very large [59, 62]. Typically, this phenomenon appears in graphs having a specic rigid structure. Supporting this intuition, Frieze et al. [66] have showed that the random graph G(n, p) with p∈(0,1) , admits an asymptotically optimal identifying code. In particular, they prove in [66] that γ ID (G(n, p)) = (1 + o(1)) 2 log n log (1/q), where q=p2+ (1 −p)2 . This suggests that the lack of structure in dense graphs implies the existence of a small identifying code. By selecting at random a small set of edges that can be deleted to add some randomness in the graph, we obtain the following result. Theorem 5.1. For every graph G on n vertices ( n large enough) with maximum degree ∆ = ω(1) and minimum degree d≥66 log ∆ , there exists a subset of edges F⊂E(G) of size |F|=O(nlog ∆) , such that γ ID (G\F) = Onlog ∆ d. Observe that when d= Θ(n) , this result is asymptotically equal to the one in [66]. In order to show Theorem 5.1, we dene a suitable random spanning subgraph of G : we rst we choose a code C by selecting each vertex independenty at random, and then we randomly delete edges among the edges containing vertices of C . We then analyze the construction by applying concentration inequalities and the use of the local lemma. A similar approach has been used in the literature when considering random subgraphs of a graph (see Section 2.3.1). Our random subgraph model is adapted to the analysis of identifying codes, and can be seen as a weighted version of Gp , like the one proposed by Alon [3]. Theorem 5.1 is asymptotically best possible in terms of both the number of deleted edges and the size of the nal identifying code for every graph with ∆ = Poly (d) (see Corollary 5.10). For smaller values of the minimum degree, we prove that our result is almost optimal. We also show that the two conditions, ∆ = ω(1) and d≥clog ∆ for some constant c , are necessary. When considering the case of adding edges to the graph, we get analogous (symmetric) results, showing that every graph is a large spanning subgraph of some graph that admits a small identifying code. This result also turns out to be tight. We also describe an application to the closely related topic of watching systems . This chapter is organized as follows. In Section 5.2, we dene our model of random subgraphs and use it to prove Theorem 5.1. In Section 5.3 we construct a family of graphs to show that Theorem 5.1 is almost tight for all values of d and ∆ . We present some other consequences of our result in Section 5.4, in particular, we argue about the case where edges are added to the graph. The chapter concludes with some nal remarks and open problems (Section 5.5). Chapter 5. Large spanning subgraphs admitting small identifying codes 73 5.2 Main theorem In this section, we prove Theorem 5.1. We will need some tools and lemmas. 5.2.1 Random subgraphs and identication In what follows, for every set of vertices B⊆V(G) and each v∈V(G) , we let NB G(v) = NG(v)∩B be the set of neighbors of v in B . Analogously, NB G[v] = NG[v]∩B . We denote by dB(v) = |NB G(v)| , the degree of v within set B . Denition 5.2. Given a graph G and B⊆V(G) , a function f:V(G)→R+∪ {0} is said to be (G, B) bounded if for each vertex u , f(u)≤dB(u) and for each pair u, v of vertices with dB(u)≥dB(v) , f(u)/dB(u)≤f(v)/dB(v) . Given a (G, B) bounded function f , we dene the random spanning subgraph G(B, f) of G as follows: •G(B, f) contains all edges of the subgraph G[V(G)\B] induced by V(G)\B , and • each edge uv incident with B is independently chosen to be in G(B, f) with probability 1−puv , where puv =1 4f(u) dB(u)+f(v) dB(v). Observe that, since f(u)≤dB(u) for each vertex u∈V(G) , we have puv ≤1/2 . The next lemma gives an exponential upper bound on the probability that two vertices of G(B, f) are not separated by B . This lemma is crucial in our main proof. Lemma 5.3. Let G be a graph, B⊆V(G) , and f a (G, B) bounded function. In the random subgraph G(B, f) , for every pair u, v of distinct vertices with dB(u)≥dB(v) , we have Pr NB G(B,f)[u] = NB G(B,f)[v]≤e−3f(u)/16 . Proof . Consider the following partition of S=NB G[u]∪NB G[v] into three parts: S1 , the vertices of B dominating u but not v ; S2 , the vertices of B dominating v but not u ; and S3 , the vertices of B dominating both u and v . Let D be the random variable which gives the size of the symmetric dierence of NB G(B,f)[u] and NB G(B,f)[v] . The statement of the lemma is equivalent to Pr(D= 0) < e−3f(u)/16 . The random variable D=|NB G(B,f)[u]⊕NB G(B,f)[v]| can be written as the sum of independent Bernoulli variables D=X w∈S Dw, where Dw= 1 if and only if w dominates precisely one of the two vertices u or v in G(B, f) . 74 5.2. Main theorem Therefore, for any w /∈ {u, v} , Pr(Dw= 1) =    1−puw if w∈S1, 1−pvw if w∈S2, puw(1 −pvw) + pvw(1 −puw) if w∈S3. Since we want to bound from above the probability that D= 0 , we can always assume that u, v /∈NB G(B,f)[u]⊕NB G(B,f)[v] . Recall that dB(u)≥dB(v) . By the denition of a (G, B)  bounded function, we have that puw ≤pvw for each w∈S3 . Since x(1 −x) has a unique maximum at x= 1/2 and puw, pvw ≤1/2 , we also have: pvw(1 −puw)≥puw(1 −puw)≥f(u) 4dB(u)1−f(u) 4dB(u)=g(u), (5.1) for each w∈S3 . For w∈S , denote by qw the parameter of the Bernoulli random variable Dw . Then, E(D)≥X w∈NB G(u) qw =X w∈S1 qw+X w∈S3 qw =X w∈S1 (1 −puw) + X w∈S3 (puw(1 −pvw) + pvw(1 −puw)) ≥X w∈S1 puw(1 −puw) + X w∈S3 puw(1 −puw) ≥g(u)dB(u) =f(u) 41−f(u) 4dB(u) ≥3 16f(u). (5.2) Finally, we have that Pr(D= 0) = Y w∈S (1 −qw)≤e−Pw∈Sqw=e−E(D)≤e−3f(u)/16 , and the lemma follows. 5.2.2 Proof of the main result We are now ready to prove the main theorem. Proof of Theorem 5.1 . The proof is structured in the following steps: 1. We select a set C at random, where each vertex is selected independently with probability p . Using the Cherno inequality, we estimate the probability of the event AC that C is small enough for our purposes. From C , we construct the spanning subgraph G(C, f) of G as given in Denition 5.2, for some suitable function f . Chapter 5. Large spanning subgraphs admitting small identifying codes 81 Eventually, there might be a unique vertex v such that NG[v]∩(C0∪C1) = ∅ (if there were two such vertices, they would not be separated by C0∪C1 , a contradiction). Hence, C=C0∪C1∪{v} is an identifying code of G of size at most 2|C0|= 2γ ID (G) . Proposition 5.9. For every M≥0 , there exists a constant c > 0 such that for every set of edges F⊂E(Kn) satisfying γ ID (Kn\F)≤Mlog n , |F| ≥ cn log n . Proof . Set M0=M/2 and let c=c0 be the constant given by Lemma 5.4 for this M0 . Suppose that there exists a set F of edges, |F|< cn log n such that G=Kn\F satises γ ID (G)≤Mlog n . By Lemma 5.5, the graph G admits an identifying code of size at most 2Mlog n=M0log n . By Lemma 5.4, we get a contradiction. If ∆ = Poly (d) , the former proposition provides an example of a graph for which the result of Theorem 5.1 is asymptotically tight. For every d > 0 , consider the graph Hd to be the disjoint union of cliques of order d+ 1 . We may assume that d+ 1 divides n for the sake of simplicity. Denote by H(1) d, . . . , H(s) d , s=n d+1 , the cliques composing Hd . Since H(i) d is a connected component, an asymptotically optimal identifying code for Hd must also be asymptotically optimal for each H(i) d . By Proposition 5.9, we must delete at least Ω(dlog d) edges from H(i) d to get an identifying code of size O(log d) . Thus, one must delete at least Ω(sd log d) = Ω(nlog d) edges from Hd to get an optimal identifying code. Corollary 5.10. For every d=ω(1) and every M≥0 , there exists a constant c > 0 such that for every set of edges F⊂E(Hd) satisfying γ ID (Hd\F)≤Mnlog d d , we have |F| ≥ cn log d . We remark that a connected counterexample can also be constructed from Hd by connecting its cliques using few edges, without aecting the above result. Corollary 5.10 implies that Theorem 5.1 is asymptotically tight when ∆ = Poly (d) , since in that case log ∆ = O(log d) . In the case where d is subpolynomial with respect to ∆ , there is a gap between the result of Theorem 5.1 and the construction provided here. 5.3.2 On the hypothesis We conclude this section by discussing the necessity of the conditions ∆ = ω(1) and d≥66 log ∆ in Theorem 5.1. First note that, if ∆ is bounded by a constant, we need at least n ∆+1 = Θ(n) vertices to dominate G . Thus, no code of size smaller than Θ(n) can be obtained by deleting edges of the graph. On the other hand, the condition d≥66 log ∆ in Theorem 5.1, is also necessary (up to a constant factor) as can be deduced from the following proposition. 82 5.4. Consequences of our results Proposition 5.11. For arbitrarily large values of ∆ , there exists a graph G with maximum degree ∆ and minimum degree d=log2∆ 2 such that, for every spanning subgraph H⊆G , γ ID (H) = (1 −o(1))n . Proof . Consider the bipartite complete graph G=Kr,s where s= 22r . Denote by V1 the stable set of size r and by V2 the stable set of size s . Observe that d=r=log2s 2=log2∆ 2 . For every twinfree spanning subgraph H⊆G , let C ⊆ V(G) be an identifying code of H . Let us show that most of the vertices in V2 must be in C . Let S⊆V2 be the subset of vertices in V2 that are not in the code. Thus, for every u∈S , NC[u] = NC(u) . Observe that NC(u)⊆V1 , and hence, there are at most 2r possible candidates for such NC(u) . Since C is dominating and separating all the pairs in S , all the subsets NC(u) must be nonempty and dierent, which implies, |S|<2r . Hence, we have |C| ≥ |V2\S| ≥ 22r−2r= (1 −o(1))22r= (1 −o(1))n . 5.4 Consequences of our results We now describe consequences of our results on the case when we want to add edges to a graph to decrease its identifying code number, and to the notion of watching systems. 5.4.1 Adding edges In the previous sections, we have studied how much can the identifying code number decrease when we delete few edges from the original graph. In this section, we discuss the symmetric question of how much can the addition of edges help to decrease this parameter. The question of how much can a parameter decrease when deleting/adding edges has been already studied for some monotone parameters. However, if the parameter is monotone, only one of either deleting or adding, can help to decrease it. One of the interesting facts of studying the identifying code number is that, since it is a nonmonotone parameter, we can have similar results for both procedures. As before, let G be a graph with maximum degree ∆ and minimum degree d . We aim to nd a set of edges F with F∩E(G) = ∅ such that γ ID (G∪F) is small. This set F will be provided by applying Theorem 5.1 to the graph G , that has maximum degree ∆(G) = n−1−d and minimum degree d(G) = n−1−∆ . Thus, it will have size |F|=Onlog ∆(G), and γ ID (G\F) = Onlog ∆(G) d(G). Since G\F=G∪F , we have the following corollary of Theorem 5.1 and Lemma 5.5. Chapter 5. Large spanning subgraphs admitting small identifying codes 83 Corollary 5.12. For every graph G on n vertices with minimum degree d=n−ω(1) and maximum degree ∆ such that n−∆≥66 log (n−d) , there exists a set of edges F with F∩E(G) = ∅ of size |F|=O(nlog (n−d)) , such that γ ID (G∪F) = Onlog (n−d) n−∆. This result is also asymptotically tight. Otherwise, by using again Lemma 5.5, we could translate our case to the case of deleting edges and we would get a contradiction with the optimality of Theorem 5.1. 5.4.2 Watching systems The result of Theorem 5.1 has a direct application for watching systems , which are a generalization of identifying codes [12, 11]. In a watching system, we can place on each vertex v a set of watchers . To each watcher w placed on v , we assign a nonempty subset Z(w)⊆N[v] , its watching zone . We now ask each vertex to belong to a unique and nonempty set of watching zones; the minimum number of watchers that need to be placed on the vertices of G to obtain a watching system is the watching number w(G) of G . It is clear from the denition that γ(G)≤w(G)≤γ ID (G) , since the vertices of any identifying code form a watching system (where the watching zones are the closed neighborhoods). In fact, even the following holds: Observation 5.13. For every twinfree graph G , w(G)≤min{γ ID (H), where H is a spanning subgraph of G}. Indeed, consider the spanning subgraph H0 of G with smallest identifying code number, and dene the watching system to be the vertices of an optimal identifying code of H0 , with the watching zones being the closed neighborhoods in H0 . In [12, Theorems 2 and 3 ], the authors propose the following upper bound for graphs with given maximum degree: Theorem 5.14 ([12]) . Let G be a graph with maximum degree ∆ , then dlog2(n+ 1)e ≤ w(G)≤γ(G)dlog2(∆ + 2)e. Note that for every values of parameters γ and ∆ , the upper bound from the above theorem is sharp for the graph consisting of γ disjoint copies of a star on ∆+1 vertices. Recall that the bound on the dominating number provided in (5.6) is tight. In particular, a d regular graph chosen uniformly at random is an asymptotically tight example with high probability. Indeed, for almost all d regular graphs G , the upper bound of Theorem 5.14 gives w(G)≤γ(G)dlog ∆ + 2e= Ω nlog2d d. (5.8) 84 5.5. Concluding remarks and open questions By Observation 5.13, a direct corollary of Theorem 5.1 is the following: Corollary 5.15. For every graph G on n vertices with minimum degree d≥66 log ∆ and maximum degree ∆ = ω(1) , we have: w(G)≤Onlog ∆ d. On the one hand, since γ(G)≥n d+1 , Corollary 5.15 is always at least as good as Theorem 5.14. On the other hand, if γ(G) is large, it asymptotically improves Theorem 5.14, as in case of a typical d -regular graph (see the bound in (5.8)). 5.5 Concluding remarks and open questions 1. The kind of results we provide in this chapter can be connected to the notion of resilience. Given a graph property P , the global resilience of G with respect to P is the minimum number of edges one has to delete to obtain a graph not satisfying P . The resilience of monotone properties is well studied, in particular, in the context of random graphs [122]. Our result can be interpreted in terms of the resilience of the following (nonmonotone) property P :  G has a large identifying code number in terms of its degree parameters, d and ∆ . For every graph G satisfying the hypothesis ∆ = ω(1) and d≥66 log ∆ , Theorem 5.1 can be stated as: the resilience of G with respect to P is O(nlog ∆) . Moreover, Corollary 5.10 shows that there are graphs that attain this value of the resilience. 2. In Theorem 5.1, we show the existence of a small identifying code for a large spanning subgraph of G . However, our proof is not constructive and, besides, the probability that such pair exists is exponentially small, due to the use of the local lemma. The algorithmic version of the local lemma proposed by Moser and Tardos [109], allows to explicitly nd a conguration that avoids all the bad events Auv , when these events are determined by a nite set of mutually independent random variables. Unfortunately, this is not the case here, since Auv depends on the random variables determining the existence of certain edges close to uv . These random variables are not independent because of the denition of puv . On the other hand, if we do not want to argue in terms of the maximum degree ∆ , one can show that by deleting a set of O(nlog n) random edges, any set of size Onlog n d is an identifying code with probability 1−o(1) . In such a case, the proof provides a randomized algorithm which constructs the desired code for almost all subgraphs. It is an open question whether this algorithm can be derandomized. 3. A notion similar to identifying codes, locating-dominating sets , has also been extensively studied in the literature (see e.g. [96] for many references). A set C of vertices of G is a locatingdominating set if C is a dominating set which separates all pairs of vertices in V(G)\ C . It follows that any identifying code is a locating-dominating set, hence Theorem 5.1 also holds for this notion. In fact, the proof of Corollary 5.10 can be adapted for this case too. 4. As further research, it would be very interesting to close the gap between the result in Chapter 5. Large spanning subgraphs admitting small identifying codes 85 Theorem 5.1 and the lower bound given by the example in Corollary 5.10. Motivated by this example, we ask the following question: Question 5.16. Is it true that for every graph G with minimum degree d , there exists a subset of edges F⊂E(G) of size |F|=O(nlog d), such that γ ID (G\F) = Onlog d d? It seems to us that the techniques used in this chapter will not provide an answer to the previous question. The main obstacle is the use of the local lemma, which forces us to take into account the role of the maximum degree of G . CHAPTER 6 Consecutive pattern avoiding in permutations 6.1 Introduction A permutation π∈ Sn contains σ∈ Sm as a consecutive pattern if there exists 0≤i≤n−m such that st(πi+1, . . . , πi+m) = σ , that is, there are m consecutive elements in π that have the relative order prescribed by σ . For instance, if σ= (1,2, . . . , m) , then π contains σ as a consecutive pattern if and only if it contains m consecutive increasing elements (a run of length m ). A permutation π∈ Sn is called consecutive σ avoiding if it does not contain σ as a consecutive pattern. We denote by αn(σ) the number of permutations in Sn that are σ avoiding. The problem of determining αn(σ) is inspired by the problem of nding the number of permutations of length n that avoid a pattern σ non necessarily in consecutive positions. A permutation π∈ Sn contains σ if there exist 1≤i1<··· < im≤n such that st(πi1, . . . , πim) = σ . Clearly, if π avoids σ , then π also avoids σ as a consecutive pattern. Knuth [90] introduced the non consecutive case and exactly determined the number of permutations avoiding some pattern of length 3 . There are many interesting results in the area (see e.g. [25, 5]) as well as the famous StanleyWilf conjecture which was proved by Marcus and Tardos [99]. For every σ∈Sm , it is hard to provide an exact formula for αn(σ) when n is large. Asymptotic formulas can be derived for some special patterns as showed by Elizalde and Noy [50]. In particular, the authors give an estimation of αn(σ) for every pattern σ of length 3 and also for some patterns of length 4 . However, even for the case of length 4 , there are still some patterns for which the asymptotic behavior of αn(σ) is not known. Elizalde [48] showed that for every σ∈ Sm , the following limit ρσ:= lim n→∞αn(σ) n!1/n , exists and that 0.7839 < ρσ<1 if m≥3 . A stronger result is given in [47], where the authors 87 88 6.1. Introduction show that αn(σ)∼cσρn σn! , for some constant cσ that only depends only on σ . A pattern of length m is called monotone if it is either (1,2, . . . , m) or (m, . . . , 2,1) . It is clear that αn(1,2, . . . , m) = αn(m, . . . , 2,1) , since π= (π1, . . . , πn) is (1,2,...m) avoiding if and only if its reversing (πn, . . . , π1) is (m, . . . , 2,1) avoiding. It was conjectured in [50] that monotone patterns are the most avoided ones among all patterns of length m , when n is large enough. This is known as the Consecutive Monotone Pattern (CMP) Conjecture . Conjecture 6.1 (CMP conjecture [50]) . For every σ∈ Sm , ρσ≤ρ(1,2,...,m). The results in [50], determining ρσ for every σ∈ S3 , settle in the armative the CMP conjecture for patterns of length 3 . Elizalde and Noy [51] show that the conjecture is true for the large class of nonoverlapping patterns. A pattern is nonoverlapping if two copies of the pattern in a permutation share at most one position. Regarding the least avoided pattern among all the patterns of length m , Nakamura [111] posed the following conjecture motivated by some simulations for small values of n and m . Conjecture 6.2 ([111]) . For every σ∈ Sm , ρσ≥ρ(1,2,...,m−2,m,m−1) . Both conjectures have been recently proved by Elizalde [49]. The proofs are based on computing the generating function for the number of σ avoiding permutations, Pσ(z) = Pαn(σ)zn n! , combined with the cluster method of Goulden and Jackson [71]. Here we will use a completely dierent approach to the consecutive pattern avoiding problem through the probabilistic method. While this approach is not as precise as the generating function technique, it provides simpler alternative proofs of some known results, as the CMP conjecture, and allows one to obtain more general results. All along this chapter, m will be a xed integer while n will be considered to tend to innity. For the sake of simplicity, however, we will use asymptotic notation on m . If this is the case, we will consider m to tend to innity while n will be an arbitrarily large function of m . Since we are interested in ρσ , we will consider m to be a xed integer and n to be arbitrarily large with respect to n . Our rst result bounds ρσ from above when the pattern σ is not monotone. Theorem 6.3. For every σ∈ Sm\{(1,2, . . . , m),(m, . . . , 2,1)} , ρσ≤1−1 m!+O1 m2·m!. To prove this theorem we make use of Suen Inequality (see Theorem 2.16), a powerful tool that provides an upper bound on the probability that none of the events of a certain collection happen simultaneously. By comparing the upper bound given by Theorem 6.3 with the result obtained by Elizalde and Noy [51] for ρ(1,2,...,m) we get the following corollary, Chapter 6. Consecutive pattern avoiding in permutations 89 Corollary 6.4. There exists an integer m0 , such that for any m≥m0 and every pattern σ∈ Sm\{(1,2, . . . , m),(m, . . . , 2,1)} , 1−ρσ≥1+Ω1 m(1 −ρ(1,2,...,m)). This immediately provides an alternative probabilistic proof for the CMP conjecture for large values of m . Analyzing more carefully the proof of Theorem 6.3 for small values of m , we can show that the CMP conjecture holds for m≥5 . The same approach, however, does not provide meaningful results for the case m= 4 . This corollary also gives a lower estimation of the minimum gap between ρ(1,2,...,m) and ρσ , for every non monotone σ∈ Sm . Theorem 6.3 can be extended to the whole set of patterns, Sm , by weakening the upper bound; for every σ∈ Sm , ρσ≤1−1 m!+O1 m·m!. The second part of the chapter is devoted to the proof of a general lower bound on ρσ for σ∈ Sm . Theorem 6.5. For every σ∈ Sm , ρσ≥1−1 m!−Om (m!)2. To prove this lower bound we use the onesided version of the Lovász Local Lemma (see Lemma 2.14). This bound is asymptotically tight and an extremal example is provided by the pattern (1,2, . . . , m −2, m, m −1) , the least avoided pattern of length m . Unlike in the case of the upper bound and the CMP conjecture, our proof of Theorem 6.5 can not be adapted to extract a proof of Conjecture 6.2. As Theorem 6.3 and Theorem 6.5 give bounds for the value of ρσ in terms of m , a natural question is to determine how most of the patterns behave. In this direction a much stronger upper bound, close to the general lower bound, is showed to hold for most of the patterns. Theorem 6.6. Let σ∈ Sm be chosen uniformly at random. Then, for each 2≤k≤m/2 , ρσ≤1−1 m!+O4m (m−k)!m!, with probability at least 1−2 (k+1)! −m2m (m/2)! . This theorem shows that when m large enough, for most of the patterns the value of ρσ is concentrated close to the lower bound provided by Theorem 6.5. The idea behind the proof of this result is that the number of permutations avoiding a pattern depends on the maximum overlapping position of this pattern. It can be showed that almost all patterns do not have a large overlap and thus, they are far from the upper bound attained by monotone patterns, the ones with maximum overlap. 90 6.2. A probabilistic approach on consecutive pattern avoiding This chapter is organized as follows. The upper bound on ρσ is studied in Section 6.3, where Theorem 6.3 and Corollary 6.4 are proved. Section 6.4 is devoted to the proof of Theorem 6.5. Finally, in Section 6.5 we provide an upper bound for most of the patterns σ by proving Theorem 6.6. We conclude with some remarks and open questions in Section 6.6. 6.2 A probabilistic approach on consecutive pattern avoiding Our goal in this section is to give a proper set of bad events A for our problem and build a good dependency graph for A . The probability that a random permutation avoids all the events in A will be the probability that a random permutation avoids σ∈ Sm as a consecutive pattern. Let π∈ Sn be chosen uniformly at random, and let σ∈ Sm be a xed pattern. We consider the set of events A={A0, . . . , An−m} where Ai:= {st(πi+1, . . . , πi+m) = σ} . As before, we let Xi be the indicator random variable of the event Ai and let X=Pn−m i=0 Xi denote the number of events in A which are realized. Then, π avoids σ as a consecutive pattern if and only if X= 0 , that is, no copy of the pattern σ appears. We have, αn(σ) = Pr(X= 0)n!, where the dependency of X on σ will be clear from the context. In particular we will be interested in ρσ= lim n→∞Pr(X= 0)1/n . (6.1) Bounding from above the number of edges in a dependency graph H is crucial in order to give a proper upper bound on the probability that no event in A holds. The following lemma shows that we can choose a dependency graph H with few edges. Lemma 6.7. Let S, T ⊆ {0,1, . . . , n−m} be two disjoint subsets such that for each (i, j)∈S×T , we have |i−j| ≥ m . Then, the set of events {Ai}i∈S and {Aj}j∈T are mutually independent. Proof . In order to prove that {Ai}i∈S and {Aj}j∈T are mutually independent, we use the random permutation model dened in Section 2.3. Recall that a uniform permutation from Sn can be obtained by considering Z1, . . . , Zn independent uniform random variables in (0,1) and by choosing π= st(Z1, . . . , Zn) . Observe that the event Ai depends only on the random variables Zi+1, . . . , Zi+m . By the hypothesis of the lemma, we have that for each i∈S and j∈T , |i−j| ≥ m . Then, using the Mutual Independence Principle (see Observation 2.7) with Fi={i+ 1, . . . , i +m} , and noting that (∪i∈SFi)∩(∪j∈TFj) = ∅, we have that the set of events {Ai}i∈S and {Aj}j∈T are mutually independent. According to the previous lemma, the graph H with vertex set V(H) = {0,1, . . . , n −m} , where ij ∈E(H) if and only if 0<|i−j|< m , is a dependency graph for A . Throughout the chapter, we will use this graph H as a dependency graph of A . Chapter 6. Consecutive pattern avoiding in permutations 97 It can be checked that L(5) is larger than the bound we get by setting ∆∗= (Pr(Ai∩Ai+2) + Pr(Ai∩Ai+4)) n≤ 2 7! +8 4 9! !n in (2.22), where Pr(Ai∩Ai+4) has been computed by using Lemma 6.10. 6.4 A lower bound on ρσ . The setting used to give an upper bound on the number of permutations avoiding a given pattern can be also used to provide a lower bound on ρσ . Now we need a way to bound from below the probability that X= 0 and for this purpose we will use the Lovász Local Lemma. Usually, the Local Lemma is used to show the existence of a certain conguration that does not satisfy any of the bad events in A . In our problem it is trivial to see that, for any pattern σ∈ Sm , there exists at least one permutation of length n that avoids σ . We are interested in providing an explicit lower bound on the probability that a permutation selected uniformly at random avoids σ . This can be also attained through the local lemma. Thus, we will use it to derive a lower bound on the number of permutations of length n that avoid σ . The onesided version of the Lovász Local Lemma (see Lemma 2.14) is particularly convenient for our approach. Next, we show how the use this version of the local lemma to prove a lower bound on ρσ . Proof of Theorem 6.5 . Let A={A0, . . . , An−m} and let X be dened as in Section 6.3. Set m(i) = i−m+ 1 . By using Lemma 6.7 with S={i} and T={0,1...,i−m} , we have Pr Ai|\ j≤i−m Aj= Pr (Ai). Recall that Pr (Ai) = 1 m! . Since all the events have the same probability to appear, we set xi=x , for each 0≤i≤n−m , in (2.19) from Lemma 2.14, to get 1 m!≤x(1 −x)m−1. By setting x=em−1 m! m! , the above inequality is satised and the Local Lemma can be applied. In particular, we obtain the following lower bound on the probability that X= 0 , Pr(X= 0) = Pr n−m \ i=0 Ai≥ 1−e(m−1)/m! m!!n−m+1 . and, by using (6.1), ρσ≥1−e(m−1)/m! m!= 1 −1 m!−Om (m!2). 98 6.5. The typical value of ρσ . The lower bound given by Theorem 6.5 is tight. This can be showed by using a result of Elizalde [49], where the author proved that the least avoided pattern is (1,2,...m−2, m, m−1) . The author also gives an implicit lower bound on z0=ρ−1 (1,2,...,m−2,m,m−1) as the smallest real root of f(z)=1−z+zm m!−mz2m+1 (2m−1)! . The following explicit upper bound can be derived from the previous equation, as in Lemma 6.12, ρ(1,2,...,m−2,m,m−1) ≤1−1 m!−Ωm (m!)2, showing that Theorem 6.5 is tight. 6.5 The typical value of ρσ . The results of the previous sections provide tight upper and lower bounds on ρσ for every σ∈ Sm . In this section we want to show that, for a typical pattern, ρσ lies much closer to the lower bound than to the upper bound. That is, the number of σ avoiding permutations of length n , for σ∈ Sm chosen uniformly at random, is typically closer to the number of permutations that avoid (1,2, . . . , m −2, m, m −1) than to the number of permutations that avoid (1,2, . . . , m) . Dene Nk⊆ Sm as the set of patterns of length m that overlap at position k . The following lemma bounds from above the size of these sets. Lemma 6.15. Let σ∈ Sm be chosen uniformly at random. Then 1. Pr(σ∈ Nk) = 1 k! if 2≤2k≤m . 2. Pr(σ∈ Nk)≤2m (m/2)! if m < 2k≤2(m−1) . Proof . Choose σ∈ Sm uniformly at random. Recall that the condition for σ∈ Nk is that τ(1) = st(σ1, . . . , σk) and τ(2) = st(σm−k+1, . . . , σm) are equal to each other. If 2k≤m , then τ(1) and τ(2) are independent, by Lemma 6.7, and uniformly distributed in Sk . For every τ, τ0∈ Sk Pr(τ(1) =τ|τ(2) =τ0) = Pr(τ(1) =τ). Thus, we can compute the exact probability of being in Nk Pr(σ∈ Nk) = Pr(τ(1) =τ(2)) = X τ∈Sk Pr(τ(1) =τ∩τ(2) =τ) = k! Pr(τ(1) =τ)2=1 k!. Suppose now that 2k > m . For any integer `≥1 , observe that Nm−k⊆ Nm−`k . This in particular implies that |Nm−k| ≤ |Nm−`k| . Thus, for any k such that 2k > m there exists an integer k0∈[m/2,3m/4] such that |Nk| ≤ |Nk0| . So we may assume that k≤3m/4 . Partition the pattern σ in s=bm m−kc parts of length m−k by dening the permutations τ(i)= st(σ(m−k)(i−1)+1, . . . , σ(m−k)i) for each 1≤i≤s and one part, τ(s+1) , consisting in the Chapter 6. Consecutive pattern avoiding in permutations 99 last m−s(m−k) positions. Observe that, in order to have an overlap at k we must have τ(1) =τ(i) for each i≤s and τ(s+1) = st(σ(s−1)(m−k), . . . , σk) . This condition is clearly necessary but not sucient for a pattern to overlap at k . By the choice of σ , the permutations τ(i) are uniformly distributed, and, by Lemma 6.7, they are mutually independent. This implies, Pr(σ∈ Nk)≤Pr(τ(s+1) = st(σ(s−1)(m−k), . . . , σk)) Y i≤s Pr(τ(i)=τ(1)) =1 (m−s(m−k))! 1 (m−k)!s−1 . If k≤2m/3 , then s= 2 . If k=m/2 + t , then Pr(σ∈ Nk)≤1 (2t)!(m/2−t)! =m/2+t 2t (m/2 + t)! <2m (m/2)! . If 2m/3≤k≤3m/4 , then s= 3 . If k= 2m/3 + t , then Pr(σ∈ Nk)≤1 (3t)!(m/3−t)!(m/3−t)! =m/3+2t 3t (m/3 + t)!(m/3−t)! <2m (m/2)! . For each 1≤k≤m−1 , dene the set Mk⊆ Sm as the set of patterns of length m such that Oσ⊆ {1,2,...k} . Observe that Mm−1 coincides exactly with Sm . The elements in M1 are called nonoverlapping patterns. They have been enumerated in [26] and also extensively studied in [49]. We use the previous lemma to give a lower bound on the size of Mk . Lemma 6.16. Let σ∈ Sm be chosen uniformly at random. Then, for each 1≤k≤m/2 , Pr (σ∈ Mk)≥1−2 (k+ 1)! −m2m (m/2)!. Proof . Observe that we can bound from below the size of Mk by using the sets Nk , |Mk|=Sm\ m−1 [ `=k+1 N`≥m!− m−1 X `=k+1 |N`|. (6.9) By Lemma 6.15, for each k such that 2k≤m , m−1 X `=k+1 Pr(σ∈ N`)≤1 (k+ 1)! +1 (k+ 2)! +···+1 bm/2c!+m2m (m/2)! . The relation in (6.9) gives Pr (σ∈ Mk)≥1− m−1 X `=k+1 Pr(σ∈ N`)≥1− m/2 X `=k+1 1 `!−m2m (m/2)! ≥1−2 (k+ 1)! −m2m (m/2)! , which proves the statement. 100 6.6. Concluding remarks and open questions Recall that M1 corresponds to the set of nonoverlapping patterns. The proof of Lemma 6.16 implies that |M1| ≥ (3 −e)m! . This bound can be rened. Indeed, Bóna [26] showed that 0.364098149 ≤|M1| m!≤0.3640992743 . The previous bound on |Mk| is clearly non sharp. A better estimation of the size of Nk when 2k > m , would help to understand the distribution of ρσ when σ∈ Sm is chosen uniformly at random. Next lemma gives a better upper bound on ∆∗ than the one in (6.5) when the pattern does not have a large overlap. Lemma 6.17. For every σ∈ Mk , ∆∗≤4m−k (2m−k)!n . Proof . Since σ∈ Mk we have Pr(Ai∩Ai+m−j)=0 for all k < j ≤m−1 . By Lemma 6.10, ∆∗≤ n−m X i=0 max{k,2m+j−n} X j=1 Pr(Ai∩Ai+m−j)≤n k X j=1 2(m−j) m−j (2m−j)! ≤n k X j=1 4m−j pπ(m−j)(2m−j)! ≤4m−k (2m−k)!n . Proof of Theorem 6.6 . Assume that σ∈ Mk . By using the notation for µ , ∆∗ and δ∗ from Section 6.3, it follows from Lemma 6.17 that ∆∗ µ≤4m−km! (2m−k)! =4m 2m−k m(m−k)! ≤4m (m−k)! . and that e2δ∗≤e4/(m−1)! ≤2 for each m≥4 . Analogously to the proof of Theorem 6.3, we can derive the following upper bound, ρσ≤1−1 m!+O4m (m−k)!m!. The above upper bound is satised when σ∈ Mk . This event holds, by Lemma 6.16, with probability at least 1−2 (k+1)! −m2m (m/2)! . This completes the proof. 6.6 Concluding remarks and open questions 1. The techniques displayed in this chapter could be applied for the study other type of patterns in permutations [27, 88] or in other combinatorial structures, like matrices [67, 99]. In permutations, the most interesting case appears when considering nonconsecutive pattern avoiding. One may think that the ideas introduced here could be useful to study this problem. Unfortunately, due to the strong dependency among a large part of the dened events, our techniques seem useless there. Chapter 6. Consecutive pattern avoiding in permutations 101 Generalized patterns have been recently introduced [31] to cover all the dierent kinds of patterns in permutations. A generalized pattern is a triple p= (σ, S, T) with σ∈Sm and S, T ⊆ {0,1, . . . , m} . An occurrence of p in π is a set of positions 1≤i1<··· < im≤n such that st(πi1, . . . , πim) = σ . Moreover, for all j∈S , ij+1 =ij+ 1 and for all k∈T , πik+1 =πik+ 1 . By convention, i0=πi0= 0 and im+1 =πim+1 =m+ 1 . Observe that consecutive patterns are obtained when S={1,2, . . . , m −1} and T=∅ . If S=T=∅ , then we recover the denition of a nonconsecutive pattern. For a general set S , the number of dependencies created among the events is still too large to apply our techniques. However, if S={1,2, . . . , m −1} one could apply the same ideas, even if T6=∅ . In such a case, it can be useful to consider a lopsidependency graph in order to get rid of the positive correlations. 2. In order to prove Conjecture 6.2 by using probabilistic techniques, one could try to mimic the same strategy we have used for proving the CMP conjecture. First, determine the subset of patterns σ such that αn(σ) = αn(1,2, . . . , m −2, m, m −1) , the least avoided pattern, and then, improve the lower bound given by Theorem 6.5 for the patterns which are not in the previous subset. Our approach, however, is hopeless to tackle Conjecture 6.2. Notice that no assumption on the properties of the pattern σ has been used in the proof of Theorem 6.5, unlike in the proof of the upper bound in Theorem 6.3. Unfortunately, the local lemma cannot distinguish the dierent nature of the dependencies among events. Thus, no better lower bound can be achieved by restricting to a smaller subset of patterns. This prompts us to formulate the following question. Question 6.18. Let σ∈ Sm be chosen uniformly at random. Is it true that ρσ≥1−1 m!+f(m), for certain f(m)≥0 , with probability at least g(m)>0 ? This is also the main problem to provide a lower bound for ρ(1,2,...,m) (see Lemma 6.12) using our probabilistic setting. Question 6.19. Is it possible to provide a probabilistic proof for Lemma 6.12? To answer this question, one would need to understand the probabilities Pr Ai|Tj<i Aj when σ= (1,2, . . . , m) . It must be stressed that, in such case, the upper bound Pr Ai|Tj<i Aj≤ Pr (Ai) does not suce to provide a meaningful lower bound on ρ(1,2,...,m) . 3. One of the crucial steps in proving Theorem 6.6 is to upper bound the size of the sets Nk , for any k≤m−1 . Lemma 6.15 provides the exact value of |Nk| when 2k≤m . Nonetheless, the upper bound given when m > 2k is far from being tight. If m > 2k , not every pattern of length k is a candidate for τ(1) = st(σ1, . . . , σk) and τ(2) = st(σm−k+1, . . . , σm) . This observation suggests that, if 2k > m , then the probability that a pattern σ chosen uniformly at random belongs to Nk is smaller than in the case when 2k≤m . This motivates the following conjecture 102 6.6. Concluding remarks and open questions Conjecture 6.20. Let Nk be the set of patterns that overlap at position k . Then, |Nk| ≤ 1 k!, for every 1≤k≤m−1 . This conjecture is also supported by numerical computations for small values of m . Notice that the expected number of overlaps of a randomly chosen pattern can be expressed as the sum of |Nk| . An interesting fact is that, if Conjecture 6.20 is true, then this is at most e . Furthermore, if this conjecture holds, then it would provide a stronger version for Theorem 6.6. CHAPTER 7 On the Lonely Runner Conjecture 7.1 Introduction Let n be a positive integer and let v1, . . . , vn, vn+1 be a set of dierent positive real numbers, also called speeds. For any real number x , denote by kxk , the distance from x to the closest integer kxk= min{x−bxc,dxe−x}. For any real number x , denote by {x} its fractional part. {x}=x−bxc. The Lonely Runner Conjecture was posed independently by Wills [127] in 1967 and Cusick [41] in 1982. Suppose that n+ 1 runners are running on the unit circle with dierent speeds and starting at the origin. Then, for each runner, there is a time where he is far from all the other runners. More formally, Conjecture 7.1. For every n≥1 , every set of dierent speeds v1, . . . , vn+1 and each k∈[n+1] , there exists a time t such that kt(vi−vk)k ≥ 1 n+ 1 , for every i∈[n+ 1] , i6=k . This conjecture can be restated by assuming that the runner we want to isolate has speed zero. Thus, he stays at the origin all the time and one must show that there is a time where all the runners are far enough from the origin. Conjecture 7.2 (Lonely Runner Conjecture) . For every n≥1 and every set of nonzero speeds v1, . . . , vn , there exists a time t such that ktvik ≥ 1 n+ 1 , for every i∈[n] . 103 104 7.1. Introduction From now on, when we talk about the Lonely Runner Conjecture we will refer to the statement of Conjecture 7.2. Observe that, if true, the Lonely Runner Conjecture would be best possible. For the set of speeds, vi=i for every i∈[n], (7.1) there is no time for which all the runners are further from the origin than 1 n+1 . This example is not unique and an innite family of extremal sets can be found in [70]. The Lonely Runner Conjecture appears in many dierent situations. We next describe some known results and some related motivations. Let us rst notice that the conjecture is obviously true for n= 1 , since at some point ktv1k= 1/2 , and it is also easy to show that it holds for n= 2 . Many proofs for n= 3 are given in the context of diophantine approximation (see [18, 41]). A computerassisted proof for n= 4 was given by Cusick and Pomerance motivated by a viewobstruction problem in geometry [42], and later Biena et al. [19] provided a simpler proof by connecting it to nowhere zero ows in regular matroids. The conjecture was proved for n= 5 by Bohmann, Holzmann and Kleitman [21]. Barajas and Serra [13] have showed that the conjecture holds for n= 6 by studying the regular chromatic number of distance graphs. In [21], the authors also showed that the conjecture can be reduced to the case where all speeds are positive integers and in the sequel we will assume this to be the case. In such a case, we also may assume that t takes values on the (0,1) unit interval, since at t∈Z , ktvik= 0 for all i . On the other hand, the conjecture can be showed to be true in the case where the set of speeds has a special structure. For instance, Czerwi«ski [43] showed a strengthening of the conjecture for the case where all the speeds are chosen uniformly at random among all the n -subsets of [N] as N→ ∞ . In particular, Czerwi«ski's result implies that, for almost all sets of runners, there exists a time where all the runners are arbitrarily close to 1/2∈(0,1) . The dependence of N with respect to n , for which this result holds, was improved recently by Alon [4]. Dubickas [46] used a result of Peres and Schlag [116] in lacunary integer sequences to prove that the conjecture holds if the sequence of increasing speeds grows fast enough; in particular, if n is large and vi+1 vi≥1 + 22 log n n, for every 1≤i < n . These results introduce the use of the Lovász Local Lemma to deal with the dependencies created among the runners. Another approach to the conjecture is to reduce the gap of loneliness. That is, show that there exists a δ≤1 n+1 such that, for any set of nonzero speeds, there exists a time t∈(0,1) such that ktvik ≥ δ for every i∈[n]. (7.2) For this approach it is particularly useful to dene the following sets, Ai={t∈(0,1) : ktvik< δ}. For every t∈Ai , we will say that the i th runner is δ close to the origin at time t . Otherwise, we will say that the runner is δ far from the origin at time t . Chapter 7. On the Lonely Runner Conjecture 105 The set Ai can be thought of as an event in the probability space (0,1) with the uniform distribution. In that case, notice that we have Pr(Ai)=2δ independently from the value of vi . If the following equation is satised Pr n \ i=1 Ai!>0, (7.3) then, there exists a time t for which (7.2) holds. Observe that this is not a necessary condition. For instance, if we consider the set of speeds given by (7.1), the Lonely Runner Conjecture is satised but it can be checked that Pr(∩n i=1Ai)=0 when δ=1 n+1 . Here, it is also convenient to consider the indicator random variables Xi for the events Ai . Let X=Pn i=1 Xi count the number of runners which are δ close from the origin at a time t∈(0,1) chosen uniformly at random. Then, condition (7.3) is equivalent to Pr(X= 0) >0 . A rst straightforward result in this direction is obtained by using the union bound in (7.3). For any δ < 1 2n , we have Pr n \ i=1 Ai!≥1− n X i=1 Pr(Ai)=1−2δn > 0. This result was improved by Chen [35], who showed that, for any set of n nonzero speeds, there exists a time t such that ktvik ≥ 1 2n−1 + 1 2n−3 , (7.4) for every i∈[n] . If 2n−3 is a prime number, then the previous result was extended by Chen and Cusick [36]. They showed that for any set of n speeds, there exists a time t such that ktvik ≥ 1 2n−3, for every i∈[n] . In order to improve (7.4), we exactly compute the pairwise join probabilities Pr(Ai∩Aj) , the amount of time that two runners spend close to the origin at the same time. As a corollary, we give the following lower bound on E(X2) . Proposition 7.3. For any δ < 1 , we have E(X2)≥2δn δ1 + c log δ−1n+ 1, for some constant c > 0 . Using this bound, we are able to improve Chen's result on the gap of loneliness around the origin. 106 7.1. Introduction Theorem 7.4. For every ε > 0 , every suciently large n and every set of nonzero speeds v1, . . . , vn , there exists a time t∈(0,1) such that ktvik ≥ 1 2n−2 + ε, for every i∈[n] . The proof of this theorem uses a Bonferronitype inequality (see Lemma 2.6) that improves the union bound with the knowledge of pairwise intersections. Another interesting result on the Lonely Runner Conjecture, was given by Czerwi«ski and Grytczuk [44]. We say that a runner k is almost alone at time t if there exists a j6=k such that kt(vi−vk)k ≥ 1 n+ 1 , for every i6=j, k . In [44], the authors showed that every runner is almost alone at some time. This means that Conjecture 7.2 is true, if we are allowed to to make one runner invisible, that is, there exists a time when all runners but one are far enough from the origin. Theorem 7.5 ([44]) . For every n≥1 and every set of nonzero speeds v1, . . . , vn , there exist a time t∈(0,1) and a j∈[n] such that ktvik ≥ 1 n+ 1 for every i6=j . As a corollary of Proposition 7.3, we get the following result that extends Theorem 7.5 when n is large. Theorem 7.6. For every suciently large n and every set of nonzero speeds v1, . . . , vn , there exist t1, t2∈(0,1) and j1, j2∈[n] , j16=j2 , such that for any `∈ {1,2} , kt`vik ≥ 1 n+ 1 , for any i6=j` . This theorem extends Theorem 7.5 by showing the existence of not only one but two runners whose deletion leave the origin alone at some point. A similar result can be derived by using a model of dynamic circular interval graphs. Then, we can show that at least two runners are almost alone at the same time. Theorem 7.7. For every suciently large n and every set of dierent speeds v1, . . . , vn , there exist a time t∈(0,1) , k1, k2∈[n] , k16=k2 , and j1, j2∈[n] such that for any `∈ {1,2} , kt(vi−vk`)k ≥ 1 n, for any i6=k`, j` . Chapter 7. On the Lonely Runner Conjecture 113 Proof of Proposition 7.3 . Recall that by (7.7), for any pair i, j ∈[n] , we have Pr(Ai∩Aj)≥2δ2 . We will show that at least a Ω1 log δ−1 fraction of the pairs are ε good. Consider the graph H on the vertex set V(H)=[n] , where ij is an edge if and only if ij is ε good. Using Lemma 7.13, we know that there are no independent sets of size larger than m= logc(αδ−1) = log δ−1 c0 ε+ 1 , where c0 ε depends only on ε . Thus, the complement of H , H , has no clique of size m . By the Erd®sStone theorem (see [54]), |E(H)| ≤ m−2 m−1 n2 2 , which implies that there are |E(H)| ≥ n2 2(m−1) , ε good unordered pairs. Now, we are able to give a lower bound on the second moment, E(X2) = X ij ε good Pr(Ai∩Aj) + X ij non ε good Pr(Ai∩Aj) + n X i=1 Pr(Ai) ≥(1 −ε)4δ2n2 logcαδ−1−1+ 2δ2n(n−1) −n2 logcαδ−1−1+ 2δn = (1 −ε)4δ2c0 εn2 log δ−1+ 2δ21−c0 ε log δ−1n2+ 2δn ≥2δn δ1 + cε log δ−1n+ 1, for some cε that depends only on ε . Next, we show some applications of our bounds, that extend some known results. 7.2.1 First application: Improving the gap of loneliness In this subsection we show how to use the pairwise join probabilities to prove Theorem 7.4. For such a purpose, we will use the Bonferronitype inequality displayed in Lemma 2.6. As we have already mentioned, Pr(Ai) = 2δ . Thus, it remains to select a tree T that maximizes Pij∈E(T)Pr(Ai∩Aj) . Lemma 7.14. For each ε0>0 and δ=o(1) , there exists a tree T on the set of vertices [n] such that X ij∈E(T) Pr(Ai∩Aj)≥(1 −ε0)4δ2n . Proof . By Proposition 7.9 we have Pr(Ai∩Aj)=4δ2+2(vi, vj)2f(εij, εji) vivj . 114 7.2. Correlation among runners Set γ < 2ε0 . We will construct a large forest F on the set of vertices [n] , where all the edges ij ∈E(F) are ε0 good. That is, they satisfy, Pr(Ai∩Aj)≥(1 −ε0)4δ2= (4 −2γ)δ2. Let us show how to select such edges by a procedure. Set S0= [n] and E0=∅ . In the k -th step, we select dierent i, j ∈Sk−1 such that either vi/vj≤(1 −γ)−1 or vi/vj≥γ−1δ−1 , and set Ek=Ek−1∪{ij} , Sk=Sk−1\{i} . If no such pair exists, we stop the procedure. Let τ be the number of steps that the procedure runs before being halted. By Lemma 7.13 with c= (1 −γ)−1 and α=γ−1 we can always nd such an edge ij , provided that the set Sk has size at least logc(αδ−1) . Thus τ≥n−logc(αδ−1) . Since the size of the sets Ek increases exactly by one at each step, we have |Eτ| ≥ n−logc(αδ−1) = (1 −o(1))n , since δ=o(1) . Besides, Eτ is an acyclic set of edges. We are never closing a cycle since we always delete one of the endpoints of the selected edge, from the set Sk . By Lemma 7.12, for each edge in Eτ we have Pr(Ai∩Aj)≥(4 −2γ)δ2. Therefore we can construct a spanning tree T on the vertex set [n] satisfying X ij∈E(T) Pr(Ai∩Aj)≥(1 −o(1)) (4 −2γ)δ2n≥(1 −ε0)4δ2n . Let us proceed to prove Theorem 7.4. Proof of Theorem 7.4 . By Lemma 2.6 and Lemma 7.14 with ε0=ε/2 , we have Pr n \ i=1 Ai!≥1− n X i=1 Pr(Ai) + X ij∈E(T) Pr(Ai∩Aj) ≥1−2δn(1 −2(1 −ε0)δ). The above expression is strictly positive for δ≤1 2n−2+2ε0=1 2n−2 + ε, and the theorem follows. 7.2.2 Second Application: Invisible runners This subsection is devoted to the proof of Theorem 7.6. In particular, we use the result of Proposition 7.3 to show that there is a large fraction of time where only one runner is δ close to the origin, for δ=1 n+1 . This implies the existence of at least two runners whose delition leave the origin alone at some time. Chapter 7. On the Lonely Runner Conjecture 115 Proof of Theorem 7.6 . For δ=1 n+1 , we have E(X) = 2n n+1 = 2 −(1 + O(n−1)) 2 n . Moreover, by Proposition 7.3, for any ε > 0 E(X2)≥(1 + O(n−1)) 4 + 2c log n, for some constant c > 0 . For every 0≤k≤n , let pk:= Pr(X=k) . We may assume that p0= 0 since otherwise, there would exists a time when all the runners are 1 n+1 far from the origin, which implies Conjecture 7.2. Then we have the following system of linear equations, p1+p2+. . . +pn= 1 p1+ 2p2+. . . +npn=E(X) p1+ 4p2+. . . +n2pn=E(X2). From these equations one can deduce that, p1= 2 −E(X) + n X i=1 (i−2)pi= (1 + O(n−1)) 2 n+ n X i=1 (i−2)pi n X i=1 (i−1)(i−2)pi=E(X2)−3E(X) + 2 = (1 + O(n−1)) 2c log n. Then, p1 is minimized when p3=··· =pn−1= 0 and pn= (1 + O(n−1)) 2c (n−1)(n−2) log n . Thus, p1≥(1 + O(n−1)) 2 n+ (1 + O(n−1)) 2c nlog n= (1 + O(n−1)) 2 n−cn log n Since a runner spends no more than 2δ=2 n+1 fraction of the time close the origin and c does not depend on n , there should be at least two such runners that make the origin almost alone at some point. 7.3 Weaker conjectures and interval graphs In this section we give a proof for Theorem 7.7. The following weaker conjecture has been proposed by Spencer 1 . Conjecture 7.15 (Weak Lonely Runner Conjecture) . For every n≥1 and every set of dierent speeds v1, . . . , vn , there exist a time t and a runner j∈[n] , such that kt(vi−vj)k ≥ 1 n for every i6=j . 1 Transmitted to the author by Jarek Grytczuk. 116 7.3. Weaker conjectures and interval graphs For every set S⊆[n] , we say that S is isolated at time t if, kt(vi−vj)k ≥ 1 n for each i∈S , j∈V\S . (7.9) Observe that S={i} is isolated at time t , if and only vi is lonely at time t . To study the appearance of isolated sets, it is convenient to dene a dynamic graph G(t) , whose connected components are sets of isolated runners at time t . For each 1≤i≤n and t∈(0,1) , dene the following dynamic interval of the torus (0,1) associated to the i -th runner, Ii(t) = x∈(0,1) : {x−tvi}<1 n. In other words, Ii(t) is the interval that starts in the position {tvi} of the i -th runner at time t and has length 1 n . Now we can dene the following dynamic circular interval graph G(t) = (V(t), E(t)) . The vertex set V(t) is composed by n vertices ui that correspond to the set of runners, and two vertices ui and uj are connected if Ii(t)∩Ij(t)6=∅ (see Figure 7.3). Figure 7.3: An instance of the graph G(t) . Observation 7.16. The graph G(t) satises the following properties, 1. G(0) = Kn . 2. Each connected component of G(t) , correspond to an isolated set of runners at time t . 3. If ui is isolated in G(t) , then vi is alone at time t . 4. All the intervals have the same size, |Ii(t)|= 1/n , and thus, G(t) is a unit circular interval graph. We can restate the Lonely Runner Conjecture in terms of the dynamic interval graph G(t) . Conjecture 7.17 (Lonely Runner Conjecture) . For any i≤n there exists a time t such that ui is isolated in G(t) . Chapter 7. On the Lonely Runner Conjecture 117 For every subgraph H⊆G(t) we dene µ(H) = µ(∪ui∈V(H)Ii(t)) , the length of the arc occupied by the intervals corresponding to H . Notice that, if H contains an edge, then µ(H)<|V(H)| n, (7.10) since the intervals Ii(t) are closed in one extreme but open in the other one. If H consists of isolated vertices, then (7.10) does not hold. The dynamic interval graph G(t) allows us to prove a weak version of the conjecture. Let us assume that v1> v2>··· > vn . Proposition 7.18. There exist a time t and a nonempty subset S⊂[n] such that S is isolated at time t . Proof . Let t be the minimum number for which the equation tv1−1 = tvn−1/n holds. This is the rst time that vn is at distance exactly 1/n ahead from the fastest runner v1 . For the sake of contradiction, assume that there is just one connected component of order n . Note that u1un/∈E(G(t)) and since G(t) is connected, there exists a path in G(t) connecting u1 and un . By (7.10), we have µ(G)<1 . Thus, there is a point x∈(0,1) such that x /∈Ii(t) for any i∈[n] . Observe that, at time t , all the intervals are sorted in increasing order around (0,1) . Let `∈[n] be such that x > {tv`} and x < {tv`+1} . Then, {u1, . . . , u`} and {u`+1, . . . , un} are in dierent connected components, since u1un, u`u`+1 /∈E(G(t)) . We observe that, if one of the parts in Proposition 7.18 consists of a singleton, say S={i} , then we would have showed Conjecture 7.15. Let us show how to apply the idea of the dynamic graph to prove an invisible lonely runner theorem, similar to Theorem 7.5. Proposition 7.19. There exists t∈(0,1) such that G(t) has either some isolated vertex or it has at least two vertices of degree one. Proof . Dene Y: (0,1) →N by, Y(t) := |E(G(t))|. Let t∈(0,1) be chosen uniformly at random. Then Y(t) is a random variable over 0,1,...,n 2 . We will show that E(Y(t)) ≤(n−1) . If we are able to do so, by a rst moment argument, we know that there exists a time t0 for which Y(t0)≤n−1 . Then, denoting by di the degree of ui , we have n X i=1 di≤2(n−1) , which, if di>0 for each i , ensures the existence of at least 2 vertices of degree one, concluding the proof of the proposition. Now, let us show that E(Y(t)) ≤(n−1) . We can write Y(t) = Pi<j Yij(t) , where Yij(t)=1 if ui and uj are connected at time t and Yij(t) = 0 otherwise. Then E(Y(t)) = Pi<j E(Yij) = 118 7.4. Concluding remarks and open questions Pi<j Pr(Ii(t)∩Ij(t)6=∅) . For the sake of simplicity when computing Pr(Ii(t)∩Ij(t)6=∅) , we can assume that vi= 0 . Since the intervals are half open, half closed, we have Pr(Ii(t)∩Ij(t)6= ∅) = 2/n , no matter the value of vj . Finally, E(Y(t)) = X i<j 2 n=n 22 n=n−1. In the dynamic interval graph setting, an invisible runner is equivalent to a vertex u with a neighbor of degree one, say v . If u is removed, then v becomes isolated in G(t) and thus, alone in the runner setting. Thus, Theorem 7.7 is a direct corollary of Proposition 7.19. 7.4 Concluding remarks and open questions 1. Using the same strategy as the proof of Theorem 7.4 one can show that it holds for some ε=ε(n)→0 . Consider γ=γ(n)→0 and m≤γn . We can nd a forest containing at least n−m= (1 −γ)n edges ij such that Pr(Ai∩Aj)≥(4 −2γ)δ2 . In this case, X ij∈E(T) Pr(Ai∩Aj)≥(4 −2γ)δ2(n−m) = (1 −O(γ))4δ2n . As in the proof of Theorem 7.4, we may set c= (1 −γ)−1 and α=γ−1 in Lemma 7.13 to apply Lemma 7.12. Then, the following inequality must be satised, logcαδ−1=m≤γn . Some technical but straightforward computations show that this inequality holds if γ is large enough, γ=γ(n)=Ω rlog n n!. Since γ= Θ(ε) in the proof of Theorem 7.4, we have that it holds for any ε= Ω qlog n n . 2. Proposition 7.3, shows that for δ=1 n+1 we have E(X2)≥(1+ O(n−1)) 4 + 2c log n . However, we think that the proof of this proposition can be adapted to show that the second moment of X is even larger. Conjecture 7.20. For any set of dierent speeds v1, . . . , vn , and δ=1 n+1 , we have E(X2)≥(1 + o(1))6 . The proof of this conjecture relies on showing that either most pairs are ε good or the contribution of the positive error terms is larger than the contribution of the negative ones. On the Chapter 7. On the Lonely Runner Conjecture 119 other hand, notice that E(X2) is not bounded from above by any constant. For the set of speeds in (7.1), Cilleruelo showed [38] that E(X2) = (1 + o(1))12 π2δn log n , (7.11) which is a Θ(log n) factor away from the lower bound in Proposition 7.3, when δ=1 n+1 . It is an open question whether (7.11) also holds as an upper bound for E(X2) . 3. Ideally, we would like to estimate the probabilities Pr(∩i∈SAi) , for every set S⊆[n] . In general, it is not easy to compute such probability. As in (7.11), the join probabilities cannot be upper bounded by any constant. However it is reasonable to think, that, for any set S of size s , we have Pr(∩i∈SAi)≥csδs, where cs depends only on s . Moreover, we know that cs≤2s , since this is the case when the speeds {vi}i∈S are rationally independent. Observation 7.10 shows that c2= 2 . Bibliography [1] F. A. Aagesen, C. Anutariya, and V. Wuwongse (eds.), Intelligence in communication systems, ip international conference, intellcomm 2004, bangkok, thailand, november 2326, 2004, proceedings , Lecture Notes in Computer Science, vol. 3283, Springer, 2004. [2] R. Aharoni, P. Charbit, and D. Howard, On a Generalization of the Ryser-Brualdi-Stein Conjecture , ArXiv e-prints (2013). [3] N. Alon, A note on network reliability , Discrete probability and algorithms (Minneapolis, MN, 1993), IMA Vol. Math. Appl., vol. 72, Springer, New York, 1995, pp. 1114. [4] , The chromatic number of random cayley graphs , to appear in European J. Combin. (2013). [5] N. Alon and E. Friedgut, On the number of permutations avoiding a given pattern , J. Combin. Theory Ser. A 89 (2000), 133140. [6] N. Alon, T. Jiang, Z. Miller, and D. Pritikin, Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints , Random Structures Algorithms 23 (2003), no. 4, 409433. [7] N. Alon and I. Z. Ruzsa, Non-averaging subsets and non-vanishing transversals , J. Combin. Theory Ser. A 86 (1999), no. 1, 113. [8] N. Alon and J. H. Spencer, The probabilistic method , third ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., Hoboken, NJ, 2008. [9] D. Angluin and L. G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings , Proceedings of the ninth annual ACM symposium on Theory of computing (New York, NY, USA), STOC '77, ACM, 1977, pp. 3041. [10] B. Arsovski, A proof of Snevily's conjecture , Israel J. Math. 182 (2011), 505508. [11] D. Auger, I. Charon, O. Hudry, and A. Lobstein, Maximum size of a minimum watching system and the graphs achieving the bound , to appear in Discrete Appl. Math. (2013). [12] , Watching systems in graphs: An extension of identifying codes , Discrete Appl. Math. 161 (2013), no. 12, 16741685. [13] J. Barajas and O. Serra, The lonely runner with seven runners , Electron. J. Combin. 15 (2008), no. 1, Paper 48, 18 pp. [14] J. Beck, An algorithmic approach to the Lovász local lemma. I , Random Structures Algorithms 2 (1991), no. 4, 343365. [15] E. A. Bender and E. R. Caneld, The asymptotic number of labeled graphs with given degree sequences , J. Combin. Theory Ser. A 24 (1978), no. 3, 296  307. 121 122 Bibliography [16] N. Bertrand, Codes identiants et codes localisateurs-dominateurs sur certains graphes , Master's thesis, ENST, Paris, France, June 2001. [17] N. Bertrand, I. Charon, O. Hudry, and A. Lobstein, 1-identifying codes on trees , Australas. J. Combin. 31 (2005), 2135. [18] U. Betke and J. M. Wills, Untere Schranken für zwei diophantische ApproximationsFunktionen , Monatsh. Math. 76 (1972), 214217. [19] W. Bienia, L. Goddyn, P. Gvozdjak, A. Seb®, and M. Tarsi, Flows, view obstructions, and the lonely runner , J. Combin. Theory Ser. B 72 (1998), no. 1, 19. [20] R. Bissacot, R. Fernández, A. Procacci, and B. Scoppola, An improvement of the Lovász local lemma via cluster expansion , Combin. Probab. Comput. 20 (2011), no. 5, 709719. [21] T. Bohman, R. Holzman, and D. Kleitman, Six lonely runners , Electron. J. Combin. 8 (2001), no. 2, Paper 3, 49 pp. [22] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs , European J. Combin. 1 (1980), 311316. [23] B. Bollobás, Random graphs , Academic Press Inc., London, 1985. [24] B. Bollobas, D. Mitsche, and P. Pralat, Metric dimension for random graphs , ArXiv eprints (2012). [25] M. Bóna, Exact and Asymptotic Enumeration of Permutations with Subsequence Conditions , ProQuest LLC, Ann Arbor, MI, 1997, Thesis (Ph.D.)Massachusetts Institute of Technology. [26] , Non-overlapping permutation patterns , Pure Math. Appl. (PU.M.A.) 22 (2011), 99105. [27] , Combinatorics of permutations , second ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2012. [28] J. A. Bondy, Induced subsets , J. Combin. Theory Ser. B 12 (1972), 201202. [29] K. M. J. Bontridder, B. V. Halldórsson, M. M. Halldórsson, C. A. J. Hurkens, J. K. Lenstra, R. Ravi, and L. Stougie, Approximation algorithms for the test cover problem , Math. Program. 98 (2003), no. 1-3, 477491. [30] S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A nonasymptotic theory of independence. , Oxford University Press, Oxford, 2013. [31] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2 + 2) -free posets, ascent sequences and pattern avoiding permutations , J. Combin. Theory Ser. A 117 (2010), no. 7, 884909. [32] N. J. Cavenagh, C. Greenhill, and I. M. Wanless, The cycle structure of two rows in a random Latin square , Random Structures Algorithms 33 (2008), no. 3, 286309. [33] I. Charon, I. Honkala, O. Hudry, and A. Lobstein, Minimum sizes of identifying codes in graphs diering by one vertex , Cryptogr. Commun. 5 (2013), no. 2, 119136. [34] I. Charon, O. Hudry, and A. Lobstein, Extremal cardinalities for identifying and locatingdominating codes in graphs , Discrete Math. 307 (2007), no. 3-5, 356366. Bibliography 129