Tag: mas575

  • 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 E(Kn) of the complete graph cannot be partitioned into less than n1 copies of the edge sets of complete bipartite subgraphs.
    • Lindström and Smet (1970).
      • Let A1,A2,,An+1[n]. Then there exist subsets I and J of [n+1] such that IJ,IJ=, and iIAi=jJAj.
    • Lindström (1993)
      • Let A1,A2,,An+2[n]. Then there exist subsets I and J of [n+2] such that IJ, IJ=, and iIAi=jJAj and iIAi=jJAj.
    • Larman, Rogers, and Seidel (1977) [New in 2017]
      • Every two-distance set in Rn has at most (n+22)+n+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 Rn has at most (n+22) points.
    • Erdős (1963)
      • Let C1,C2,,Cm be the list of clubs and each club has at least k members. If m<2k1, then such an assignment of students into two lecture halls is always possible.
    • Erdős, Ko, and Rado (1961). Proof by Katona (1972)
      • Let kn/2. Let F be a k-uniform intersecting family of subsets of an n-set. Then |F|(n1k1).
    • Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948)
      • Let k be a positive integer. Let F be a family on an n-set S such that |XY|=k whenever X,YF and XY. Then |F|n.
      • Corollary due to de Brujin and Erdős (1948):  Suppose that n points are given on the plane so that not all are on one line. Then there are at least n distinct lines through at least two of the n points.
    • Frankl and Wilson (1981). Proof by Babai (1988).
      • If a family F of subsets of [n] is L-intersecting and |L|=s, then |F|i=0s(ni).
    • Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991).
      • If a family F of subsets of [n] is uniform L-intersecting and |L|=s, then |F|(ns).  (A family of sets is \emph{uniform} if all members have the same size.)
    • Deza, Frankl, and Singhi (1983)
      • Let p be a prime. Let L{0,1,2,,p1} and |L|=s.If
        (i) |A|L+pZ for all AF,
        (ii) |AB|L+pZ for all A,BF, AB,
        then |F|i=0s(ni).
    • Alon, Babai, and Suzuki (1991)
      • Let p be a prime. Let k be an integer. Let L{0,1,2,,p1} and |L|=s. Assume s+kn. If
        (i) |A|kL+pZ for all AF,
        (ii) |AB|L+pZ for all A,BF, AB,
        then |F|(ns).
    • Grolmusz and Sudakov (2002) [New in 2017]
      • Let p be a prime. Let L{0,1,,p1} with |L|=s and k2. Let F be a family of subsets of [n] such that
        (i) |A|L+pZ for all AF and
        (ii) |A1A2Ak|L+pZ for every collection of k distinct members A1,A2,,Ak of F.
        Then |F|(k1)i=0s(ni).
    • Grolmusz and Sudakov (2002) [New in 2017]
      • Let |L|=s and k2. Let F be a family of subsets of [n] such that |A1A2Ak|L for every collection of k distinct members A1,A2,,Ak of F. Then |F|(k1)i=0s(ni).
    • Sperner (1928)
      • If F is an antichain of subsets of an n-set, then |F|(nn/2).
    • Lubell (1966), Yamamoto (1954), Meschalkin (1963)
      • If F is an antichain of subsets of an n-element set, then AF1(n|A|)1.
    • Bollobás (1965)
      • Let A1, A2, , Am, B1, B2, , Bm be subsets on an n-set such that
        (a) AiBi= for all i[m],
        (b) AiBj for all ij.
        Theni=1m1(|Ai|+|Bi||Ai|)1.
    • Bollobás (1965), extending Erdős, Hajnal, and Moon (1964)
      • If each family of at most (r+sr) edges of an r-uniform hypergraph can be covered by s vertices, then all edges can also be covered by s vertices.
    • Lovász (1977)
      • Let A1, A2, , Am, B1, B2, , Bm be subsets such that |Ai|=r and |Bi|=s for all i and
        (a) AiBi= for all i[m],
        (b) AiBj for all i<j.
        Then m(r+sr).
      • Let W be a vector space over a field F. Let U1,U2,,Um,V1,V2,,Vm be subspaces of W such that dim(Ui)=r and dim(Vi)=s for each i=1,2,,m and
        (a) UiVi={0} for i=1,2,,m;
        (b) UiVj{0} for 1i<jm.
        Then m(r+sr).
    • Füredi (1984)
      • Let U1,U2,,Um,V1,V2,,Vm be subspaces of a vector space W over a field F. If dim(Ui)=r, dim(Vi)=s for all i{1,2,,m} and for some t0,
        (a) dim(UiVi)t for all i{1,2,,m},
        (b) dim(UiVj)>t for all 1i<jm,
        then m(r+s2trt).
    • Frankl and Wilson (1981)
      • The chromatic number of the unit distance graph of Rn is larger than 1.2n for sufficiently large n.
    • Kahn and Kalai (1993)
      • (Borsuk’s conjecture is false) Let f(d) be the minimum number such that every set of diameter 1 in Rd can be partitioned into f(d) sets of smaller diameter. Then f(d)>(1.2)d for large d.
    • Mehlhorn and Schmidt (1982) [New in 2017]
      • For a matrix C, 2κ(C)rank(C). (Let κ(C) be the minimum number of rounds in order to partition C 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)
      • κ(C)rk(C).
    •  ?
      • There exists a randomized protocol to decide the equality of two strings of length n using O(logn) bits.
        The probablity of outputting an incorrect answer is less than 1/n.
    • Dvir (2009) [New in 2017]
      • Let fF[x1,,xn] be a polynomial of degree at most q1 over a finite field F with q=|F| elements. Let K be a Kakeya set. If f(x)=0 for all xK, then f is a zero polynomial.
      • If KFn is a Kakeya set, then |K|(|F|+n1n)|F|nn!.
    • Ellenberg and Gijswijt (2017) [New in 2017]
      • If A is a subset of F3n with no three-term arithmetic progression, then |A|3N where N=a,b,c0;a+b+c=n;b+2c2n/3n!a!b!c!.Furthermore 3No(2.756n).
    • Tao (2016) [New in 2017]
      • Let k2 and let A be a finite set and F be a field. Let f:AkF be a function such that if f(x1,x2,,xk)0, then x1=x2==xk. Then the slice rank of f is equal to |{x:f(x,x,,x)0}|.
    • Erdős and Rado (1960) [New in 2017]
      • There is a function f(k,r) on positive integers k and r such that every family of k-sets with more than f(k,r) members contains a sunflower of size r.
    • Naslund and Sawin (2016) [New in 2017]
      • Let F be a family of subsets of [n] having no sunflower of size 3. Then |F|3(n+1)kn/3(nk).
    • Alon and Tarsi (1992)
      • Let F be a field and let fF[x1,x2,,xn]. Suppose that deg(f)=d=i=1ndi and the coefficient of i=1nxidi is nonzero. Let L1,L2,,Ln be subsets of F such that |Li|>di. Then there exist a1L1, a2L2, , anLn such that f(a1,a2,,an)0.
    • Cauchy (1813), Davenport (1935)
      • Let p be a prime and let A,B be two nonempty subsets of Zp. Then |A+B|min(p,|A|+|B|1).
    • Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964).
      • Let p be a prime and A be a nonempty subset of Zp. Then |{a+a:a,aA,aa}|min(p,2|A|3).
    • Alon (2000)  [New in 2017]
      • Let p be an odd prime. For k<p and every integers a1,a2,,ak,b1,b2,,bk,  if b1,b2,,bk are distinct, then there exists a permutation π of {1,2,,k} such that the sums ai+bπ(i) are distinct.
    • Alon? [New in 2017]
      • If A is an n×n matrix over a field F, per(A)0 and bFn,  then for every family of sets L1, L2, , Ln of size 2 each, there is a vector xL1×L2××Ln such that (Ax)ibi for all i.
    • Alon? [New in 2017]
      • Let G be a bipartite graph with the bipartition A, B with |A|=|B|=n. Let B={b1,b2,,bn}. If G has at least one perfect matching, then for every integer d1,d2,,dn,  there exists a subset X of A such that for each i, the number of neighbors of bi in X is not di.
    • Erdős, Ginzburg, and Ziv (1961) [New in 2017]
      • Let p be a prime. Every sequence a1,a2,,a2p1 of integers contains a subsequence ai1, ai2, , aip such that  ai1+ai2+aip0(modp).
    • 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 G be an undirected graph. Let d(G)=maxHG|E(H)||V(H)|. Then there is an orientation of G such that the outdegree of each vertex is at most d(G).
    • Alon and Tarsi (1992)
      • A simple planar bipartite graph is 3-choosable.