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 copies of the edge sets of complete bipartite subgraphs.
- The edge set
- Lindström and Smet (1970).
- Let
. Then there exist subsets and of such that
- Let
- Lindström (1993)
- Let
. Then there exist subsets and of such that , , and
- Let
- Larman, Rogers, and Seidel (1977) [New in 2017]
- Every two-distance set in
has at most points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.)
- Every two-distance set in
- Blokhuis (1984) [New in 2017]
- Every two-distance set in
has at most points.
- Every two-distance set in
- Erdős (1963)
- Let
be the list of clubs and each club has at least members. If , then such an assignment of students into two lecture halls is always possible.
- Let
- Erdős, Ko, and Rado (1961). Proof by Katona (1972)
- Let
. Let be a -uniform intersecting family of subsets of an -set. Then
- Let
- Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948)
- Let
be a positive integer. Let be a family on an -set such that whenever and . Then . - 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.
- Let
- Frankl and Wilson (1981). Proof by Babai (1988).
- If a family
of subsets of is -intersecting and , then
- If a family
- Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991).
- If a family
of subsets of is uniform -intersecting and , then (A family of sets is \emph{uniform} if all members have the same size.)
- If a family
- Deza, Frankl, and Singhi (1983)
- Let
be a prime. Let and .If
(i) for all ,
(ii) for all , ,
then
- Let
- Alon, Babai, and Suzuki (1991)
- Let
be a prime. Let be an integer. Let and . Assume . If
(i) for all ,
(ii) for all , ,
then
- Let
- Grolmusz and Sudakov (2002) [New in 2017]
- Let
be a prime. Let with and . Let be a family of subsets of such that
(i) for all and
(ii) for every collection of distinct members of .
Then
- Let
- Grolmusz and Sudakov (2002) [New in 2017]
- Let
and . Let be a family of subsets of such that for every collection of distinct members of . Then
- Let
- Sperner (1928)
- If
is an antichain of subsets of an -set, then
- If
- Lubell (1966), Yamamoto (1954), Meschalkin (1963)
- If
is an antichain of subsets of an -element set, then
- If
- Bollobás (1965)
- Let
, , , , , , , be subsets on an -set such that
(a) for all ,
(b) for all .
Then
- Let
- 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.
- If each family of at most
- Lovász (1977)
- Let
, , , , , , , be subsets such that and for all and
(a) for all ,
(b) for all .
Then . - Let
be a vector space over a field . Let be subspaces of such that and for each and
(a) for ;
(b) for .
Then .
- Let
- Füredi (1984)
- Let
be subspaces of a vector space over a field . If , for all and for some ,
(a) for all ,
(b) for all ,
then .
- Let
- Frankl and Wilson (1981)
- The chromatic number of the unit distance graph of
is larger than for sufficiently large .
- The chromatic number of the unit distance graph of
- Kahn and Kalai (1993)
- (Borsuk’s conjecture is false) Let
be the minimum number such that every set of diameter in can be partitioned into sets of smaller diameter. Then for large .
- (Borsuk’s conjecture is false) Let
- Mehlhorn and Schmidt (1982) [New in 2017]
- For a matrix C,
. (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.)
- For a matrix C,
- Lovász and Saks (1993)
.
- ?
- There exists a randomized protocol to decide the equality of two strings of length
using bits.
The probablity of outputting an incorrect answer is less than .
- There exists a randomized protocol to decide the equality of two strings of length
- Dvir (2009) [New in 2017]
- Let
be a polynomial of degree at most over a finite field with elements. Let be a Kakeya set. If for all , then is a zero polynomial. - If
is a Kakeya set, then
- Let
- Ellenberg and Gijswijt (2017) [New in 2017]
- If
is a subset of with no three-term arithmetic progression, then where Furthermore .
- If
- Tao (2016) [New in 2017]
- Let
and let be a finite set and be a field. Let be a function such that if , then . Then the slice rank of is equal to .
- Let
- 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 .
- There is a function
- Naslund and Sawin (2016) [New in 2017]
- Let
be a family of subsets of having no sunflower of size . Then
- Let
- Alon and Tarsi (1992)
- Let
be a field and let . Suppose that and the coefficient of is nonzero. Let be subsets of such that . Then there exist , , , such that
- Let
- Cauchy (1813), Davenport (1935)
- Let
be a prime and let be two nonempty subsets of . Then
- Let
- 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
- Let
- Alon (2000) [New in 2017]
- Let
be an odd prime. For and every integers , if are distinct, then there exists a permutation of such that the sums are distinct.
- Let
- Alon? [New in 2017]
- If
is an matrix over a field , and , then for every family of sets , , , of size each, there is a vector such that for all .
- If
- Alon? [New in 2017]
- Let
be a bipartite graph with the bipartition , with . Let . If has at least one perfect matching, then for every integer , there exists a subset of such that for each , the number of neighbors of in is not .
- Let
- Erdős, Ginzburg, and Ziv (1961) [New in 2017]
- Let
be a prime. Every sequence of integers contains a subsequence , , , such that .
- Let
- Alon, Friedland, and Kalai (1984) [New in 2017]
- Every (multi)graph with average degree
and maximum degree contains a -regular subgraph.
- Every (multi)graph with average degree
- ?
- Let
be an undirected graph. Let . Then there is an orientation of such that the outdegree of each vertex is at most .
- Let
- Alon and Tarsi (1992)
- A simple planar bipartite graph is
-choosable.
- A simple planar bipartite graph is