Report

Constructing Ramsey Graphs from Boolean Function Representations. Parikshit Gopalan Georgia Institute of Technology Atlanta, Georgia, USA. Explicit Ramsey Graph Constructions [Ramsey] : Every graph on 2n vertices has either an independent set or a clique of size n/2. Easy to construct G on 2n vertices with (G), (G) · 2n/2. [Erdös] : There exists a graph G on 2n vertices with (G), (G) · 2n. Probabilistic Method. $100 for explicit construction. Alternate View Constructing Ramsey graphs: Two color the edges of Kn so that there are no large monochromatic cliques. Constructing Multicolor Ramsey graphs: Color the edges of Kn using t colors so that there are no large monochromatic cliques. A Brief History of Explicit Constructions [Frankl-Wilson] : Gives (G), (G) · 2√n. • Extremal set theory. [Grolmusz] : Same bound, multicolor graphs. • Polynomial representations of the OR function. [Alon] : Similar to Frankl-Wilson, multicolor graphs. • Polynomial representations of graphs. n [Barak-Rao-Shaltiel-Wigderson] : (G), (G) · 2 . • Extractors and pseudorandomness. Polynomial Representations of Boolean functions Def: P(X1,…,Xn) over Zm represents f: {0,1}n ! {0,1} if f(x) f(y) ) P(x) P(y) mod m Lower bounds for AC0[m]. Prime Case: [Razborov, Smolensky] : • Small circuits ≈ Low-degree polynomials. • Prove degree lower bounds. Composite Case: Low-degree polynomials ) Small circuits Degree lower bounds over Zm. (Simpler problem?) Representing the OR function Problem: What is the degree of OR mod m ? For p prime: (n). For m composite (say 6): • Conjecture: (n) [Barrington] • O(n1/2) upper bound. [Barrington-Beigel-Rudich] • (log n) lower bound. [Barrington-Tardos] [Barrington-Beigel-Rudich, Grolmusz, Tsai, BarringtonTardos, Green, Alon-Beigel, Bhatnagar-G.-Lipton, Hansen] Can asymmetry help compute a symmetric function? A Connection [Grolmusz] Problem: Let F be a family of subsets Si of [n] where |Si| = 0 mod m |Si Å Sj| 0 mod m How large can F be? Grolumsz: If m = 6, |F| can be superpolynomial in n. Uses O(√n) degree OR polynomial of BBR. Gives a Ramsey graph matching FW. Better OR polynomials ) Better graphs. Our Results New view of OR representations. Simple Ramsey construction from OR representations. Unifies Frankl-Wilson, Grolmusz, Alon. All based on O(√n) symmetric OR polynomials. Consequences : Insight from complexity: Asymmetry versus Symmetry Extends to multicolor Ramsey graphs. Improved bounds for restricted set systems. Outline of This Talk I Ramsey graphs from OR representations. • New view of OR representations. • Sample constructions. • Ramsey graphs. II Limitations to Symmetric Constructions. Outline of This Talk I Ramsey graphs from OR representations. • New view of OR representations. • Sample constructions. • Ramsey graphs. II Limitations to Symmetric Constructions. OR Representations New view of an OR representation: Two polynomials s.t. the union of their zero sets is {0,1}n \ {0}. P=0 Q=0 OR Representations New view of an OR representation: • Two polynomials. • Union of their zero sets is {0,1}n \ {0}. • Degree of representation = max(deg(P), deg(Q)). Both polynomials mod p. (n) P mod p, Q mod q. O(√n) [BBR, Alon] Prime Representations Both polynomials mod pa. O(√n) [FW] Prime-power representations All give O(√n) degree symmetric polynomials. Alon’s Construction Choose p ¼ q, and let n = pq -1. • Let P(X1,…,Xn) = 1 – ( Xi)p-1 mod p Indicator for Xi being divisible by p. • Let Q(X1,…,Xn) = 1 – ( Xi)q-1 mod q Indicator for Xi being divisible by q. • Both are 1 only for (0,…,0). Degree of the construction is max(p,q) = O(√n). [BBR’94] Take p = 2, q = 3. Special cases of OR representations modulo pq. [Frankl-Wilson] Take n = p2 -1. Both polynomials modulo powers of p. The Ramsey Graph Construction Ramsey Construction: Vertices: {0,1}n. Edges: Add edge (x,y) if P(x © y) = 0. Thm: Degree d OR representation gives (G), (G) · nd. Proof by the linear algebra method [Babai-Frankl]. Plugging in d = O(√n) gives a bound of 2√n. Lower degree ) better graphs. Outline of This Talk I Ramsey graphs from OR representations. • New view of OR representations. • Sample constructions. • Ramsey graphs construction. II Limitations to Symmetric Constructions. Limitations to Symmetric Constructions Thm : (√n) lower bound for symmetric polynomials. For any OR representation, deg(P) £ deg(Q) = (n). Symmetry vs asymmetry question applies to Ramsey graph constructions. Limitations to Symmetric Constructions Thm : (√n) lower bound for symmetric polynomials. P mod p, Q mod q. [BBR, Alon] Gives a representation of OR over Zpq. Known lower bound: √(n/pq). When n < pq [Alon] … Xi represents OR mod pq. Both polynomials mod pa. [FW] Based on interpolation algorithm mod pa [G’06]. Partition Problem Adversary gets number n. Picks 1. Primes p and q where p¢q > n. 2. A µ {1,…, p-1} and B µ {1, …, q-1} Every x 2 {1, …, n} is covered by A or B. Minimize |A|¢|B|. x mod p lies in A Partition Problem Adversary gets number n. Picks 1. Primes p and q where p¢q > n. 2. A µ {1,…, p-1} and B µ {1, …, q-1} Every x 2 {1, …, n} is covered by A or B. Minimize |A|¢|B|. p = 5, q = 7, n = 12 1 2 3 4 1 1 … 2 3 4 5 6 12 Partition Lemma Trivial Solutions : A = {1,…, p-1} and B = {p, 2p, …, } A = {q, 2q, …} and B = {1, …, q-1} Gives |A|¢ |B| = n. Better solutions ) Better OR representations. Partition Lemma: In any solution, |A|¢|B| ¸ n/8. Symmetry vs. Asymmetry Do low degree OR polynomials exist? Conjecture [Barrington-Beigel-Rudich]: No! (for representations mod 6) • Symmetric polynomials for Symmetric functions. • CRT. Hard explicit construction problem ? Symmetric polynomials give graphs on {0,1}n based on distances. Q : Are such graphs not good Ramsey graphs?