Return to Answer

Update 2015.08.07: This proof had an error, as pointed out by Turbo, but hopefully not fatal, below I tried to fix it.

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 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 gives a nonzero sum for a cycle $c_1c_2\ldots c_k$ if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. <- This is false, but luckily we won't need it. Instead, we need that there is a $c_i$ such that $c_{i-1}$ is before it and $c_{i+1}$ is after it, or the other way around. Therefore, it has a good chance to work for long cycles.

Our strategy will be to take $t$ random 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 less than $k$. This in total gives $d\approx t\cdot n + k\log n$.

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

After this we can choose $k=\frac {n\log \log n}{\log n}$ to get the desired $d=O(n\log\log n)$ bound.

Proof of the claim (new). Divide $n$ into groups of size $\frac k3$. Fix an order inside each group, this will be the same in each permutation, which thus practically act on $m=\frac{3n}k$ elements. Every cycle $C$ of length $k$ either has three groups that contain three consecutive vertices from $C$, or two groups, one of which contains two of three consecutive vertices and the other group the third one (this latter case is better for us). For example, $c_1$ and $c_2$ are in the first group, with $c_1<c_2$, while $c_3$ is in the second group. In this case, all we need is a permutation where the second group is after the first group, then $c_2$ will be between its neighbors. Similarly, if $c_1, c_2$ and $c_3$ are all in different groups, then we need that the group of $c_2$ is between the other two groups. Therefore, it is enough to show that for $m=\frac{3n}k$ elements there are $O(\log m)$ permutations such that for any three elements $a,b,c$ there is a permutation in which $a<b<c$. 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$.

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

Update 2015.08.07: This proof had an error, as pointed out by Turbo, but hopefully not fatal, below I tried to fix it.

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 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 gives a nonzero sum for a cycle $c_1c_2\ldots c_k$ if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. <- This is false, but luckily we won't need it. Instead, we need that there is a $c_i$ such that $c_{i-1}$ is before it and $c_{i+1}$ is after it, or the other way around. Therefore, it has a good chance to work for long cycles.

Our strategy will be to take $t$ random 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 less than $k$. This in total gives $d\approx t\cdot n + k\log n$.

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

After this we can choose $k=\frac {n\log \log n}{\log n}$ to get the desired $d=O(n\log\log n)$ bound.

Proof of the claim (new). Divide $n$ into groups of size $\frac k3$. Fix an order inside each group, this will be the same in each permutation, which thus practically act on $m=\frac{3n}k$ elements. Every cycle $C$ of length $k$ either has three groups that contain three consecutive vertices from $C$, or two groups, one of which contains two of three consecutive vertices and the other group the third one (this latter case is better for us). For example, $c_1$ and $c_2$ are in the first group, with $c_1<c_2$, while $c_3$ is in the second group. In this case, all we need is a permutation where the second group is after the first group, then $c_2$ will be between its neighbors. Similarly, if $c_1, c_2$ and $c_3$ are all in different groups, then we need that the group of $c_2$ is between the other two groups. Therefore, it is enough to show that for $m=\frac{3n}k$ elements there are $O(\log m)$ permutations such that for any three elements $a,b,c$ there is a permutation in which $a<b<c$. A standard probabilistic argument shows that $O(\log m)$ random permutations work.

Update 2015.08.07: This proof had an error, as pointed out by Turbo, but hopefully not fatal, below I tried to fix it.

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 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 gives a nonzero sum for a cycle $c_1c_2\ldots c_k$ if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. <- This is false, but luckily we won't need it. Instead, we need that there is a $c_i$ such that $c_{i-1}$ is before it and $c_{i+1}$ is after it, or the other way around. Therefore, it has a good chance to work for long cycles.

Our strategy will be to take $t$ random 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 less than $k$. This in total gives $d\approx t\cdot n + k\log n$.

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

After this we can choose $k=\frac {n\log \log n}{\log n}$ to get the desired $d=O(n\log\log n)$ bound.

Proof of the claim (new). Divide $n$ into groups of size $\frac k3$. Fix an order inside each group, this will be the same in each permutation, which thus practically act on $m=\frac{3n}k$ elements. Every cycle $C$ of length $k$ either has three groups that contain three consecutive vertices from $C$, or two groups, one of which contains two of three consecutive vertices and the other group the third one (this latter case is better for us). For example, $c_1$ and $c_2$ are in the first group, with $c_1<c_2$, while $c_3$ is in the second group. In this case, all we need is a permutation where the second group is after the first group, then $c_2$ will be between its neighbors. Similarly, if $c_1, c_2$ and $c_3$ are all in different groups, then we need that the group of $c_2$ is between the other two groups. Therefore, it is enough to show that for $m=\frac{3n}k$ elements there are $O(\log m)$ permutations such that for any three elements $a,b,c$ there is a permutation in which $a<b<c$. 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$.

Update 2015.08.07: This proof had an error, as pointed out by Turbo, but hopefully not fatal, below I tried to fix it.

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 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 gives a nonzero sum for a cycle $c_1c_2\ldots c_k$ if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. <- This is false, but luckily we won't need it. Therefore, it has a good chance to work for long cycles.

Our strategy will be to take $t$ random 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 less than $k$. This in total gives $d\approx t\cdot n + k\log n$.

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

After this we can choose $k=\frac {n\log \log n}{\log n}$ to get the desired $d=O(n\log\log n)$ bound.

Proof of the claim (new). Divide $n$ into groups of size $\frac k3$. Fix an order inside each group, this will be the same in each permutation. Every cycle of length $k$ either has three groups that contain three consecutive vertices, or two groups, one of which contains two of three consecutive vertices and the other group the third one (this latter case is better for us). Therefore, it is enough to show that for $m=\frac{3n}k$ elements there are $O(\log m)$ permutations such that for any three elements $a,b,c$ there is a permutation in which $a<b<c$. A standard probabilistic argument shows that $O(\log m)$ random permutations work.

Update 2015.08.07: This proof had an error, as pointed out by Turbo, but hopefully not fatal, below I tried to fix it.

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 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 gives a nonzero sum for a cycle $c_1c_2\ldots c_k$ if and only if the length of the cycle is even and every eventh vertex comes before (or after) every oddth vertex. <- This is false, but luckily we won't need it. Instead, we need that there is a $c_i$ such that $c_{i-1}$ is before it and $c_{i+1}$ is after it, or the other way around. Therefore, it has a good chance to work for long cycles.

Our strategy will be to take $t$ random 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 less than $k$. This in total gives $d\approx t\cdot n + k\log n$.

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

After this we can choose $k=\frac {n\log \log n}{\log n}$ to get the desired $d=O(n\log\log n)$ bound.

Proof of the claim (new). Divide $n$ into groups of size $\frac k3$. Fix an order inside each group, this will be the same in each permutation, which thus practically act on $m=\frac{3n}k$ elements. Every cycle $C$ of length $k$ either has three groups that contain three consecutive vertices from $C$, or two groups, one of which contains two of three consecutive vertices and the other group the third one (this latter case is better for us). For example, $c_1$ and $c_2$ are in the first group, with $c_1<c_2$, while $c_3$ is in the second group. In this case, all we need is a permutation where the second group is after the first group, then $c_2$ will be between its neighbors. Similarly, if $c_1, c_2$ and $c_3$ are all in different groups, then we need that the group of $c_2$ is between the other two groups. Therefore, it is enough to show that for $m=\frac{3n}k$ elements there are $O(\log m)$ permutations such that for any three elements $a,b,c$ there is a permutation in which $a<b<c$. A standard probabilistic argument shows that $O(\log m)$ random permutations work.