Name
Abstract | ||
|---|---|---|
AbstractThe independence numberαH of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if Hn is an n-vertex r+1-uniform hypergraph in which every r-element set is contained in at most d edges, where 00 satisfies cr~r/e as rï ∞. The value of cr improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi J Comb Theory Ser A 32 1982, 321-335. Our relatively short proof extends a method due to Shearer Random Struct Algorithms 7 1995, 269-271 and Alon Random Struct Algorithms 9 1996, 271-278. The above statement is close to best possible, in the sense that for each rï 2 and all values of d∈ï , there are infinitely many Hn such thatαHnï brndlogï nd1/rwhere br>0 depends only on r. In addition, for many values of d we show br~cr as rï ∞, so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224-239, 2014 |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/rsa.20453 | Periodicals |
Keywords | Field | DocType |
independent sets,hypergraphs,steiner systems | Steiner systems,Discrete mathematics,Combinatorics,Vertex (geometry),struct,Constraint graph,Hypergraph,Ramsey's theorem,Mathematics | Journal |
Volume | Issue | ISSN |
44 | 2 | 1042-9832 |
Citations | PageRank | References |
3 | 0.51 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Dhruv Mubayi | 2 | 579 | 73.95 |
| Jacques Verstraëte | 3 | 192 | 26.99 |