most recent 30 from http://mathoverflow.net 2013-05-24T16:19:32Z http://mathoverflow.net/feeds/question/66195 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66195/n-partite-n-clique-with-added-conditions Pawan Aurora 2011-05-27T14:35:24Z 2011-05-28T20:35:52Z

<p>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.</p> <p>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.</p> <p>We conjecture that the graph $G$ will always contain a $n$-clique. Is it true?</p>

http://mathoverflow.net/questions/66195/n-partite-n-clique-with-added-conditions/66309#66309 fedja 2011-05-28T20:35:52Z 2011-05-28T20:35:52Z

<p>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.</p> <p>Now, what are you really after? </p>