Extremal uncrowded hypergraphs

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)321-335
Number of pages15
JournalJournal of Combinatorial Theory, Series A
Issue number3
StatePublished - May 1982

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Extremal uncrowded hypergraphs'. Together they form a unique fingerprint.

Cite this