Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-06T00:14:16.991Z Has data issue: false hasContentIssue false
  • English
  • Français

Simple Containers for Simple Hypergraphs

Part of: Graph theory

Published online by Cambridge University Press:  17 August 2015

DAVID SAXTON  and
ANDREW THOMASON
DAVID SAXTON
Affiliation:
IMPA, Estrada Dona Castorina 110, Rio de Janeiro, Brasil 22460-320 (e-mail: saxton@impa.br)
ANDREW THOMASON
Affiliation:
DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: A.G.Thomason@dpmms.cam.ac.uk)
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.

We give an easy method for constructing containers for simple hypergraphs. The method also has consequences for non-simple hypergraphs. Some applications are given; in particular, a very transparent calculation is offered for the number of H-free hypergraphs, where H is some fixed uniform hypergraph.

MSC classification

Primary: 05C65: Hypergraphs
Secondary: 05C35: Extremal problems

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 3 , May 2016 , pp. 448 - 459
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Balogh, J., Morris, R. and Samotij, W. Independent sets in hypergraphs. J. Amer. Math. Soc. 28 (2015), 669–709.Google Scholar
[2] Bollobás, B. and Thomason, A. (2000) The structure of hereditary properties and colourings of random graphs. Combinatorica 20 173–202.Google Scholar
[3] Conlon, D. and Gowers, W. T. Combinatorial theorems in sparse random sets. arXiv:1011.4310 Google Scholar
[4] Dotson, R. and Nagle, B. (2009) Hereditary properties of hypergraphs. J. Combin. Theory Ser. B 99 460–473.CrossRefGoogle Scholar
[5] Erdős, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.Google Scholar
[6] Erdős, P., Kleitman, D. J. and Rothschild, B. L. (1976) Asymptotic enumeration of Kn -free graphs. In Colloquio Internazionale sulle Teorie Combinatorie (Rome 1973), Vol. 2, pp. 19–27.Google Scholar
[7] Erdős, P. and Simonovits, M. (1983) Supersaturated graphs and hypergraphs. Combinatorica 3 181–192.CrossRefGoogle Scholar
[8] Kohayakawa, Y., Łczak, T. and Rödl, V. (1997) On K 4-free subgraphs of random graphs. Combinatorica 17 173–213.Google Scholar
[9] Kohayakawa, Y., Rödl, V. and Schacht, M. (2004) The Turán theorem for random graphs. Combin. Probab. Comput. 13 61–91.CrossRefGoogle Scholar
[10] Marchant, E. and Thomason, A. (2011) The structure of hereditary properties and 2-coloured multigraphs. Combinatorica 31 85–93.CrossRefGoogle Scholar
[11] Janson, S., Łczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[12] Nagle, B., Rödl, V. and Schacht, M. (2006) Extremal hypergraph problems and the regularity method. In Topics in Discrete Mathematics, Algorithms Combin. 26 247–278.Google Scholar
[13] Prömel, H.-J. and Steger, A. (1992) Excluding induced subgraphs III: A general asymptotic. Random Struct. Alg. 3 19–31.CrossRefGoogle Scholar
[14] Saxton, D. and Thomason, A. (2012) List colourings of regular hypergraphs. Combin. Probab. Comput. 21 315–322.Google Scholar
[15] Saxton, D. and Thomason, A. Hypergraph containers. Inventio Math. DOI 10.1007/s00222-014-0562-8.Google Scholar
[16] Schacht, M. Extremal results for random discrete structures. Submitted.Google Scholar
[17] Szabó, T. and Vu, V. H. (2003) Turán's theorem in sparse random graphs. Random Struct. Alg. 23 225–234.CrossRefGoogle Scholar