ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a graph GG, let ν(G)\nu(G) denote its matching number and νur(G)\nu_{ur}(G) its uniquely restricted matching number. For every positive real number ϵ\epsilon and every positive integer Δ\Delta, consider graphs of maximum degree at most Δ\Delta and girth at least gg. High-girth approximation conjecture. There is some positive integer g=g(ϵ,Δ)g=g(\epsilon,\Delta) such that

νur(G)≥(1−ϵ)ν(G)\nu_{ur}(G)\geq (1-\epsilon)\nu(G)

for every graph GG of maximum degree at most Δ\Delta and girth at least gg. The conjecture asserts that, for fixed maximum degree, sufficiently large girth makes the uniquely restricted matching number asymptotically as close as desired to the ordinary matching number; the source gives no resolution, so it remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.