Timeline for "n-partite n-clique" with added conditions
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 11, 2013 at 18:32 | review | Close votes | |||
| Sep 23, 2013 at 3:03 | |||||
| May 30, 2011 at 4:57 | vote | accept | Pawan Aurora | ||
| May 28, 2011 at 20:35 | answer | added | fedja | timeline score: 5 | |
| May 28, 2011 at 15:53 | comment | added | Pawan Aurora | Thanks again and sorry for assuming these things are implied | |
| May 28, 2011 at 15:50 | history | edited | Pawan Aurora | CC BY-SA 3.0 |
fixed an equation
|
| May 28, 2011 at 14:53 | comment | added | fedja | I meant $l\ne j$, of course. | |
| May 28, 2011 at 14:52 | comment | added | fedja | Now, check what you are posting. I really mean it. Look at the condition you wrote and sum all edge weights looking columnwise. You'll get (n-1) times the sum of $w_{ij}$. Now do it rowwise. You'll get $n$ times the sum of $w_{ij}$. Nonsense, isn't it? I suspect that $l\le j$ is missing but I'm too lazy to make guesses. | |
| May 28, 2011 at 3:30 | comment | added | Pawan Aurora | If you try with smaller graphs and choose random permutations to add edges, as was suggested in the argument that disproved my earlier conjecture, you would end up getting a graph that has no $n$-clique, but then the new set of conditions would force a lot of those random edges to disappear and the permutation condition would get violated. On the other hand, if you start with a graph that has a $n$-clique, these conditions should remain satisfied. | |
| May 28, 2011 at 3:30 | comment | added | Pawan Aurora | Actually I am trying to abstract my real problem as a graph theoretic one in hope to simplify the understanding and help find a proof. The new set of conditions are more difficult to analyze (I guess), that is why in my previous conjecture, I tried to use a condition that followed from these conditions but perhaps did not capture everything. It might be possible that I am still missing something, but its worth trying to prove or disprove the conjecture. | |
| May 28, 2011 at 1:19 | comment | added | Douglas Zare | @Pawan Aurora: Could you say what your evidence is? My intuition is that your first conjecture failed heuristically, and this one adds a mild condition which shouldn't change the basic source of counterexamples people gave to your first version. I've looked at the problem of forcing a clique to exist in an $n$-partite graph, and in that general setting I needed a lot more edges than what you appear to be assuming. | |
| May 27, 2011 at 19:30 | history | edited | Pawan Aurora | CC BY-SA 3.0 |
fixed an equation
|
| May 27, 2011 at 19:22 | comment | added | Pawan Aurora | We do have some evidence, that is why we would like it to be true | |
| May 27, 2011 at 18:58 | comment | added | fedja | Erm. When $k=i$, the first sum is surely $0$ (there are no edges to its own part), so you'd better check what you wrote. By the way, the word "conjecture" doesn't mean "something I would like to be true". It means "something for which I have a lot of evidence but no proof" ;). | |
| May 27, 2011 at 17:26 | history | edited | Pawan Aurora | CC BY-SA 3.0 |
added text
|
| May 27, 2011 at 16:50 | comment | added | Pawan Aurora | The permutation condition is actually a consequence of the new set of conditions. Although it limits the number of legal edges these edges should fall at the right places | |
| May 27, 2011 at 14:59 | comment | added | Douglas Zare | Why would you conjecture this after mathoverflow.net/questions/65952/n-partite-n-clique failed? | |
| May 27, 2011 at 14:35 | history | asked | Pawan Aurora | CC BY-SA 3.0 |