4
$\begingroup$

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form of the network problem I am working on in distributed computing.

N.B.: all the graphs mentioned below are simple and undirected.

TL;DR

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

Notation and Claim

A biregular or semiregular bipartite graph is a bipartite graph $G = (U, V, E)$ where the vertices in each bipartition $U$ or $V$ have the same degree. An $(x, y)$-biregular graph is a biregular graph $G = (U, V, E)$ where all vertices in $U$ have degree $x$ and the ones in $V$ have degree $y$ (from Wikipedia). We have $x|U| = y|V|$ immediately.

Let $|U| = ab$ and $|V| = a$. Then $bx = y$ and $1 \leq x \leq a$.

Claim. An $(x, bx)$-biregular graph $G = (U, V, E)$ always contains at least one $x$-regular bipartite subgraphs.

And the beauty of the claim is that if it holds, we are guaranteed to keep removing such a subgraph from $G$ by recursively applying the claim — an $(x, bx)$-biregular graph $G = (U, V, E)$ is now decomposed into $b$ edge-disjoint $x$-regular bipartite subgraphs.

Here is a visual example with $a = 4$, $b = 3$ and $x = 2$ (hence $|U| = 12$ and $|V| = 4$). The edges with the same colour consist of a subgraph.

Some trivial cases:

  1. When $x = a$, meaning $G$ is complete and biregular, the claim holds.
  2. When $x = 1$, $G$ is disconnected but it is still the case.
  3. When $b = 1$, $G$ is a $x$-regular bipartite graph itself.

Possible Areas

After a long time online searching, I found three areas may be related to the claim potentially:

  1. Hypergraphs or family of sets: in such context, it can be paraphrased into that a multiple $x$-uniform $bx$-regular hypergraph with $abx$ hyperedges includes an $x$-uniform $x$-regular partial subhypergraph with $a$ hyperedges.
  2. Block design or more generally, combinatorial design: the claim now becomes that a 1-$(a, x, bx)$ design comprises a 1-$(a, x, x)$ sub-design; the sub-design is symmetric (the number of points equals the number of blocks) and not necessarily simple (no repeated blocks allowed).
  3. Algebraic graph theory: the adjacency matrix of a bipartite graph is quite unique, let alone that of a biregular one; with linear-algebraic or group-theoretic techniques, we may have a solution.

The Question

It is threefold:

  1. Do there exist some pre-existed results leading to the claim?
  2. Is there a better way to efficiently come up with a possible counter-example? I just wrote a Python script to randomly generate such a biregular graph and output a list of all its regular bipartite subgraphs by the brute-force search (to avoid any bias caused by heuristic algorithms). If someone is interested, I can link the script here.
  3. In order to prove/disprove the claim, which other mathematical fields are the most likely to be helpful here?

Thanks in advance from a computer scientist!

$\endgroup$
1
  • 1
    $\begingroup$ For fixed $a,b$, replacing $x$ with $a-x$ can be achieved via complementing the graphs. Hence, without loss of generality, one can assume $x \leq a/2$. $\endgroup$ Feb 18 at 21:16

3 Answers 3

3
$\begingroup$

With $x=2$ and $b \ge 1$ the claim is true.

Proof: Since $G$ has no degree-$1$ vertices, it is not a forest, so it contains at least one cycle. The cycle is your $2$-regular subgraph.


With $x=3$ and $b=4/3$ the claim is false. The following $(3,4)$-biregular graph has no $3$-regular subgraph.

(3,4)-biregular graph with no 3-regular subgraph

This example is Figure 2 in Asratian et al. (2009). They note that it has no full $3$-regular subgraph (full meaning "one that covers all of the $4$-degree vertices"), but we can in fact find that it has no $3$-regular subgraph at all. It suffices to consider all $2^8-1=255$ nonempty subsets of the $3$-degree vertices (lower layer); in each case, take the subgraph of those vertices and all their neighbors; and observe that in all cases the resulting subgraph is noncubic. (This was, of course, a straightforward computational way; surely there are finer methods.)

To provide some context (and to address the question "which mathematical fields are likely to be helpful"): It seems that regular subgraphs of biregular graphs are relevant in interval coloring, which is edge-coloring with certain constraints. Most results that I quickly found are in the direction "if there is a regular subgraph with so-and-so properties, then you have an interval coloring".

Asratian, Armen S.; Casselgren, Carl Johan; Vandenbussche, Jennifer; West, Douglas B., Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs, J. Graph Theory 61, No. 2, 88-97 (2009). ZBL1198.05037.

$\endgroup$
2
$\begingroup$

Here is a heuristic reason why such a claim cannot hold. I cannot make the claim rigorous as I don't know enough about random biregular bipartite graphs.

If the claim indeed holds, then for any $(x, bx)$-regular graph with $|U| = ab$, there must exist a $W \subset U$ such that $|W| = a$ and $(W, N(W) = T)$ is a $x$-regular graph.

Now consider a random $(x, bx)$-regular graph with $x = \frac{a}{2}$ and $b = 2$. My intuition says that the following holds.

  1. The graph is an expander with high probability. That is $|W| < |N(W)|$ unless $|N(W)| > a / 2$. For otherwise, by assigning negative weights to $W$ and positive weights to $V - N(W)$ and $U - W$, the graph is going to have second eigenvalue $\Theta(x)$, whereas in reality, the second eigenvalue is $O(\sqrt{x})$ with high probability. This rules out the possibility of $W$ being small.

  2. For any fixed $(W, T)$ with $|W| = |T|, W \subset U, T \subset V$, the degree sequence of the subgraph spanned $(W, T)$ is going to follow a normal distribution, which has PDF at most $O(\sqrt{x}^{-1})$ at any point. Thus, the probability that the subgraph is exactly $x$-regular is $$\Theta(\sqrt{x})^{-|W| -|T|}.$$ Finally, as we only need to consider $|W|, |T| \geq a/2$, this probability is at most $$\Theta(\sqrt{x})^{-a}.$$ So by the union bound over all $(W, T)$, the probability that we can find such $W, T$ is at most $$2^{|U| + |V|}\Theta(\sqrt{x})^{-a} = o(1).$$ So with high probability, such a $(W, T)$ pair does not exist.

$\endgroup$
2
$\begingroup$

The claim does not hold. Here is a counterexample with $a=7$, $b=2$ and $x=3$.

This graph has partite sets of sizes $|U|=14$ and $|V|=7$. Labeling vertices of $V$ as $1,2,\dots,7$, the vertices in $U$ (each of degree 3) are connected to $$127,\ 127, 136,\ 136,\ 145,\ 157,\ 235,\ 246,\ 246,\ 256,\ 347,\ 347,\ 356, 457.$$

I have computationally verified that this graph has no 3-regular subgraph. It is the smallest counterexample with respect to the total number of vertices (with integer $b$), and it's unique for 21 vertices.


Here is the graph drawing:

Graph drawing

And here is its graph6 string:

T@C?GG@COC?O?OC_AO?a??oBk_E?{@O[b?`g

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.