We are given a $n$-partite weighted graph $G$. Each partition has $n$ vertices, some of which may be isolated. Each partition must contain at least one non-isolated vertex. Let us number the vertices in some $i^{th}$ partition as $V_{i1},V_{i2},...,V_{in}$. Now each non-isolated vertex $V_{ij}$ has a set of $n-1$ neighbors (one in each of the remaining $n-1$ partitions) that form a permutation with $j$. Vertex $V_{ij}$ can have other neighbors as well. In fact it can have several such sets of neighbors.

Every non-isolated vertex has a positive weight $w_{ij}$ and every edge $(V_{ij},V_{kl})$ has a positive weight $e_{ijkl}$. For every non-isolated vertex $V_{ij}$, the following must be true $w_{ij}=\sum_{l}e_{ijkl}\forall k(\neq i)=\sum_{k}e_{ijkl}\forall l(\neq j)$. As a consequence of this condition, if a vertex has only one neighbor at position $l$ (of some partition $k$) among all partitions, then it cannot have any other neighbor in that partition $k$. Also, if a vertex has only one neighbor in some partition $k$ (at some position $l$), then it cannot have any neighbor at that position in any other partition.

We conjecture that the graph $G$ will always contain a $n$-clique. Is it true?

  • $\begingroup$ Why would you conjecture this after mathoverflow.net/questions/65952/n-partite-n-clique failed? $\endgroup$ – Douglas Zare May 27 '11 at 14:59
  • $\begingroup$ 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 $\endgroup$ – Pawan Aurora May 27 '11 at 16:50
  • 1
    $\begingroup$ 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" ;). $\endgroup$ – fedja May 27 '11 at 18:58
  • 1
    $\begingroup$ 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. $\endgroup$ – fedja May 28 '11 at 14:52
  • 1
    $\begingroup$ I meant $l\ne j$, of course. $\endgroup$ – fedja May 28 '11 at 14:53

Take $n$ prime and connect $(i,j)$ with $(k,l)$ if $(i-k)(j-l)\equiv 1\mod n$. Clearly, each vertex has one neighbor in each row and column except its own. Also, if $xy=1$ and $zt=1$ in $\mathbb Z_n$, then there is no reason to expect that $(x-z)(y-t)=1$ (actually, if $-3$ is not a quadratic residue modulo $n$ (say, $n=5$), it is not merely unlikely but plainly impossible, so this graph contains no triangles, leave alone $n$-cliques.

Now, what are you really after?

  • $\begingroup$ Consider $n=3$. So we have the following edges $(V_{11},V_{22}),(V_{11},V_{33})$ as well as the edge $(V_{22},V_{33})$ apart from some other edges. Clearly we have a triangle (a $3$-clique here) among $V_{11},V_{22},V_{33}$. $\endgroup$ – Pawan Aurora May 29 '11 at 3:49
  • $\begingroup$ Since when is -3=0 a nonresidue modulo 3? $\endgroup$ – fedja May 29 '11 at 14:20
  • $\begingroup$ I am totally lost here. As long as every vertex has exactly one neighbor in each row and column except its own, we always have a $n$-clique. In fact every vertex is part of some $n$-clique. What am i missing here? $\endgroup$ – Pawan Aurora May 29 '11 at 18:39
  • $\begingroup$ OK, you have your proof and I offered my counterexample. Now, we can either check your proof (which may be long and hard) or refute my $n=5$ construction (which should be easy if it is wrong). So, you claim that you can find a triangle in it or a vertex with a wrong set of neighbors. Do it and I'll retract my claim. $\endgroup$ – fedja May 29 '11 at 21:20
  • $\begingroup$ You are right. I wish I could think like you. $\endgroup$ – Pawan Aurora May 30 '11 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.