Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties
For fixed graphs , we prove an upper bound on the threshold function for the property that . This establishes the -statement of a conjecture of Kohayakawa and Kreuter.
Source author record
Frank Mousset
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
9works
4topics
4close collaborators
Published work
9 publications
preprint2016arXiv
A general lower bound for collaborative tree exploration
We consider collaborative graph exploration with a set of k agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other vertices. We assume agents are deterministic, vertices are distinguishable, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small (k≤n) and large (k≥n) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains. First, we significantly extend a lower bound of Ω(logk/loglogk) by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range k≤nlogcn for any c∈N. Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with k=Dn1+o(1) agents has a competitive ratio of ω(1), while Dereniowski et al. gave an algorithm with k=Dn1+ε agents and competitive ratio O(1), for any ε>0 and with D denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using k=n agents, there exist trees of arbitrarily large height D that require Ω(D2) rounds, and we provide a simple algorithm that matches this bound for all trees.
Open access
preprint2016arXiv
A tight Erdős-Pósa function for long cycles
A classic result of Erdős and Pósa says that any graph contains either k vertex-disjoint cycles or can be made acyclic by deleting at most O(klogk) vertices. Here we generalize this result by showing that for all numbers k and l and for every graph G, either G contains k vertex-disjoint cycles of length at least l, or there exists a set X of O(kl+klogk) vertices that meets all cycles of length at least l in G. As a corollary, the tree-width of any graph G that does not contain k vertex-disjoint cycles of length at least l is of order O(kl+klogk). These results improve on the work of Birmelé, Bondy and Reed '07 and Fiorini and Herinckx '14 and are optimal up to constant factors.
Open access
preprint2016arXiv
Packing spanning graphs from separable families
Let G be a separable family of graphs. Then for all positive constants ε and Δ and for every sufficiently large integer n, every sequence G1,…,Gt∈G of graphs of order n and maximum degree at most Δ such that e(G1)+⋯+e(Gt)≤(1−ε)(2n) packs into Kn. This improves results of Böttcher, Hladký, Piguet, and Taraz when G is the class of trees and of Messuti, Rödl, and Schacht in the case of a general separable family. The result also implies approximate versions of the Oberwolfach problem and of the Tree Packing Conjecture of Gyárfás (1976) for the case that all trees have maximum degree at most Δ. The proof uses the local resilience of random graphs and a special multi-stage packing procedure.
Open access
preprint2015arXiv
Bootstrap percolation with inhibition
Bootstrap percolation is a prominent framework for studying the spreading of activity on a graph. We begin with an initial set of active vertices. The process then proceeds in rounds, and further vertices become active as soon as they have a certain number of active neighbors. A recurring feature in bootstrap percolation theory is an `all-or-nothing' phenomenon: either the size of the starting set is so small that the process stops very soon, or it percolates (almost) completely. Motivated by several important phenomena observed in various types of real-world networks we propose in this work a variant of bootstrap percolation that exhibits a vastly different behavior. Our graphs have two types of vertices: some of them obstruct the diffusion, while the others facilitate it. We study the effect of this setting by analyzing the process on Erdős-Rényi random graphs. Our main findings are two-fold. First we show that the presence of vertices hindering the diffusion does not result in a stable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. In particular, the process is non-monotone: a larger starting set can result in a smaller final set. In the second part of the paper we show that this phenomenom arises from the round-based approach: if we move to a continuous time model in which every edge draws its transmission time randomly, then we gain stability, and the process stops with an active set that contains a non-trivial constant fraction of all vertices. Moreover, we show that in the continuous time model percolation occurs significantly faster compared to the classical round-based model. Our findings are in line with empirical observations and demonstrate the importance of introducing various types of vertex behaviors in the mathematical model.
Open access
preprint2014arXiv
Connectivity Thresholds for Bounded Size Rules
In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round d≥1 edges are drawn uniformly at random, and using some rule exactly one of them is chosen and added to the evolving graph. For the class of Achlioptas processes we investigate how much impact the rule has on one of the most basic properties of a graph: connectivity. Our main results are twofold. First, we study the prominent class of bounded size rules, which select the edge to add according to the component sizes of its vertices, treating all sizes larger than some constant equally. For such rules we provide a fine analysis that exposes the limiting distribution of the number of rounds until the graph gets connected, and we give a detailed picture of the dynamics of the formation of the single component from smaller components. Second, our results allow us to study the connectivity transition of all Achlioptas processes, in the sense that we identify a process that accelerates it as much as possible.
Open access
preprint2014arXiv
On the number of graphs without large cliques
In 1976 Erdos, Kleitman and Rothschild determined the number of graphs without a clique of size ℓ. In this note we extend their result to the case of forbidden cliques of increasing size. More precisely we prove that for ℓn≤21(logn)1/4 there are 2(1−1/(ℓn−1))n2/2+o(n2/ℓn) Kℓn-free graphs of order n. Our proof is based on the recent hypergraph container theorems of Saxton, Thomason and Balogh, Morris, Samotij, in combination with a theorem of Lovasz and Simonovits.
Open access
preprint2014arXiv
Packing a randomly edge-colored random graph with rainbow k-outs
Let G be a graph on n vertices and let k be a fixed positive integer. We denote by $\mathcal G_{\text{$k$-out}}(G)$ the probability space consisting of subgraphs of G where each vertex v∈V(G) randomly picks k neighbors from G, independently from all other vertices. We show that if δ(G)=ω(logn) and k≥2, then the following holds for every p=ω(logn/δ(G)). Let H be a random graph obtained by keeping each e∈E(G) with probability p independently at random and then coloring its edges independently and uniformly at random with elements from the set [kn]. Then, w.h.p. H contains t:=(1−o(1))δ(G)p/(2k) edge-disjoint graphs H1,...,Ht such that each of the Hi is \emph{rainbow} (that is, all the edges are colored with distinct colors), and such that for every monotone increasing property of graphs P and for every 1≤i≤t we have $\Pr[\mathcal G_{\text{$k$-out}}(G)\models \mathcal P]\leq \Pr[H_i\models \mathcal P]+n^{-ω(1)}$. Note that since (in this case) a typical member of $\mathcal G_{\text{$k$-out}}(G)$ has average degree roughly 2k, this result is asymptotically best possible. We present several applications of this; for example, we use this result to prove that for p=ω(logn/n) and c=23n, a graph H∼Gc(Kn,p) w.h.p. contains (1−o(1))np/46 edge-disjoint rainbow Hamilton cycles. More generally, using a recent result of Frieze and Johansson, the same method allows us to prove that if G has minimum degree δ(G)≥(1+ε)n/2, then there exist functions c=O(n) and t=Θ(np) (depending on ε) such that the random subgraph H∼Gc(G,p) w.h.p. contains t edge-disjoint rainbow Hamilton cycles.
Open access
preprint2012arXiv
On Rainbow Cycles and Paths
In a properly edge colored graph, a subgraph using every color at most once is called rainbow. In this thesis, we study rainbow cycles and paths in proper edge colorings of complete graphs, and we prove that in every proper edge coloring of K_n, there is a rainbow path on (3/4-o(1))n vertices, improving on the previously best bound of (2n+1)/3 from Gyarfas and Mhalla. Similarly, a k-rainbow path in a proper edge coloring of K_n is a path using no color more than k times. We prove that in every proper edge coloring of K_n, there is a k-rainbow path on (1-2/(k+1)!)n vertices.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.