Isoperimetric-Cheeger constant for full bipartite graph

231 Views Asked by At

Let $(V_1\bigcup V_2 , V_1\times V_2)$ a full bipartite graph. ($V_1\cap V_2 =\emptyset)$.

Definition for isoperimetric constant: $min\{\frac{|\partial W|}{|W|} : W\subset V , |W| \le \frac{|V|}{2}\}$ when $\partial W$ is the set of edges which cross the cut $W$ i.e $\{u,v\}\in E , u\in W , v\in W^c$.

So what I figured out so far (regarding full-bipartite graph)

Choosing a set of nodes $W \subset V_1$ which satisfies the condition for the isoperimetric constant , $\frac{|\partial W|}{|W|} = \frac{|W|\cdot |V_2| }{|W|} = |V_2|$ , doing the same thing for $W\subseteq V_2 \Rightarrow \frac{|W|\cdot |V_1| }{|W|} = |V_1|$.

Let us show a better result - taking $W_1 \subset V_1$, $W_2\subset V_2$ such that $|W_1|=\frac{|V_1|}{2} ,|W_2|=\frac{|V_2|}{2} $ we get $\frac{{\frac{|V_1|}{2}}\cdot \frac{|V_2|}{2} + {\frac{|V_1|}{2}}\cdot \frac{|V_2|}{2}}{\frac{|V_1|+|V_2|}{2}} = \frac{|V_1||V_2|}{|V_1|+|V_2|}$.

Which satisfies $\frac{|V_1||V_2|}{|V_1|+|V_2|} \le \min\{|V_1| , |V_2|\}$.

I wish to prove that besides some special cases (like $|V_{i}| = 1$ for $i\in \{1,2\}$ this is the isoperimteric constant. I didn't succeed doing it algebraically, I thought maybe some combinatoric might be of an aid , like Hall's marriage theorem or more generally flow networks.

Any approach would be appreciated.

1

There are 1 best solutions below

2
On BEST ANSWER

The cases where $|W_1| = 0$ or $|W_2|=0$ give us $\frac{|\partial W|}{|W|}$ equal to $|V_1|$ or $|V_2|$ respectively.

The rest of the time, if $|W_1| = x \cdot |V_1|$ and $|W_2| = y \cdot |V_2|$, we have $$ \frac{|\partial W|}{|W|} = \frac{x(1-y)|V_1||V_2| + y(1-x)|V_1||V_2|}{x|V_1|+y|V_2|}. $$ As a function of $x$ with $y$ fixed, this has the form $\frac{ax+b}{cx+d}$ with derivative $\frac{a d - b c}{(c x + d)^2}$, and this is either always positive or always negative. So the best choice of $x$ is always either $x=0$ (which we've already considered), $x=1$ (if possible; in this case $y=0$ is best and again we've already considered that) or $x$ running up against the other upper bound $x|V_1| + y|V_2| \le \frac12|V_1| + \frac12|V_2|$.

In other words, it's enough to consider cases where $|W| = \frac12|V|$. In this case, we want to minimize \begin{align} |\partial W| &= |W_1|(|V_2|-|W_2|) + |W_2|(|V_1|-|W_1|) \\ &= |W_1|(|V_2| - \frac12|V|+|W_1|) + (\frac12|V|-|W_1|)(|V_1|-|W_1|) \\ &= 2|W_1|^2 - 2|V_1||W_1| + \frac12|V||V_1| \end{align} and the minimum occurs at the vertex of the parabola, where $|W_1| = \frac12|V_1|$. This leads to $|W_2| = \frac12|V_2|$ and is exactly the case you've considered, which we know is better than both the $|W_1|=0$ and the $|W_2|=0$ cases.

Of course, parity issues affect this slightly.