Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T19:09:31.676Z 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: [email protected])
TOM BOHMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: [email protected])
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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