Timeline for A question on representation of graphs
Current License: CC BY-SA 3.0
43 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 30, 2015 at 22:55 | comment | added | domotorp | I couldn't really simplify but I tried to clear up the proof. | |
| Aug 30, 2015 at 22:54 | history | edited | domotorp | CC BY-SA 3.0 |
improved presentation
|
| Aug 26, 2015 at 0:54 | comment | added | Turbo | Do you have time to post update? | |
| Aug 17, 2015 at 19:38 | comment | added | Turbo | ok thank you very much. I look to your updates (I am thinking of serious connection to another problem as well). | |
| Aug 17, 2015 at 19:31 | comment | added | domotorp | I'm sorry, but I only wrote that I believe there is one. Now I'm a bit busy, but later might come back to this. | |
| Aug 16, 2015 at 11:39 | comment | added | Turbo | Could you post the simplification as well? I still do not completely follow your proof. | |
| Aug 14, 2015 at 7:21 | comment | added | Turbo | You could add a second answer to the question then? | |
| Aug 13, 2015 at 21:22 | comment | added | domotorp | I suppose. I also think that the proof could be greatly simplified. | |
| Aug 13, 2015 at 5:38 | comment | added | Turbo | so you are saying that local action (acting on pairs or triples) here as some global significance (on all alternating cycles)? | |
| Aug 12, 2015 at 18:14 | comment | added | domotorp | I think what helps is that we do something for every pair/triple, there is a lot less of those. | |
| Aug 12, 2015 at 0:11 | comment | added | Turbo | I think something is still wrong. There are $2^{n\log n}$ aternating permutations. I do not think $n\log\log n$ bits of information covering permutations suffices. | |
| Aug 9, 2015 at 18:50 | comment | added | domotorp | I have added it. | |
| Aug 9, 2015 at 18:49 | history | edited | domotorp | CC BY-SA 3.0 |
added 317 characters in body
|
| Aug 9, 2015 at 10:11 | comment | added | Turbo | Could you please elaborate on statement 'A standard probabilistic argument shows that $O(\log m)$ random permutations work' by including a possible proof in your post? | |
| Aug 9, 2015 at 9:03 | comment | added | Turbo | basically we can think of permuting vertices themselves so that with high probability alternating cycles become something else. | |
| Aug 9, 2015 at 8:58 | comment | added | domotorp | OK. For odd cycles it should always work. Anyhow, the "if and only if" sentence turned out to be incorrect, as the boldface sentence after it says, so please ignore it. | |
| Aug 9, 2015 at 8:52 | comment | added | Turbo | I see I am misunderstanding. Your idea may work.. | |
| Aug 9, 2015 at 7:18 | comment | added | Turbo | Fails at alternating even cycle: $v2\rightarrow v3\rightarrow v1\rightarrow v5\rightarrow v4\rightarrow v6\rightarrow v2$. Assigned vectors: $$v2\rightarrow v3: l_3+r_2$$$$v3\rightarrow v1: r_1+l_3$$$$v1\rightarrow v5: r_1+l_5$$$$v5\rightarrow v4: l_5+r_4$$$$v4\rightarrow v6: r_4+l_6$$$$v6\rightarrow v2: l_6+r_2$$ $$\mbox{SUM}=l_3+r_2+r_1+l_3+r_1+l_5+l_5+r_4+r_4+l_4+l_6+l_6+r_2=0.$$ No matter what permutation is used, formula sums to $0$. | |
| Aug 9, 2015 at 7:08 | comment | added | Turbo | 'Notice that this gives a nonzero sum for a cycle c1c2…ck if and only if the length of the cycle is even' seems wrong at atleast odd cycle: $v2\rightarrow v1\rightarrow v5\rightarrow v3\rightarrow v4\rightarrow v2$. Assigned vectors: $$v2\rightarrow v1: l_2+r_1$$$$v1\rightarrow v5: r_1+l_5$$$$v5\rightarrow v3: l_5+r_3$$$$v3\rightarrow v4: r_3+l_4$$$$v4\rightarrow v2: l_4+r_2$$ $$\mbox{SUM}=l_2+r_1+r_1+l_5+l_5+r_3+r_3+l_4+l_4+r_2=l_2+r_2.$$ However I do not know why you even need 'only if' part? | |
| Aug 8, 2015 at 20:12 | comment | added | domotorp | Apparently yes, but let me know if you think the proof is incorrect. | |
| Aug 8, 2015 at 10:18 | comment | added | Turbo | Sorry I meant $2^{\Theta(n^2)}$ different alternating/reverse alternating permutations as we have $\Theta(n^2)$ edges. Does using $\log\frac nk$ permutations suffice? | |
| Aug 8, 2015 at 10:14 | comment | added | domotorp | We use $\log \frac nk$ permutatinos of length $n$ and the proof why this works is in the last paragraph of my answer, let me know if you think any part of that is incorrect. | |
| Aug 8, 2015 at 9:43 | comment | added | Turbo | There are more than $2^{d\log d}\approx 2^{n(\log\log n)\log(n\log\log n)}\approx 2^{n\log n\log\log n}$ different alternating/reverse alternating permutations. How does using $\log\frac{n}k=\log\frac{\log n}{\log\log\log n}$ different permutations of sequences of length $d=O(n\log\log n)$ work? | |
| Aug 8, 2015 at 7:40 | comment | added | domotorp | No, it doesn't. But this is not a problem, because we take many permutations and in at least one of them the cycle won't be alternating. | |
| Aug 7, 2015 at 22:28 | comment | added | Turbo | Because you mention ' Instead, we need that there is a ci such that ci−1 is before it and ci+1 is after it, or the other way around' It seems that you are saying you need that criteria for your labelling to work. I am giving a counter example of a cycle following alternate permutation (which has been the bottle neck) where your criterion is not satisfied. So I am asking does your labelling scheme work in these scenarios of cycle following alternate or reverse alternate permutations? | |
| Aug 7, 2015 at 22:12 | comment | added | domotorp | 1, I never wrote that I wanted directly. 2, The permutation v1->v3->v2->v5->v4->v6 indeed doesn't satisfy the criteria because there is no vi between vi-1 and vi+1, but why is it a problem that it doesn't satisfy the criteria? | |
| Aug 7, 2015 at 22:04 | comment | added | Turbo | This alternating cycle v1->v3->v2->v5->v4->v6->v1 does not satisfy your criteria. There is no vi 'directly' between vi-1 and vi+1. | |
| Aug 7, 2015 at 21:43 | comment | added | domotorp | The cycle is c1c2..ck. We need that in the permutation for at least one i, ci is between ci-1 and ci+1. | |
| Aug 7, 2015 at 21:27 | comment | added | Turbo | what do you mean by this 'Instead, we need that there is a ci such that ci−1 is before it and ci+1 is after it, or the other way around'? Are you implying cycles of form v1v2v3v4v5v6v1? Here V3 is after v2 and v1 is before v2? Or are you saying something else? | |
| Aug 7, 2015 at 21:14 | comment | added | domotorp | I added more details. | |
| Aug 7, 2015 at 21:13 | history | edited | domotorp | CC BY-SA 3.0 |
added 569 characters in body
|
| Aug 7, 2015 at 20:18 | comment | added | Turbo | Something still seems wrong however it is hard to pinpoint. Could you make your proof detailed? | |
| Aug 7, 2015 at 20:04 | comment | added | Turbo | It is a little hard to follow. Could you make your proof a bit more rigorous? | |
| Aug 7, 2015 at 19:43 | comment | added | domotorp | Oops, I think you're right, this proof was wrong. However, I think that the main argument still works, I tried to update my answer, please check it! | |
| Aug 7, 2015 at 19:42 | history | edited | domotorp | CC BY-SA 3.0 |
added 347 characters in body
|
| Aug 7, 2015 at 18:49 | comment | added | Turbo | Yes. Once you order them as say v1,v2,...vn-1,vn. The case I was stuck is how to assign edges vectors so that their even alternating cycles sum to non-zero value. Eg: v1<v3>v2<v5>v4<v6>v1. | |
| Aug 7, 2015 at 18:43 | comment | added | domotorp | I think that we really misunderstand each other. I mean permutations of the vertices, i.e., order them in some way, as $v_{i_1}, v_{i_2},\ldots,v_{i_n}$. | |
| Aug 7, 2015 at 17:45 | comment | added | Turbo | This is what I mean by alternating permutation en.wikipedia.org/wiki/Alternating_permutation (1<3>2<5>4<6>1). | |
| Aug 7, 2015 at 17:34 | comment | added | Turbo | "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? | |
| Aug 6, 2015 at 5:33 | comment | added | domotorp | 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... | |
| Aug 6, 2015 at 5:29 | comment | added | Turbo | 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? | |
| Aug 2, 2015 at 20:24 | history | bounty ended | David E Speyer | ||
| Jul 31, 2015 at 21:17 | history | answered | domotorp | CC BY-SA 3.0 |