Back to Search
Start Over
A quantitative Lov\'asz criterion for Property B
- Source :
- Combinator. Probab. Comp. 29 (2020) 956-960
- Publication Year :
- 2019
-
Abstract
- A well known observation of Lov\'asz is that if a hypergraph is not $2$-colorable, then at least one pair of its edges intersect at a single vertex. %This very simple criterion turned out to be extremly useful . In this short paper we consider the quantitative version of Lov\'asz's criterion. That is, we ask how many pairs of edges intersecting at a single vertex, should belong to a non $2$-colorable $n$-uniform hypergraph? Our main result is an {\em exact} answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollob\'as's two families theorem with Pluhar's randomized coloring algorithm.<br />Comment: A note on Property B
- Subjects :
- Mathematics - Combinatorics
05D05
Subjects
Details
- Database :
- arXiv
- Journal :
- Combinator. Probab. Comp. 29 (2020) 956-960
- Publication Type :
- Report
- Accession number :
- edsarx.1903.04968
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1017/S0963548320000334