Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ that is needed. Does this question have any connection to representation of symmetric group over $\Bbb F_2^d$?

**Update:** Fundamental roadblock here seems to be related to finding a nice way to provide labelling that encompasses every even alternating/reverse alternating cycle which prevents a better than $O(n\log{n})$ solution.

**ADDED** by David Speyer: I'd like to explain why I find this question interesting and challenging, and wish that people better at extremal combinatorics had turned some attention to it.

If we instead ask that every disjoint union of simple cycles have nonzero sum, the problem is easy (at least to leading order). A winning strategy is to use $d=n \log_2 n$ bits, divided into $n$ blocks of length $\log_2 n$. For edge $ij$, put the binary label of $j$ in the $i$-th block and the binary label of $j$ in the $i$-th block. And it is easy to show you can't do much better. For simplicity, take $n=2m$ even. Look at the $(2m-1) (2m-3) \cdots 5 \cdot 3 \cdot 1$ perfect matchings of the graph. If any two of them get the same sum, then their symmetric difference is a disjoint union of cycles with weight $0$. So we need to have at least $(2m-1) (2m-3) \cdots 5 \cdot 3 \cdot 1$ different vectors, so we need to use at least $\log_2 (2m-1) (2m-3) \cdots 5 \cdot 3 \cdot 1 \approx \frac{n}{2} \log_2 n$ bits. We have found the answer up to a factor of $2$.

Now, out of the $n!$ disjoint unions of cycles, roughly $(e/n) n!$ are a single cycle. One would think that reducing the number of things to avoid by a factor of $n$ shouldn't be able to effect the number of bits very much. Yet it seems incredibly hard to show this! How can we show that the cycles are basically randomly distributed among the disjoint unions of cycles?

Here is one way we could attempt to give a lower bound. Once again, take $n=2m$. Look at the $m!$ matchings from the first $m$ vertices to the second, which we can identify with the group $S_m$. Adding up the edges in a matching gives a coloring of $S_m$ with $2^d$ colors. If we make $S_m$ into a graph by joining $\sigma$ and $\tau$ when $\sigma^{-1} \tau$ is a single cycle, then this must be a proper coloring. So we are trying to find a lower bound for the chromatic number of the Cayley graph of $S_m$ with respect to the cycles. There is literature on the chromatic number of Cayley graphs, but I couldn't find anything that would help. I did find that a random graph on $m!$ vertices where an edge would appear with probability $e/m$ should be expected to have chromatic number $\frac{m! (e/m)}{2 \log m!} \approx \frac{e m!}{2 m^2 \log m}$. If that is the case here, we once again get $d \geq \log_2 m!$ (discarding lower terms). Is there some $S_m$ representation theory which would allow us to actually compute the chromatic number?

It really frustrates me that there is an exponential separation between by upper and lower bounds.

I will give the bounty for a construction which beats $(1-\delta) n \log_2 n$, or a lower bound which beats $(\log n)^{1+\delta}$, for any $\delta>0$.

Finally, I'd like to share a wild musing of mine. Consider two problems in graph theory and optimization. In the first problem, we are given an $n \times n$ matrix of weights $w_{ij}$, and we are trying to find a permuation $\sigma$ of $n$ which minimizes $\sum_i w_{i \sigma(i)}$. The second problem is the same, but we require that $\sigma$ is an $n$-cycle. The first problem is the assignment problem and there are good algorithms for it. The second problem is the traveling salesman problem and it is NP Hard. I am reminded of this problem: A large fraction of permutations are cycles, yet restricting myself to cycles makes thing incredibly harder.

4more comments