14
$\begingroup$

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.

$\endgroup$
9
  • 4
    $\begingroup$ I do not think the tag representation theory is a proper one here. $\endgroup$ Jul 17, 2015 at 7:03
  • $\begingroup$ @AlirezaAbdollahi Actually I do not know. I think this question may have a connection. $\endgroup$
    – Turbo
    Jul 17, 2015 at 10:39
  • $\begingroup$ I see. Maybe a the graph-theory tag is needed. $\endgroup$ Jul 17, 2015 at 11:37
  • $\begingroup$ Tossed in coding-theory tag. Here is my thinking: Let $V$ be the free vector space on the $\binom{n}{2}$ edges of your graph. Let $K$ be the kernel of the map $V \to \mathbb{F}_2^d$ given by your labels. You want $K$ to be large while not containing the characteristic function of any cycle. This reminds me of the coding theory goal of finding large $K$ that does not contain any vector of small Hamming weight. $\endgroup$ Jul 21, 2015 at 3:43
  • 2
    $\begingroup$ @DavidSpeyer: maybe you could come up with a more evocative title for this question? $\endgroup$ Jul 27, 2015 at 3:11

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ No, the cycle basis article is about a different (non-algebraic) invariant of directed graphs. $\endgroup$ Jul 17, 2015 at 16:00
8
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ As a heuristic, there are about $n!$ simple cycles in $K_n$. If we want to get $d$ below $\log_2 n! \approx n \log_2 n$, we need to get the images of the simple cycles in $\mathbb{F}_2^d$ to be abnormally skewed away from $0$. It is easy to think of weights that skew towards zero, but hard to find ways to skew away. $\endgroup$ Jul 21, 2015 at 4:45
  • $\begingroup$ Apparently so. I can't prove any lower bounds, which is frustrating, but there are upwards of $(2^n)!$ simple cycles which only use edges between the two graphs. It doesn't surprise me that I need something like $2^n$ more coordinates to kill them all. $\endgroup$ Jul 21, 2015 at 6:44
  • $\begingroup$ I don't understand what ring structure you want to use on $\mathbb{F}_2^d$ for this strategy, nor particularly why you think these quadratic equations will be easier to make nonzero than the linear ones you started with. Assuming that you are using the finite field of order $2^d$, and arguing heuristically, there are $2^{nd}$ possible choices of the $x_i$. Each quadratic vanishes at about $1/2$ these choices, and there are $\approx n!$ quadratics. (continued) $\endgroup$ Jul 21, 2015 at 12:06
  • $\begingroup$ So I would expect odds of success for an individual choice to be $1/2^{n!}$. So I expect to win if $2^{nd}/2^{n!}>1$, or $d \approx n!$. This is much worse than the $\log_2 n!$ I gave above. Do you have a reason to think you can do better than random? $\endgroup$ Jul 21, 2015 at 12:06
  • $\begingroup$ Why? (Plus more characters.) $\endgroup$ Jul 21, 2015 at 12:09
6
+300
$\begingroup$

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$.

$\endgroup$
37
  • $\begingroup$ I am not understanding this sentence well " Notice that this gives a nonzero sum for a cycle c1c2…ck if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. Therefore, it has a good chance to work for long cycles" and this phrase well "two groups with an eventh element and a third group with an oddth element". What is eventh, oddth mean? $\endgroup$
    – Turbo
    Aug 6, 2015 at 5:29
  • $\begingroup$ In the first for $k=6$, I want that in the order $<$ given by the permutation satisfies $c_1,c_3,c_5<c_2,c_4,c_6$ or $c_1,c_3,c_5>c_2,c_4,c_6$. I hope from this you can also decipher what I meant in the second phrase... $\endgroup$
    – domotorp
    Aug 6, 2015 at 5:33
  • $\begingroup$ "Our strategy will be to take t random permutations (with t⋅2n independent vectors) and take the sums on each edge to take care of all cycles longer than k." t random permutations of what? $\endgroup$
    – Turbo
    Aug 7, 2015 at 17:34
  • $\begingroup$ This is what I mean by alternating permutation en.wikipedia.org/wiki/Alternating_permutation (1<3>2<5>4<6>1). $\endgroup$
    – Turbo
    Aug 7, 2015 at 17:45
  • 1
    $\begingroup$ I have added it. $\endgroup$
    – domotorp
    Aug 9, 2015 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.