Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419336 | Discrete Applied Mathematics | 2014 | 4 Pages |
Abstract
Chen and Chvátal introduced the notion of lines in hypergraphs; they proved that every 33-uniform hypergraph with nn vertices either has a line that consists of all nn vertices or else has at least log2nlog2n distinct lines. We improve this lower bound by a factor of 2−o(1)2−o(1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pierre Aboulker, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Vašek Chvátal, Peihan Miao,