Theorems covered in MAS575 Combinatorics Spring 2017

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.