Hypergraphs with independent neighborhoods |
| |
| Authors: | Tom Bohman Alan Frieze Dhruv Mubayi Oleg Pikhurko |
| |
| Institution: | 1. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
2. Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, IL, 60607, USA
|
| |
| Abstract: | For each k ≥ 2, let ρ
k
∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ
k
+ o(1))(
k
n
) edges as n → ∞. We prove that ρ
k
= 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
