MathDB

The Upper Matching Conjecture

From papers

Let GG be a bipartite rr-regular graph on 2qr2qr vertices, where q,r≥2q,r\geq2. Let ΦG(x)\Phi_G(x) be its matching generating polynomial, and for polynomials f,g∈R[x]f,g\in\mathbb{R}[x] write g⪰fg\succeq f when g−fg-f has nonnegative coefficients. Let qKr,rqK_{r,r} be the disjoint union of qq copies of the complete bipartite graph Kr,rK_{r,r}.

The Upper Matching Conjecture. One has

ΦG⪯ΦqKr,r,\Phi_G\preceq\Phi_{qK_{r,r}},

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

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

Progress summary

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

Equivalent formulations 1

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

  1. Upper matching conjecture

    Let G=(V,E)G=(V,E) be a finite bipartite rr-regular graph on 2qr2qr vertices, where q,r∈Nq,r\in\mathbb{N} and q,r≥2q,r\geq2. Let Kr,rK_{r,r} be the complete bipartite graph on 2r2r vertices, and let qKr,rqK_{r,r} be the disjoint union of qq copies of Kr,rK_{r,r}. Upper matching conjecture. For every l=0,…,qrl=0,\ldots,qr,

    ϕ(l,G)≤ϕ(l,qKr,r).\phi(l,G)\leq\phi(l,qK_{r,r}).

    The conjecture is proved in the source's cited earlier work for r=2r=2, is trivial for l=0,1l=0,1, and follows for l=qrl=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).

Sources & referencesView supporting material

Primary source

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

bipartite-graphsextremal-combinatoricsmatching-theory

Solutions 0

No solutions have been posted yet.