V(Qn) = {0,1}n

V(Qn) = {0,1}n

• V(Qn) = {0,1}n

• E(Qn) = pairs that differ in exactly one coordinate

[01011] denotes the edge between vertices [010011] and [011011]

• [01011] denotes the edge between vertices [010011] and [011011]

• [0001] denotes a Q3 subgraph of Q7.

Turán’s theorem [1941] answers the question:

• Turán’s theorem [1941] answers the question:

• How many edges can an n-vertex graph contain while not containing Kr as a subgraph?

• Equivalently:

• What is the minimum number of edges we must delete from Kn to kill all copies of Kr?

c(n,G) = minimum number of edges to delete from Qn to kill all copies of G.

• c(n,G) = minimum number of edges to delete from Qn to kill all copies of G.

• E.g. c(3,Q2) = 3

• c(G) = limn→∞ c(n,G)/|E(Qn)|

Conjecture: c(Q2) = 1/2

• Conjecture: c(Q2) = 1/2

• [Erdös,1984]

• Best known bounds

• [Thomason, Wagner, 2008]

• [Brass, Harborth, Neinborg, 1995]

• .377 < c(Q2) < .5(n-sqrt(n))2n-1

Conjecture [Alon, Krech, Szabó, 2007]: c(Q3)= 1/4.

• Conjecture [Alon, Krech, Szabó, 2007]: c(Q3)= 1/4.

• Best known bounds [Offner, 2008]

• .116 < c(Q3) ≤ 1/4

p(G) = maximum number of colors s.t. it is possible to color the edges of any Qn s.t. every copy of G contains every color.

• p(G) = maximum number of colors s.t. it is possible to color the edges of any Qn s.t. every copy of G contains every color.

• E.g. p(Q2) = 2.

• Motivation: c(G) ≤ 1/p(G).

Hypercube

• Hypercube

• Turan type problems

• Polychromatic colorings

• * Results

• * Lower bounds

• * Upper bounds

• Open problems

d(d+1)/2 ≥ p(Qd) ≥ floor[(d+1)2/4]

• d(d+1)/2 ≥ p(Qd) ≥ floor[(d+1)2/4]

• [Alon, Krech, Szabó, 2007]

• p(Qd) = floor[(d+1)2/4]

• [Offner, 2008]

• We have bounds on p(G) for some other choices of G.

Find a coloring and show every instance of G contains all colors.

• Find a coloring and show every instance of G contains all colors.

• Typical coloring:

• Let l(e) = # of 1s to left of star in edge e.

• e.g. l([01011] ) = 1, r([01011] ) = 2.

E.g. p(Q3) ≥ 4: Color(e)= (l(e) (mod 2), r(e) (mod 2))

• E.g. p(Q3) ≥ 4: Color(e)= (l(e) (mod 2), r(e) (mod 2))

A coloring of Qn is simple if the color of e is determined by (l(e),r(e)).

• A coloring of Qn is simple if the color of e is determined by (l(e),r(e)).

• Lemma: We need only consider simple colorings.

• Proof: Application of Ramsey’s theorem.

To show p(G) < r, show that for any simple r-coloring of Qn, there is some instance of G containing at most r-1 colors.

• To show p(G) < r, show that for any simple r-coloring of Qn, there is some instance of G containing at most r-1 colors.

p(Qd) ≤ floor[(d+1)2/4].

• p(Qd) ≤ floor[(d+1)2/4].

• Idea: Arrange the color classes of Qn in a grid:

For which graphs G can we determine p(G)? Right now, Qd, Qd\v, a few others.

• For which graphs G can we determine p(G)? Right now, Qd, Qd\v, a few others.

• Is it true that for all r, there is some G s.t. p(G) = r?

Bialostocki [1983] proved if Qn is Q2-polychromatically colored with p(Q2)=2 colors, the color classes are (asymptotically) the same size. Is this true for Qd, d>2?

• Bialostocki [1983] proved if Qn is Q2-polychromatically colored with p(Q2)=2 colors, the color classes are (asymptotically) the same size. Is this true for Qd, d>2?

• What can be said about the relationship between p and c?