The following problem emerged from my project about distributed computing. First some definitions:

Let $1\leqslant m \leqslant n$, $N=\{ 1,\ldots,n\}$. The Johnson graph $J_{n,m}$ has as vertex set all subsets of $N$ of cardinality $m$, two vertices $b_1,b_2$ are adjacent if and only if $\lvert b_1 \cap b_2 \rvert = m - 1$. Let $V_{n,m}=V(J_{n,m})$. If $U\subset V_{n,m}$, define the set $\zeta(U)$ as

$\zeta(U)= \{ c\cup d \mid c,d \in U \wedge \lvert c \cap d \rvert = m - 1 \}$.

Notice that each $f\in \zeta(U)$ has size $m+1$, because, if $f= c\cup d$ for $c,d \in U$, then $\lvert c \rvert = \lvert d \rvert = m$ and it is known that $\lvert c \cap d \rvert = m - 1 \Leftrightarrow \lvert c \cup d \rvert = m + 1$. Thus $\zeta(U)\subseteq V_{n,m+1}$.

The problem: Suppose that $U\subset 2^N$ is a collection of subsets of $N$, all of them of size m. Assume also that $\lvert U \rvert \leqslant n - m$ and that the subgraph $G\left[ U \right]$ of $J_{n,m}$ induced by $U$ is disconnected.

Then prove that $\bigcup_{b\in \zeta(U)}b \neq N \vee G\left[ \zeta(U) \right]$ is a disconnected subgraph of $J_{n,m+1}$.

The hard part of the proof, in which i have been unsuccessful, is when we suppose that $\bigcup_{b\in \zeta(U)}b = N$, we have to show that $G\left[ \zeta(U) \right]$ is disconnected.

Can anyone shed some light on this matter ? Any hints or references ?

Thanks a lot for all your comments !!!


------------- Update -----------------

Trying to solve this question, i have discovered some facts that could be useful.

  1. Let $1\leqslant m \leqslant n$. If $G$ is a connected subgraph of $J_{n,m}$ then $\lvert \bigcup_{b\in V(G)}b \rvert \leq m + \lvert V(G) \rvert - 1$.
  2. Let $1\leqslant m \leqslant n$ and $U\subseteq V_{n,m}$ with $\lvert U \rvert \leqslant n - m$. If $G\left[U\right]$ is connected then $\bigcup_{b\in U}b \neq N$.
  3. Let $U\subset V_{n,m}$ such that $\bigcup U \neq N$. Then $\bigcup \zeta(U) \neq N$.
  • $\begingroup$ what is it you denote by $\overline{n}$ ? Do you mean $N$ ? $\endgroup$ – Ewan Delanoy Oct 1 '12 at 14:14
  • $\begingroup$ Yes, indeed. thanks for pointing out that. I have corrected the last three facts with the correct symbol for the set $\{1, \ldots, n \}$. $\endgroup$ – onebengaltiger Oct 2 '12 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.