1
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ Why would you conjecture this after mathoverflow.net/questions/65952/n-partite-n-clique failed? $\endgroup$
    – Douglas Zare
    May 27, 2011 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, 2011 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, 2011 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, 2011 at 14:52
  • 1
    $\begingroup$ I meant $l\ne j$, of course. $\endgroup$
    – fedja
    May 28, 2011 at 14:53

1 Answer 1

Reset to default
5
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\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, 2011 at 3:49
  • $\begingroup$ Since when is -3=0 a nonresidue modulo 3? $\endgroup$
    – fedja
    May 29, 2011 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, 2011 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, 2011 at 21:20
  • $\begingroup$ You are right. I wish I could think like you. $\endgroup$
    – Pawan Aurora
    May 30, 2011 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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