The extremal matching conjecture for almost alternating threshold graphs

Let k0k\geq 0. Let AA be an almost alternating threshold graph, and let GG be a threshold graph with the same number of vertices and edges as AA. Write mk(H)m_k(H) for the number of matchings of size kk in a graph HH. Extremal matching conjecture. Then

mk(G)mk(A).m_k(G)\leq m_k(A).

In addition, if k2k\geq 2, mk(A)>0m_k(A)>0, and GG is not almost alternating, then

mk(G)<mk(A).m_k(G)<m_k(A).

The paper establishes that almost alternating threshold graphs maximize the total number of matchings, but its methods do not extend to matchings of a fixed size kk. Computer testing through 2222 vertices supports this stronger fixed-size assertion, which remains open.

Sources & referencesView supporting material

Primary source

L. Keough and A. J. Radcliffe, “Extremal Threshold Graphs for Matchings and Independent Sets”, arXiv:1710.00083 (2017).

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.

Solutions 0

No solutions have been posted yet.