Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T08:02:00.140Z Has data issue: false hasContentIssue false
  • English
  • Français

Erdős–Ko–Rado in Random Hypergraphs

Published online by Cambridge University Press:  01 September 2009

JÓZSEF BALOGH ,
TOM BOHMAN  and
DHRUV MUBAYI
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: jobal@math.uiuc.edu)
TOM BOHMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@math.cmu.edu)
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: mubayi@math.uic.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let 3 ≤ k < n/2. We prove the analogue of the Erdős–Ko–Rado theorem for the random k-uniform hypergraph Gk(n, p) when k < (n/2)1/3; that is, we show that with probability tending to 1 as n → ∞, the maximum size of an intersecting subfamily of Gk(n, p) is the size of a maximum trivial family. The analogue of the Erdős–Ko–Rado theorem does not hold for all p when k ≫ n1/3.

We give quite precise results for k < n1/2−ϵ. For larger k we show that the random Erdős–Ko–Rado theorem holds as long as p is not too small, and fails to hold for a wide range of smaller values of p. Along the way, we prove that every non-trivial intersecting k-uniform hypergraph can be covered by k2 − k + 1 pairs, which is sharp as evidenced by projective planes. This improves upon a result of Sanders [7]. Several open questions remain.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 5: New Directions in Algorithms, Combinatorics and Optimization , September 2009 , pp. 629 - 646
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. and Spencer, J. H. (2000) The Probabilistic Method, 2nd edn, Wiley, New York.CrossRefGoogle Scholar
[2]Bollobás, B. (2001) Random Graphs, 2nd edn, Cambridge University Press.CrossRefGoogle Scholar
[3]Bohman, T., Cooper, C., Frieze, A., Martin, R. and Ruszinkó, M. (2003) On randomly generated intersecting hypergraphs. Electron. J. Combin. 10 #29.CrossRefGoogle Scholar
[4]Bohman, T., Frieze, A., Martin, R. and Ruszinkó, M. (2007) On randomly generated intersecting hypergraphs II. Random Struct. Alg. 30 17–34.CrossRefGoogle Scholar
[5]Erdős, P., Ko, C. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2 12 313–320.CrossRefGoogle Scholar
[6]Kohayakawa, Y., Łuczak, T. and Rödl, V. (1997) On K 4-free subgraphs of random graphs. Combinatorica 17 173–213.CrossRefGoogle Scholar
[7]Sanders, A. J. (2004) Covering by intersecting families. J. Combin. Theory Ser. A 108 51–61.CrossRefGoogle Scholar
[8]Szabó, T. and Vu, V. H. (2003) Turán's theorem in sparse random graphs. Random Struct. Alg. 23 225–234.CrossRefGoogle Scholar