Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-11T22:01:44.882Z Has data issue: false hasContentIssue false
  • English
  • Français

A quantitative Lovász criterion for Property B

Part of: Graph theory

Published online by Cambridge University Press:  07 August 2020

Asaf Ferber  and
Asaf Shapira
Asaf Ferber*
Affiliation:
Department of Mathematics, University of California, Irvine
Asaf Shapira
Affiliation:
School of Mathematics, Tel Aviv University, Tel Aviv69978, Israel
*
*Corresponding author. Email: asaff@uci.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

MSC classification

Primary: 05C12: Distance in graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 6 , November 2020 , pp. 956 - 960
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

†

Supported in part by an NSF grant DMS-1954395.

‡

Supported in part by ISF Grant 1028/16 and ERC Starting Grant 633509.

References

Alon, N. and Spencer, J. (1992) The Probabilistic Method. Wiley.Google Scholar
Bernstein, F. (1908) Zur Theorie der trigonometrische Reihen. Leipz. Ber. 60 325–328.Google Scholar
Bollobás, B. (1965) On generalized graphs. Acta Math. Acad. Sci. Hungar. 16 447–452.CrossRefGoogle Scholar
Cherkashin, D. and Kozik, J. (2015) A note on random greedy coloring of uniform hypergraphs. Random Struct. Algorithms 47 407–413.CrossRefGoogle Scholar
Lovász, L. (1979) Combinatorial Problems and Exercises. North-Holland.Google Scholar
Miller, E. W. (1937) On a property of families of sets. Comput. Rend. Varsovie 30 31–38.Google Scholar
Pluhar, A. (2009) Greedy colorings of uniform hypergraphs. Random Struct. Algorithms 35 216–221.CrossRefGoogle Scholar
Seymour, P. (1974) On the two-colouring of hypergraphs. Quart. J. Math. Oxford 25 303–312.CrossRefGoogle Scholar