The Upper Matching Conjecture

At least 19 years old · documented by 2006

Let $G$ be a bipartite $r$ -regular graph on $2qr$ vertices, where $q,r\geq2$ . Let $\Phi_G(x)$ be its matching generating polynomial, and for polynomials $f,g\in\mathbb{R}[x]$ write $g\succeq f$ when $g-f$ has nonnegative coefficients. Let $qK_{r,r}$ be the disjoint union of $q$ copies of the complete bipartite graph $K_{r,r}$ .

The Upper Matching Conjecture. One has

\Phi_G\preceq\Phi_{qK_{r,r}},

and equality holds only if $G=qK_{r,r}$ .

This conjecture is proved for $r=2$ . It asserts that the disjoint union of complete bipartite graphs maximizes every matching coefficient among bipartite $r$ -regular graphs with the same number of vertices; the cases $r\geq3$ remain open.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Upper matching conjecture
Let $G=(V,E)$ be a finite bipartite $r$ -regular graph on $2qr$ vertices, where $q,r\in\mathbb{N}$ and $q,r\geq2$ . Let $K_{r,r}$ be the complete bipartite graph on $2r$ vertices, and let $qK_{r,r}$ be the disjoint union of $q$ copies of $K_{r,r}$ . Upper matching conjecture. For every $l=0,\ldots,qr$ ,
$\phi(l,G)\leq\phi(l,qK_{r,r}).$
The conjecture is proved in the source's cited earlier work for $r=2$ , is trivial for $l=0,1$ , and follows for $l=qr$ from the Minc conjecture proved by Bregman. The general case remains unresolved in the supplied text.
source: Shmuel Friedland, Elliot Krop, Per Hakan Lundow and Klas Markström, “Validations of the Asymptotic Matching Conjectures”, arXiv:math/0603001 (2008).

References

Primary source

Shmuel Friedland and Leonid Gurvits, “Generalized Friedland-Tverberg inequality: applications and extensions”, arXiv:math/0603410 (2006).

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Upper matching conjecture

Primary source

Progress summary