A question on representation of graphs

Question

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.

Answer 1

It's important to clarify what definition of "cycle" you have in mind. In algebraic-graph-theory contexts like this one, the natural definition is that it's a set of edges with even degree at each vertex; these sets form the vectors of a $\mathbb{Z}_2$-vector space, the cycle space of the graph, using the symmetric difference operation as the vector sum.

With this definition, the minimum $d$ you're looking for is just the circuit rank of the graph, i.e. the dimension of the cycle space, $m-n+1$ where $m$ is the number of edges and $n$ is the number of vertices. Your labeling gives a linear map from the cycle space to the label space, this map has a nontrivial kernel unless $d$ is large enough, and a vector in the kernel is a cycle with zero label sum. In the other direction, it is easy to find labelings with dimension equal to the circuit rank that avoid cycles summing to zero. For instance, find a spanning tree of the graph, label each tree edge with the zero vector, and label each non-tree edge with a basis vector (independent of all the other nonzero labels).

This all works regardless of whether the graph is complete. But if you have some other definition of cycles in mind, such as simple cycles, then your labeling problem looks messier.

Answer 2

I have now tried a few different strategies which are all winding up at $d \approx n \log_2 n$. I'll describe the simplest of these. (David Epstein's strategy with the spanning tree gives $d \approx n^2/2$.)

Let $2^{m-1} < n \leq 2^m$, so we can encode the vertices of the graph with $m$ bits. I will show how to take $d=mn$. Think of those $mn$ bits as $n$ blocks of length $m$. For an edge joining vertices $i$ and $j$, put the binary label of $j$ in the $i$-th block and the binary label of $i$ in the $j$-th block. Put zeroes in all other blocks.

Suppose we have a simple cycle. Let this cycle contain the section $(i,j,k)$. Then the $j$-th block will contain the binary labels of $i$ and $k$, which will not cancel, and nothing else.

I have some minor tricks which can shave small numbers of bits off this, but I am waiting to see if someone can come up with something much better first.

---

My best lower bound is $\approx \log_2 n$. This is horribly far from what I believe the truth to be, but I record it nonetheless. Let $n=2p$ for $p$ prime. For $0 \leq k < p$, let $w_k = \sum_{i=1}^p v(i, p+1+(i \bmod p))$. If $d < \log_2 p$, then two of the $w_k$ are equal by the pigeonhole principle, say $w_{k_1} = w_{k_2}$. But then $w_{k_1} + w_{k_2}$ is the sum over the edges in a $2p$ cycle.

Answer 3

Here is a modest improvement on the upper bound that shows $d=O(n\log\log n)$.

The base of the construction is the following. Order the vertices according to some permutation as $v_1,\ldots,v_n$. Fix $2n$ independent vectors from $\mathbb F_2^d$ and assign two vectors, $\ell_i$ and $r_i$, to each vertex $v_i$. Assign to the edge $v_iv_j$ the vector $r_i+\ell_j$ if $i<j$ and $\ell_i+r_j$ if $i>j$. Notice that this usually gives a nonzero sum for long cycles.

Our strategy will be to take $t\approx \log \frac nk$ permutations (with $t\cdot 2n$ independent vectors) and take the sums on each edge to take care of all cycles longer than $k$. The standard probabilistic approach with $\approx k\log n$ further independent vectors takes care of all cycles whose length is at most $k$. This in total gives $d\approx t\cdot n + k\log n =O(n\log\log n)$.

Claim. $t\approx \log \frac nk$ permutations are enough to take care of all cycles longer than $k$.

Proof of the claim. Divide $n$ into groups of size $k$. Fix an order inside each group, this will be the same in each permutation, which thus practically act on $m=\frac nk$ elements. For every cycle $C=c_1\ldots c_k$ of length $k$, either there are three different groups that contain three consecutive vertices from $C$ (thus $c_{i-1}\in G_1$, $c_{i}\in G_2$, $c_{i+1}\in G_3$), or two different groups, one of which contains the first two of three consecutive vertices and the other group the third one (thus $c_{i-1},c_{i}\in G_1$, $c_{i+1}\in G_2$)

In this latter case, all we need is a permutation where $G_2$ is after $G_1$, then $c_i$ will be between its neighbors and thus the respective $\ell$ and $r$ vectors won't be negated when taking the sum over the edges of $C$. Similarly, in the first case, we need that $G_2$ is between $G_1$ and $G_3$.

Therefore, it is enough to show that for $m=\frac nk$ elements there are $O(\log m)$ permutations such that for any three elements $G_1,G_2,G_3$ there is a permutation in which $G_1<G_2<G_3$. A standard probabilistic argument shows that $O(\log m)$ random permutations work. In more detail, there are $m^3$ ordered triples, each permutation has probability $\frac 16$ to work for each triple, thus if we take $t$ independent permutations, the chance for any ordered tripe that none of the permutations work for it is $(1-\frac 16)^t$ and taking the union bound we need $m^3(1-\frac 16)^t<1$.