Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

Regular pairs in sparse random graphs I

We consider bipartite subgraphs of sparse random graphs that are regular in the sense of Szemerédi and, among other things, show that they must satisfy a certain local pseudorandom property. This property and its consequences turn out to be useful when considering embedding problems in subgraphs of sparse random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 359–434, 2003     

Regularity inheritance in pseudorandom graphs

Advancing the sparse regularity method, we prove one‐sided and two‐sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved H‐counting lemmas for subgraphs of bijumbled graphs, for some H.     

A multipartite Ramsey number for odd cycles

In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n₀ such that if n?n₀ is a positive odd integer then any two‐coloring of the edges of the complete five‐partite graph K_{(n ? 1)/2, (n ? 1)/2, (n ? 1)/2, (n ? 1)/2, 1} contains a monochromatic cycle of length n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Direct Ramsey theorem for structures involving relations and functions

We prove the direct structural Ramsey theorem for structures with relations as well as functions. The result extends the theorem of Abramson and Harrington and of Nešet?il and Rödl.     

Ramsey unsaturated and saturated graphs

A graph is Ramsey unsaturated if there exists a proper supergraph of the same order with the same Ramsey number, and Ramsey saturated otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles C_n and paths P_n on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc.     

On an anti‐Ramsey threshold for sparse graphs with one triangle

For graphs G and H, let  denote the property that for every proper edge‐coloring of G (with an arbitrary number of colors) there is a rainbow copy of H in G, that is, a copy of H with no two edges of the same color. The authors (2014) proved that, for every graph H, the threshold function  of this property for the binomial random graph  is asymptotically at most , where denotes the so‐called maximum 2‐density of H. Nenadov et al. (2014) proved that if H is a cycle with at least  seven vertices or a complete graph with at least 19 vertices, then . We show that there exists a fairly rich, infinite family of graphs F containing a triangle such that if for suitable constants and , where , then almost surely. In particular, for any such graph F.     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

The Ramsey number for hypergraph cycles I

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁,…,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,…,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C_n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.     

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.     

Online Ramsey games for more than two colors

Consider the following one‐player game played on an initially empty graph with n vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of r available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph F. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of 2‐balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 464–492, 2017     

Threshold functions for asymmetric Ramsey properties with respect to vertex colorings

In this note we investigate Ramsey properties of random graphs. The threshold functions for symmetric Ramsey properties with respect to vertex colorings were determined by Łuczak, Ruciński, and Voigt [6]. As a generalization of this problem we consider asymmetric Ramsey properties and establish the values of the threshold functions. Furthermore, we investigate canonical colorings. © 1996 John Wiley & Sons, Inc.     

The chromatic Ramsey number of odd wheels

We prove that the chromatic Ramsey number of every odd wheel W_{2k+ 1}, k?2 is 14. That is, for every odd wheel W_{2k+ 1}, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W_{2k+ 1} in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012     

Online Ramsey theory for a triangle on -free graphs

Given a class of graphs and a fixed graph , the online Ramsey game for H on is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of forever, and we say Painter wins the game. We initiate the study of characterizing the graphs such that for a given graph , Painter wins the online Ramsey game for on -free graphs. We characterize all graphs such that Painter wins the online Ramsey game for on the class of -free graphs, except when is one particular graph. We also show that Painter wins the online Ramsey game for on the class of -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].     

Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

For a given graph F we consider the family of (finite) graphs G with the Ramsey property for F, that is the set of such graphs G with the property that every two‐coloring of the edges of G yields a monochromatic copy of F. For F being a triangle Friedgut, Rödl, Ruciński, and Tetali (2004) established the sharp threshold for the Ramsey property in random graphs. We present a simpler proof of this result which extends to a more general class of graphs F including all cycles. The proof is based on Friedgut's criteria (1999) for sharp thresholds and on the recently developed container method for independent sets in hypergraphs by Saxton and Thomason and by Balogh, Morris and Samotij. The proof builds on some recent work of Friedgut et al. who established a similar result for van der Waerden's theorem.