Extremal uncrowded hypergraphs

M. Ajtai; J. Komlós; J. Pintz; J. Spencer; E. Szemerédi

doi:10.1016/0097-3165(82)90049-8

Extremal uncrowded hypergraphs

M. Ajtai, J. Komlós, J. Pintz, J. Spencer, E. Szemerédi

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ≪ t ≪ n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size c_k( n t)(ln t)^{1 k}.

Original language	English (US)
Pages (from-to)	321-335
Number of pages	15
Journal	Journal of Combinatorial Theory, Series A
Volume	32
Issue number	3
DOIs	https://doi.org/10.1016/0097-3165(82)90049-8
State	Published - May 1982

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(82)90049-8

Cite this

@article{47a42d5a60be4fa78dc1114c17c3cc04,

title = "Extremal uncrowded hypergraphs",

abstract = "Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ≪ t ≪ n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size ck( n t)(ln t) 1 k.",

author = "M. Ajtai and J. Koml{\'o}s and J. Pintz and J. Spencer and E. Szemer{\'e}di",

year = "1982",

month = may,

doi = "10.1016/0097-3165(82)90049-8",

language = "English (US)",

volume = "32",

pages = "321--335",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Extremal uncrowded hypergraphs

AU - Ajtai, M.

AU - Komlós, J.

AU - Pintz, J.

AU - Spencer, J.

AU - Szemerédi, E.

PY - 1982/5

Y1 - 1982/5

N2 - Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ≪ t ≪ n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size ck( n t)(ln t) 1 k.

AB - Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ≪ t ≪ n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size ck( n t)(ln t) 1 k.

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

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

U2 - 10.1016/0097-3165(82)90049-8

DO - 10.1016/0097-3165(82)90049-8

M3 - Article

AN - SCOPUS:0000916941

SN - 0097-3165

VL - 32

SP - 321

EP - 335

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 3

ER -

Extremal uncrowded hypergraphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this