A quantitative Lovász criterion for Property B. (7th November 2020)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Shapira, Asaf
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 6(2020)
• Page Start: 956
• Page End: 960
• Publication Date: 2020-11-07
• Subjects: 05C12; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000334
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: A well-known observation of Lovász is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lovász's criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable n -uniform hypergraph. Our main result is an exact answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollobás's two families theorem with Pluhar's randomized colouring algorithm.