Name
Abstract | ||
|---|---|---|
An (n, r, s)-system is an r-uniform hypergraph on n vertices such that every pair of edges has an intersection of size less than s. Using probabilistic arguments, Rodl and Sinajova showed that for all fixed integers r > s >= 2, there exists an (n, r, s)-systern with independence number O (n(1-delta+o(1))) for some optimal constant delta > 0 only related to r and s. We show that for certain pairs (r, s) with s <= r/2 there exists an explicit construction of an (n, r, s)-system with independence number O (n(1-epsilon)), where epsilon > 0 is an absolute constant only related to r and s. Previously this was known only for s > r/2 by results of Chattopadhyay and Goodman. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.37236/10513 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 29 | 1 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xizhi Liu | 1 | 0 | 1.35 |
| Dhruv Mubayi | 2 | 0 | 0.68 |