Hypergraph independent sets

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)9-20
Number of pages12
JournalCombinatorics Probability and Computing
Volume22
Issue number1
DOIs
StatePublished - Jan 2013

Fingerprint

Dive into the research topics of 'Hypergraph independent sets'. Together they form a unique fingerprint.

Cite this