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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics