Category: KAIST

This post will give an incomplete list of theorems covered in MAS575 Combinatorics Fall 2017. This post will be continuously updated throughout this semester. (Last update: April 5, 2017.)
2017년 봄학기 MAS575 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다.

• Graham and Pollak (1971). Proof by Tverberg (1982)
  • The edge set 𝐸⁡(𝐾𝑛) of the complete graph cannot be partitioned into less than 𝑛 −1 copies of the edge sets of complete bipartite subgraphs.
• Lindström and Smet (1970).
  • Let 𝐴1,𝐴2,…,𝐴𝑛+1 ⊆[𝑛]. Then there exist subsets 𝐼 and 𝐽 of [𝑛 +1] such that 𝐼∪𝐽≠∅,𝐼∩𝐽=∅, and ⋃𝑖∈𝐼𝐴𝑖=⋃𝑗∈𝐽𝐴𝑗.
• Lindström (1993)
  • Let 𝐴1,𝐴2,…,𝐴𝑛+2 ⊆[𝑛]. Then there exist subsets 𝐼 and 𝐽 of [𝑛 +2] such that 𝐼 ∪𝐽 ≠∅, 𝐼 ∩𝐽 =∅, and ⋃𝑖∈𝐼𝐴𝑖=⋃𝑗∈𝐽𝐴𝑗 and ⋂𝑖∈𝐼𝐴𝑖=⋂𝑗∈𝐽𝐴𝑗.
• Larman, Rogers, and Seidel (1977) [New in 2017]
  • Every two-distance set in ℝ𝑛 has at most (𝑛+22) +𝑛 +1 points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.)
• Blokhuis (1984) [New in 2017]
  • Every two-distance set in ℝ𝑛 has at most (𝑛+22) points.
• Erdős (1963)
  • Let 𝐶1,𝐶2,…,𝐶𝑚 be the list of clubs and each club has at least 𝑘 members. If 𝑚 <2𝑘−1, then such an assignment of students into two lecture halls is always possible.
• Erdős, Ko, and Rado (1961). Proof by Katona (1972)
  • Let 𝑘 ≤𝑛/2. Let F be a 𝑘-uniform intersecting family of subsets of an 𝑛-set. Then |F|≤(𝑛−1𝑘−1).
• Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948)
  • Let 𝑘 be a positive integer. Let F be a family on an 𝑛-set 𝑆 such that |𝑋 ∩𝑌| =𝑘 whenever 𝑋,𝑌 ∈F and 𝑋 ≠𝑌. Then |F| ≤𝑛.
  • Corollary due to de Brujin and Erdős (1948):  Suppose that 𝑛 points are given on the plane so that not all are on one line. Then there are at least 𝑛 distinct lines through at least two of the 𝑛 points.
• Frankl and Wilson (1981). Proof by Babai (1988).
  • If a family F of subsets of [𝑛] is 𝐿-intersecting and |𝐿| =𝑠, then |F|≤𝑠∑𝑖=0(𝑛𝑖).
• Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991).
  • If a family F of subsets of [𝑛] is uniform 𝐿-intersecting and |𝐿| =𝑠, then |F|≤(𝑛𝑠).  (A family of sets is \emph{uniform} if all members have the same size.)
• Deza, Frankl, and Singhi (1983)
  • Let 𝑝 be a prime. Let 𝐿 ⊆{0,1,2,…,𝑝 −1} and |𝐿| =𝑠.If
    (i) |𝐴| ∉𝐿 +𝑝⁢ℤ for all 𝐴 ∈F,
    (ii) |𝐴 ∩𝐵| ∈𝐿 +𝑝⁢ℤ for all 𝐴,𝐵 ∈F, 𝐴 ≠𝐵,
    then |F|≤𝑠∑𝑖=0(𝑛𝑖).
• Alon, Babai, and Suzuki (1991)
  • Let 𝑝 be a prime. Let 𝑘 be an integer. Let 𝐿 ⊆{0,1,2,…,𝑝 −1} and |𝐿| =𝑠. Assume 𝑠 +𝑘 ≤𝑛. If
    (i) |𝐴| ≡𝑘 ∉𝐿 +𝑝⁢ℤ for all 𝐴 ∈F,
    (ii) |𝐴 ∩𝐵| ∈𝐿 +𝑝⁢ℤ for all 𝐴,𝐵 ∈F, 𝐴 ≠𝐵,
    then |F|≤(𝑛𝑠).
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let 𝑝 be a prime. Let 𝐿 ⊆{0,1,…,𝑝 −1} with |𝐿| =𝑠 and 𝑘 ≥2. Let F be a family of subsets of [𝑛] such that
    (i) |𝐴| ∉𝐿 +𝑝⁢ℤ for all 𝐴 ∈F and
    (ii) |𝐴1 ∩𝐴2 ∩⋯ ∩𝐴𝑘| ∈𝐿 +𝑝⁢ℤ for every collection of 𝑘 distinct members 𝐴1,𝐴2,…,𝐴𝑘 of F.
    Then |F|≤(𝑘−1)⁢𝑠∑𝑖=0(𝑛𝑖).
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let |𝐿| =𝑠 and 𝑘 ≥2. Let F be a family of subsets of [𝑛] such that |𝐴1∩𝐴2∩⋯∩𝐴𝑘|∈𝐿 for every collection of 𝑘 distinct members 𝐴1,𝐴2,…,𝐴𝑘 of F. Then |F|≤(𝑘−1)⁢𝑠∑𝑖=0(𝑛𝑖).
• Sperner (1928)
  • If F is an antichain of subsets of an 𝑛-set, then |F|≤(𝑛⌊𝑛/2⌋).
• Lubell (1966), Yamamoto (1954), Meschalkin (1963)
  • If F is an antichain of subsets of an 𝑛-element set, then ∑𝐴∈F1(𝑛|𝐴|)≤1.
• Bollobás (1965)
  • Let 𝐴1, 𝐴2, …, 𝐴𝑚, 𝐵1, 𝐵2, …, 𝐵𝑚 be subsets on an 𝑛-set such that
    (a) 𝐴𝑖 ∩𝐵𝑖 =∅ for all 𝑖 ∈[𝑚],
    (b) 𝐴𝑖 ∩𝐵𝑗 ≠∅ for all 𝑖 ≠𝑗.
    Then𝑚∑𝑖=11(|𝐴𝑖|+|𝐵𝑖||𝐴𝑖|)≤1.
• Bollobás (1965), extending Erdős, Hajnal, and Moon (1964)
  • If each family of at most (𝑟+𝑠𝑟) edges of an 𝑟-uniform hypergraph can be covered by 𝑠 vertices, then all edges can also be covered by 𝑠 vertices.
• Lovász (1977)
  • Let 𝐴1, 𝐴2, …, 𝐴𝑚, 𝐵1, 𝐵2, …, 𝐵𝑚 be subsets such that |𝐴𝑖| =𝑟 and |𝐵𝑖| =𝑠 for all 𝑖 and
    (a) 𝐴𝑖 ∩𝐵𝑖 =∅ for all 𝑖 ∈[𝑚],
    (b) 𝐴𝑖 ∩𝐵𝑗 ≠∅ for all 𝑖 <𝑗.
    Then 𝑚 ≤(𝑟+𝑠𝑟).
  • Let 𝑊 be a vector space over a field 𝔽. Let 𝑈1,𝑈2,…,𝑈𝑚,𝑉1,𝑉2,…,𝑉𝑚 be subspaces of 𝑊 such that dim⁡(𝑈𝑖) =𝑟 and dim⁡(𝑉𝑖) =𝑠 for each 𝑖 =1,2,…,𝑚 and
    (a) 𝑈𝑖 ∩𝑉𝑖 ={0} for 𝑖 =1,2,…,𝑚;
    (b) 𝑈𝑖 ∩𝑉𝑗 ≠{0} for 1 ≤𝑖 <𝑗 ≤𝑚.
    Then 𝑚 ≤(𝑟+𝑠𝑟).
• Füredi (1984)
  • Let 𝑈1,𝑈2,…,𝑈𝑚,𝑉1,𝑉2,…,𝑉𝑚 be subspaces of a vector space 𝑊 over a field 𝔽. If dim⁡(𝑈𝑖) =𝑟, dim⁡(𝑉𝑖) =𝑠 for all 𝑖 ∈{1,2,…,𝑚} and for some 𝑡 ≥0,
    (a) dim⁡(𝑈𝑖 ∩𝑉𝑖) ≤𝑡 for all 𝑖 ∈{1,2,…,𝑚},
    (b) dim⁡(𝑈𝑖 ∩𝑉𝑗) >𝑡 for all 1 ≤𝑖 <𝑗 ≤𝑚,
    then 𝑚 ≤(𝑟+𝑠−2⁢𝑡𝑟−𝑡).
• Frankl and Wilson (1981)
  • The chromatic number of the unit distance graph of ℝ𝑛 is larger than 1.2𝑛 for sufficiently large 𝑛.
• Kahn and Kalai (1993)
  • (Borsuk’s conjecture is false) Let 𝑓⁡(𝑑) be the minimum number such that every set of diameter 1 in ℝ𝑑 can be partitioned into 𝑓⁡(𝑑) sets of smaller diameter. Then 𝑓⁡(𝑑) >(1.2)√𝑑 for large 𝑑.
• Mehlhorn and Schmidt (1982) [New in 2017]
  • For a matrix C, 2𝜅⁡(𝐶) ≥rank⁡(𝐶). (Let 𝜅⁡(𝐶) be the minimum number of rounds in order to partition 𝐶 into almost homogeneous matrices, if in each round we can split each of the current submatrices into two either vertically or horizontally. This is a parameter related to the communication complexity.)
• Lovász and Saks (1993)
  • 𝜅⁡(𝐶) ≤rk⁡(𝐶).
•  ?
  • There exists a randomized protocol to decide the equality of two strings of length 𝑛 using 𝑂⁡(log⁡𝑛) bits.
    The probablity of outputting an incorrect answer is less than 1/𝑛.
• Dvir (2009) [New in 2017]
  • Let 𝑓 ∈𝔽⁡[𝑥1,…,𝑥𝑛] be a polynomial of degree at most 𝑞 −1 over a finite field 𝔽 with 𝑞 =|𝐹| elements. Let 𝐾 be a Kakeya set. If 𝑓⁡(𝑥) =0 for all 𝑥 ∈𝐾, then 𝑓 is a zero polynomial.
  • If 𝐾 ⊆𝔽𝑛 is a Kakeya set, then |𝐾|≥(|𝔽|+𝑛−1𝑛)≥|𝐹|𝑛𝑛!.
• Ellenberg and Gijswijt (2017) [New in 2017]
  • If 𝐴 is a subset of 𝔽𝑛3 with no three-term arithmetic progression, then |𝐴| ≤3⁢𝑁 where 𝑁=∑𝑎,𝑏,𝑐≥0;𝑎+𝑏+𝑐=𝑛;𝑏+2⁢𝑐≤2⁢𝑛/3𝑛!𝑎!𝑏!𝑐!.Furthermore 3⁢𝑁 ≤𝑜⁡(2.756𝑛).
• Tao (2016) [New in 2017]
  • Let 𝑘 ≥2 and let 𝐴 be a finite set and 𝔽 be a field. Let 𝑓 :𝐴𝑘 →𝔽 be a function such that if 𝑓⁡(𝑥1,𝑥2,…,𝑥𝑘) ≠0, then 𝑥1 =𝑥2 =⋯ =𝑥𝑘. Then the slice rank of 𝑓 is equal to |{𝑥 :𝑓⁡(𝑥,𝑥,…,𝑥) ≠0}|.
• Erdős and Rado (1960) [New in 2017]
  • There is a function 𝑓⁡(𝑘,𝑟) on positive integers 𝑘 and 𝑟 such that every family of 𝑘-sets with more than 𝑓⁡(𝑘,𝑟) members contains a sunflower of size 𝑟.
• Naslund and Sawin (2016) [New in 2017]
  • Let F be a family of subsets of [𝑛] having no sunflower of size 3. Then |F|≤3⁢(𝑛+1)⁢∑𝑘≤𝑛/3(𝑛𝑘).
• Alon and Tarsi (1992)
  • Let 𝔽 be a field and let 𝑓 ∈𝔽⁡[𝑥1,𝑥2,…,𝑥𝑛]. Suppose that deg⁡(𝑓) =𝑑 =∑𝑛𝑖=1𝑑𝑖 and the coefficient of ∏𝑛𝑖=1𝑥𝑑𝑖𝑖 is nonzero. Let 𝐿1,𝐿2,…,𝐿𝑛 be subsets of 𝔽 such that |𝐿𝑖| >𝑑𝑖. Then there exist 𝑎1 ∈𝐿1, 𝑎2 ∈𝐿2, …, 𝑎𝑛 ∈𝐿𝑛 such that 𝑓⁡(𝑎1,𝑎2,…,𝑎𝑛)≠0.
• Cauchy (1813), Davenport (1935)
  • Let 𝑝 be a prime and let 𝐴,𝐵 be two nonempty subsets of ℤ𝑝. Then |𝐴+𝐵|≥min⁡(𝑝,|𝐴|+|𝐵|−1).
• Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964).
  • Let 𝑝 be a prime and 𝐴 be a nonempty subset of ℤ𝑝. Then |{𝑎+𝑎′:𝑎,𝑎′∈𝐴,𝑎≠𝑎′}|≥min⁡(𝑝,2⁢|𝐴|−3).
• Alon (2000)  [New in 2017]
  • Let 𝑝 be an odd prime. For 𝑘 <𝑝 and every integers 𝑎1,𝑎2,…,𝑎𝑘,𝑏1,𝑏2,…,𝑏𝑘,  if 𝑏1,𝑏2,…,𝑏𝑘 are distinct, then there exists a permutation 𝜋 of {1,2,…,𝑘} such that the sums 𝑎𝑖 +𝑏𝜋⁡(𝑖) are distinct.
• Alon? [New in 2017]
  • If 𝐴 is an 𝑛 ×𝑛 matrix over a field 𝔽, per⁡(𝐴) ≠0 and 𝑏 ∈𝔽𝑛,  then for every family of sets 𝐿1, 𝐿2, …, 𝐿𝑛 of size 2 each, there is a vector 𝑥 ∈𝐿1 ×𝐿2 ×⋯ ×𝐿𝑛 such that (𝐴⁢𝑥)𝑖≠𝑏𝑖 for all 𝑖.
• Alon? [New in 2017]
  • Let 𝐺 be a bipartite graph with the bipartition 𝐴, 𝐵 with |𝐴| =|𝐵| =𝑛. Let 𝐵 ={𝑏1,𝑏2,…,𝑏𝑛}. If 𝐺 has at least one perfect matching, then for every integer 𝑑1,𝑑2,…,𝑑𝑛,  there exists a subset 𝑋 of 𝐴 such that for each 𝑖, the number of neighbors of 𝑏𝑖 in 𝑋 is not 𝑑𝑖.
• Erdős, Ginzburg, and Ziv (1961) [New in 2017]
  • Let 𝑝 be a prime. Every sequence 𝑎1,𝑎2,…,𝑎2⁢𝑝−1 of integers contains a subsequence 𝑎𝑖1, 𝑎𝑖2, …, 𝑎𝑖𝑝 such that  𝑎𝑖1 +𝑎𝑖2 +⋯𝑎𝑖𝑝 ≡0⁢(mod⁡𝑝).
• Alon, Friedland, and Kalai (1984) [New in 2017]
  • Every (multi)graph with average degree >4 and maximum degree ≤5 contains a 3-regular subgraph.
• ?
  • Let 𝐺 be an undirected graph. Let 𝑑⁡(𝐺) =max𝐻⊆𝐺⁡|𝐸⁡(𝐻)||𝑉⁡(𝐻)|. Then there is an orientation of 𝐺 such that the outdegree of each vertex is at most ⌈𝑑⁡(𝐺)⌉.
• Alon and Tarsi (1992)
  • A simple planar bipartite graph is 3-choosable.