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

Hypergraph Independent Sets

Published online by Cambridge University Press:  11 October 2012

JONATHAN CUTLER  and
A. J. RADCLIFFE
JONATHAN CUTLER
Affiliation:
Department of Mathematical Sciences, Montclair State University, Montclair, NJ 07043, USA (e-mail: jonathan.cutler@montclair.edu)
A. J. RADCLIFFE
Affiliation:
Department of Mathematics, University of Nebraska–Lincoln, Lincoln, NE 68588-0130, USA (e-mail: aradcliffe1@math.unl.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.

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices is j-independent if its intersection with any edge has size strictly less than j. The Kruskal–Katona theorem implies that in an r-uniform hypergraph with a fixed size and order, the hypergraph with the most r-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number of j-independent sets in an r-uniform hypergraph.

Keywords

Primary 05C65Secondary 05D05, 05C69

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 1 , January 2013 , pp. 9 - 20
Copyright
Copyright © Cambridge University Press 2012

References

[1]Chung, F. R. K. (1991) Regularity lemmas for hypergraphs and quasi-randomness. Random Struct. Alg. 2 241–252.CrossRefGoogle Scholar
[2]Cutler, J. and Radcliffe, A. J. (2011) Extremal problems for independent set enumeration. Electron. J. Combin. 18 #R169.CrossRefGoogle Scholar
[3]Czygrinow, A. and Rödl, V. (2000) An algorithmic regularity lemma for hypergraphs. SIAM J. Comput. 30 1041–1066.Google Scholar
[4]Frieze, A. and Kannan, R. (1999) Quick approximation to matrices and applications. Combinatorica 19 175–220.Google Scholar
[5]Gowers, W. T. (2006) Quasirandomness, counting and regularity for 3-uniform hypergraphs. Combin. Probab. Comput. 15 143–184.Google Scholar
[6]Gowers, W. T. (2007) Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. of Math. (2) 166 897–946.CrossRefGoogle Scholar
[7]Kahn, J. (2001) An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10 219–237.CrossRefGoogle Scholar
[8]Katona, G. (1968) A theorem of finite sets. In Theory of Graphs: Proc. Colloq., Tihany, 1966, Academic Press, pp. 187–207.Google Scholar
[9]Kruskal, J. B. (1963) The number of simplices in a complex. In Mathematical Optimization Techniques (Bellman, R., ed.), University of California Press, pp. 251–278.Google Scholar
[10]Loh, P.-S., Pikhurko, O. and Sudakov, B. (2010) Maximizing the number of q-colorings. Proc. London Math. Soc. 101 655–696.Google Scholar
[11]Rödl, V., Nagle, B., Skokan, J., Schacht, M. and Kohayakawa, Y. (2005) The hypergraph regularity method and its applications. Proc. Natl. Acad. Sci. USA 102 8109–8113.Google Scholar
[12]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399–401.Google Scholar
[13]Tao, T. (2006) A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 1257–1280.Google Scholar
[14]Yuster, R. (2006) Finding and counting cliques and independent sets in r-uniform hypergraphs. Inform. Process. Lett. 99 130–134.Google Scholar
[15]Zhao, Y. (2010) The number of independent sets in a regular graph. Combin. Probab. Comput. 19 315–320.Google Scholar