𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Ramsey Properties of Random Hypergraphs

✍ Scribed by Vojtech Rödl; Andrzej Ruciński

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
501 KB
Volume
81
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

Let K (k) (n, p) be the random k-uniform hypergraph obtained by independent inclusion of each of the ( n k ) k-tuples with probability p. For an arbitrary k-uniform hypergraph G and every integer r we find the threshold for the property that every r-coloring of the vertices of K (k) (n, p) results in a monochromatic copy of G. In the edge coloring case, which is of our main interest, we find the threshold only for k=3, r=2, and G=K 3 4 . In the proof we utilize a recent version of the hypergraph regularity lemma due to Frankl and Ro dl.

📜 SIMILAR VOLUMES

Ramsey properties of random graphs
Ramsey properties of random graphs
✍ Tomasz Luczak; Andrzej Ruciński; Bernd Voigt 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 917 KB
The chromatic numbers of random hypergra
The chromatic numbers of random hypergraphs
✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

New Lower Bounds for Ramsey Numbers of G
New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs
✍ Felix Lazebnik; Dhruv Mubayi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 146 KB 👁 1 views

## dedicated to the memory of rodica simion Let G be an r-uniform hypergraph. The multicolor Ramsey number r k G is the minimum n such that every k-coloring of the edges of the complete r-uniform hypergraph K r n yields a monochromatic copy of G. Improving slightly upon results from M. Axenovich,

On testing the ‘pseudo-randomness’ of a
On testing the ‘pseudo-randomness’ of a hypergraph
✍ Julie Haviland; Andrew Thomason 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Haviland, J. and A. Thomason, On testing the 'pseudo-randomness' of a hypergraph, Discrete Mathematics 103 (1992) 321-327. By Haviland and Thomason (1989) a definition for a pseudo-random hypergraph was proposed, and the resemblance between these pseudo-random hypergraphs and random hypergraphs was