## “n-partite n-clique” with added conditions

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?

-
 Why would you conjecture this after mathoverflow.net/questions/65952/… failed? – Douglas Zare May 27 2011 at 14:59 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 – Pawan Aurora May 27 2011 at 16:50 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" ;). – fedja May 27 2011 at 18:58 We do have some evidence, that is why we would like it to be true – Pawan Aurora May 27 2011 at 19:22 @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. – Douglas Zare May 28 2011 at 1:19
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.
 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}$. – Pawan Aurora May 29 2011 at 3:49 Since when is -3=0 a nonresidue modulo 3? – fedja May 29 2011 at 14:20 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? – Pawan Aurora May 29 2011 at 18:39 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. – fedja May 29 2011 at 21:20 You are right. I wish I could think like you. – Pawan Aurora May 30 2011 at 4:56