MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## n-partite n-clique

We are given a n-partite graph G. Each partition has n vertices, some of which may be isolated. 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 at least one neighbor in each of the remaining $n-1$ partitions s.t. for a given numbering of the vertices, the n vertices (vertex $V_{ij}$ and its $n-1$ neighbors) form a permutation on the second index. For e.g., consider a 4-partite graph. Each partition has 4 vertices. Using the numbering as given above, vertex $V_{12}$ has as neighbors vertices $V_{21},V_{34},V_{43}$. Vertex $V_{12}$ can have other neighbors as well. We need to show that the graph G will always contain a n-clique. A stronger claim would be to say that every vertex is part of some n-clique.

-
 FWIW here is a reformulation (I think). Let G be a graph with vertex set the edges of the complete bipartite graph K(n,n). Suppose that each vertex of G is contained in a perfect matching in K(n,n) and is joined to all the other edges in that perfect matching. Prove that G contains an n-clique. – gowers May 25 2011 at 12:44 I haven't checked, but it seems likely to me that a random graph will be a counterexample: you need a very high edge probability to get an n-clique and I think probably a lot lower to satisfy your conditions with high probability. – gowers May 25 2011 at 12:52 You would need at least some constraint on the number of isolated vertices, wouldn't you? Currently, the graph with no edges at all is a counterexample. – Klaus Draeger May 25 2011 at 13:45 Yes, of course. I posted the details to finish it off. – fedja May 25 2011 at 13:46

False as stated: take large $n$ and for each vertex $V_{ij}$ choose some random permutation and draw the corresponding edges. Now, we have $n^n$ possible cliques to form. Let's look at the probability that $V_{11},\dots, V_{nn}$ is a clique. The chance that $V_{11}$ acquires $k$ fixed neighbors in this subgraph when its edges are drawn is $\frac{(n-1-k)!}{(n-1)!}$. Multiplying by ${n-1\choose k}$, we see that the chance to get $k$ vertices is less than $\frac 1{k!}$. Thus, if $X_1$ is the number of acquired neighbors for $V_{11}$, then $Ee^{X_1}\le e^e$. Thus $Ee^{\sum X_j}\le e^{en}$ by independence. But the clique means that $\sum X_j\ge n(n-1)/2$, so the probability that we have a given clique is at most $e^{en}e^{-\frac{n(n-1)}2}$, which is smaller than $n^{-n}$ by an order of magnitude.
 In your analysis, do you account for the edges that get added due to the permutations chosen by other vertices? I guess what I am trying to say is that once you have chosen the permutations for the vertices in a partition and added edges, when you are choosing permutations for vertices in the next partition, you only choose from the remaining $(n-2)!$ and so on. – Pawan Aurora May 26 2011 at 5:24 And yes, each partition must contain at least one non-isolated vertex. The structure of the graph should remain consistent with the condition that 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$. What it means is that if there is some vertex in a partition that does not get any neighbor from a particular partition when adding edges, then that vertex must be isolated. – Pawan Aurora May 26 2011 at 5:24 Not really. You said that you do not mind extra edges and you didn't say that the good edge sets must not overlap, so I run full drawing for each vertex. If I get some edges twice, I just consider myself lucky. – fedja May 26 2011 at 22:03