1
$\begingroup$

We are given an $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 $n$-clique.

A stronger claim would be to say that every vertex is part of some $n$-clique.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – gowers
    May 25, 2011 at 12:44
  • $\begingroup$ 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. $\endgroup$
    – gowers
    May 25, 2011 at 12:52
  • $\begingroup$ 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. $\endgroup$ May 25, 2011 at 13:45
  • $\begingroup$ Yes, of course. I posted the details to finish it off. $\endgroup$
    – fedja
    May 25, 2011 at 13:46

1 Answer 1

3
$\begingroup$

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.

I strongly suspect that you meant something else. Actually, my first impulse when seeing your post was to say "Consider the graph consisting of isolated vertices only" but then I decided that it would be too cheap.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 26, 2011 at 5:24
  • $\begingroup$ 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. $\endgroup$ May 26, 2011 at 5:24
  • $\begingroup$ 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. $\endgroup$
    – fedja
    May 26, 2011 at 22:03

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.