Premium
On uncrowded hypergraphs
Author(s) -
Duke Richard A.,
Lefmann Hanno,
Rödl Vojtech
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060208
Subject(s) - hypergraph , combinatorics , conjecture , mathematics , independence number , degree (music) , discrete mathematics , physics , graph , acoustics
In this note we will show that every k —uniform hypergraph ℋ on n vertices with average degree i k‐1 containing no 2—cycles has independence number α(ℋ)≧c k n/t (ln t ) 1/(k‐1) for t ≧ t 0 ( k ). This confirms a conjecture of Spencer. © 1995 John Wiley & Sons, Inc.