Hypergraph independent sets

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

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 - 1 Jan 2013

Fingerprint

Independent Set
Hypergraph
Uniform Hypergraph
Regularity Lemma
Extremal Problems
Strictly
Intersection
Upper bound
Imply
Subset
Theorem

Cite this

Cutler, Jonathan ; Radcliffe, A. J. / Hypergraph independent sets. In: Combinatorics Probability and Computing. 2013 ; Vol. 22, No. 1. pp. 9-20.
@article{5f66dd80c8ed412881fe018d9f7402d6,
title = "Hypergraph independent sets",
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.",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2013",
month = "1",
day = "1",
doi = "10.1017/S0963548312000454",
language = "English",
volume = "22",
pages = "9--20",
journal = "Combinatorics Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "1",

}

Hypergraph independent sets. / Cutler, Jonathan; Radcliffe, A. J.

In: Combinatorics Probability and Computing, Vol. 22, No. 1, 01.01.2013, p. 9-20.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Hypergraph independent sets

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84870920550&partnerID=8YFLogxK

U2 - 10.1017/S0963548312000454

DO - 10.1017/S0963548312000454

M3 - Article

VL - 22

SP - 9

EP - 20

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 1

ER -