Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ colors, and let $H(G)$ denote the number of partitions of $Y$ into $d$ sets $Y_1, ... ,Y_d$ of size $n/d$ such that for every $1 \leq i \leq d$ there holds $$ \bigcup_{y \in Y_i}\Gamma(y) = X, $$ where $\Gamma(y) = \{x:x \sim y\}$ is the neighborhood of $y$. Basically, $H(G)$ is counting the number of ways to partition $Y$ into vertex covers.

I want to prove the best inequality I can of the form $$ H(G) \leq f(d,n) \cdot F(G). $$ Here's what I know:

From an inequality of Schrijver, the number of 1-factorizations of $G$ is at least $\left(\frac{d!^2}{d^d}\right)^n$.

On the other hand, I claim that the number of ways to choose $Y_1$ is at most $d^{n/d}$. Indeed, let $x_1$ be an uncovered vertex of $X$. Then there must be a vertex $y_1 \in Y_1$ such that $y_1 \sim x_1$. Since $x_1$ has $d$ neighbors, there are $d$ choices for such a vertex $y_1$. Then we choose another uncovered vertex $x_2$, and again there are at most $d$ choices for $y_2$, and so on. Since $|Y_1|=n/d$, we get the desired bound on the number of ways to choose $Y_1$.

Now, deleting the vertices and edges of $Y_1$ leaves $X$ $(d-1)$-regular, and so the number of ways to choose $Y_2$ is at most $(d-1)^{n/d}$. Continuing in this fashion, we get the bound $H(G)\leq d!^{n/d}$. Altogether, we have shown that $$ H(G) \leq \left(\frac{d^d d!^{1/d}}{d!^{2}}\right)^n F(G). $$

My question is about $H(G)$. It looks like a natural object, but I haven't seen it defined and I don't know anything about it. Do such objects have a name? Are there known bounds on them, better than the bound above?

Also: It is interesting to me that such a bound exists, and it looks like some form of duality. Is there a sense in which H(G) and F(G) are dual to one another?

  • 1
    $\begingroup$ When your bound on $H(G)$ is sharp, $G$ is a disjoint union of complete bipartite $(d,d)$-graphs. In this case $F(G)$ seems to be much larger than the minimal possible (at least, this is true when $d=2$). So I would assume that the constant can be improved... $\endgroup$ – Ilya Bogdanov Oct 22 '15 at 18:58

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.