New Results on Simplex-Clusters in Set Systems
- PDF / 348,264 Bytes
- 12 Pages / 442.205 x 665.008 pts Page_size
- 24 Downloads / 215 Views
Bolyai Society – Springer-Verlag
Combinatorica 12pp. DOI: 10.1007/s00493-020-4441-1
NEW RESULTS ON SIMPLEX-CLUSTERS IN SET SYSTEMS GABRIEL CURRIER Received February 5, 2020 Revised July 27, 2020 A d-simplex is defined to be a collection A1 , . . . , Ad+1 of subsets of size k of [n] such that the intersection of all of them is empty, but the intersection of any d of them is non-empty. Furthemore, a d-cluster is a collection of d+1 such sets with empty intersection and union of size ≤ 2k, and a d-simplex-cluster is such a collection that is both a d-simplex and a d-cluster. The Erd˝ os–Chv´ atal d-simplex Conjecture from 1974 states that any family of k-subsets of [n] containing no d-simplex must be of size no greater than n−1 . In 2011, k−1 Keevash and Mubayi extended this conjecture by hypothesizing that the same bound would hold for families containing no d-simplex-cluster. In this paper, we resolve Keevash and Mubayi’s conjecture for all 4 ≤ d + 1 ≤ k and n ≥ 2k − d + 2, which in turn resolves all remaining cases of the Erd˝ os–Chv´ atal Conjecture except when n is very small (i.e. n < 2k − d + 2).
1. Introduction For positive integers n, k we define [n] := {1, . . . , n} and use X k to denote the set of all k-element subsets of a set X. Furthermore, we refer to a set [n] F ⊆ [n] k as a family, and if every element of F contains some S ∈ s , we say that F is an s-star centered at S. If S = {x}, we say simply that F is a star centered at x. Observe that s-stars can be no bigger than n−s k−s . The following theorem, commonly known as the Erd˝os-Ko-Rado (EKR) theorem, is a foundational result in extremal combinatorics.
Mathematics Subject Classification (2010): 05D05
2
GABRIEL CURRIER
Theorem 1. Let n ≥ 2k and suppose F ⊆ [n] k . Furthermore, if A ∩ B 6= ∅ for all A, B ∈ F, then n−1 |F| ≤ , k−1 where, if n > 2k, equality holds only if F is a maximum-sized star. Families F that satisfy this condition are sometimes referred to as pairwise intersecting. Since its original publication in 1961 [4], EKR has seen numerous applications and has been proven using a wide array of different combinatorial and algebraic techniques. It has even generated a whole subfield of extremal combinatorics known as intersection problems, in which one considers the maximum size of a family with a certain forbidden subfamily, where the subfamily is defined according to some intersection or union constraints. For an introduction to this field, we direct readers to a recent survey of Frankl and Tokushige [9]. One of the more heavily-studied problems in this area involves the notion of a d-simplex. Definition 1. A d-simplex is a set of d + 1 elements {A1 , A2 , . . . , Ad+1 } of Td+1 [n] with the properties that i=1 Ai = ∅ and for any 1 ≤ j ≤ d + 1 we have k T i6=j Ai 6= ∅. In 1971, Erd˝ os conjectured that a family F ⊆ [n] that contains no 2k simplex (also known as a triangle) must adhere to the same bound of |F| ≤ n−1 . In 1974, Chv´ a tal extended this conjecture to the following. k−1 [n] Conjecture 1 ([2]). Let 3 ≤
Data Loading...
