Description
Time 2.15-3.15
Title : Labeling the complete bipartite graphs with no simple zero cycles
Abstract : Suppose we want to label the edges of the complete bipartite graph K_{n,n} with elements of F_2^d in such a way that the sum of labels over any simple cycle is nonzero. What is the smallest possible value of d be for such a labeling to exist?
It was proved by Gopalan et. al. that log^2(n) \leq d \leq nlog(n). Kane, Lovett and Rao recently proved that d is in fact linear in n. In particular we have n/2-2 \leq d < 6n.
Upper bound is established by explicit construction while lower bound is obtained by bounding the size of independent sets in certain Cayley graphs of S_n.