共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
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 相似文献
3.
4.
Peter Allen Julia Bttcher Jozef Skokan Maya Stein 《Random Structures and Algorithms》2020,56(2):306-338
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. 相似文献
5.
Fabrıcio Siqueira Benevides 《Journal of Graph Theory》2012,71(3):293-316
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 n0 such that if n?n0 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 相似文献
6.
7.
S?awomir Solecki 《Journal of Combinatorial Theory, Series A》2012,119(2):440-449
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. 相似文献
8.
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 Cn and paths Pn on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc. 相似文献
9.
《Journal of Graph Theory》2018,87(2):176-187
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. 相似文献
10.
11.
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 Kn, 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=K3 and H is a cycle of a fixed length. 相似文献
12.
P.E. Haxell 《Journal of Combinatorial Theory, Series A》2006,113(1):67-83
Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible. 相似文献
13.
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. 相似文献
14.
Andreas Noever 《Random Structures and Algorithms》2017,50(3):464-492
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 相似文献
15.
16.
Bernd Kreuter 《Random Structures and Algorithms》1996,9(3):335-348
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. 相似文献
17.
We prove that the chromatic Ramsey number of every odd wheel W2k+ 1, k?2 is 14. That is, for every odd wheel W2k+ 1, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W2k+ 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 相似文献
18.
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]. 相似文献
19.
20.
《Random Structures and Algorithms》2018,52(1):3-40
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. 相似文献