Chvátal's Conjecture and the Holroyd-Talbot Conjecture


The event is taking part on the Tuesday, Oct 22nd 2019 at 15.30
Theme/s: Pure and Applied Colloquia, Pure Maths
Location of Event: 306 Alan Turing
This event is a: Public Seminar

A family of sets is intersecting if every two sets in intersect. If consists of all the sets in a family that contain a fixed point , then we call the star of at . Thus, a star is trivially intersecting. We say that has the star property if at least one of its largest intersecting subfamilies is a star of . The classical Erdős--Ko--Rado (EKR) Theorem [4] says that the family of -element subsets of has the star property. Determining the size or the structure of a largest intersecting subfamily of a given family has become one of the most popular endeavours in extremal set theory.

A hereditary family is a union of power sets. An outstanding open conjecture of Chvátal [3] claims that every hereditary family has the star property. We will discuss the work done on this conjecture and on a weighted version [2] that generalizes both the conjecture and an analogous conjecture for families of signed sets.

A base of is a set in that is not a subset of another one. We denote by the size of a smallest base of . A generalization of an appealing conjecture of Holroyd and Talbot [5] is the following uniform version of Chvátal's conjecture: If is a hereditary family with , then the family of -element sets in has the star property. The EKR Theorem confirms this for the case where is the power set of . The speaker [1] proved the conjecture for with sufficiently large depending on . We will discuss various aspects of this result together with variants and generalizations.

[1] P. Borg, Extremal -intersecting sub-families of hereditary families, J. London Math. Soc. 79 (2009), 167--185.
[2] P. Borg, On Chvátal's conjecture and a conjecture on families of signed sets, European J. Combin. 32 (2011), 140--145.
[3] V. Chvátal, Unsolved Problem No. 7, in: C. Berge, D.K. Ray-Chaudhuri (Eds.), Hypergraph Seminar, Lecture Notes in Mathematics, 411, Springer, Berlin, 1974.
[4] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2) 12 (1961), 313--320.
[5] F.C. Holroyd and J. Talbot, Graphs with the Erdős--Ko--Rado property, Discrete Math. 293 (2005), 165--176.


Report an error on this page

External Speakers

Peter Borg, University of Malta