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
    Commented 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
    Commented 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
    Commented 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
    Commented May 28, 2011 at 14:52
  • 1
    $\begingroup$ I meant $l\ne j$, of course. $\endgroup$
    – fedja
    Commented 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
    Commented May 29, 2011 at 3:49
  • $\begingroup$ Since when is -3=0 a nonresidue modulo 3? $\endgroup$
    – fedja
    Commented 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
    Commented 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
    Commented May 29, 2011 at 21:20
  • $\begingroup$ You are right. I wish I could think like you. $\endgroup$
    – Pawan Aurora
    Commented May 30, 2011 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .