{
  "abstract": "Bondy and Szwarcfiter defined $\\mathrm{ex}^*(n,F)$ as the largest number of edges in an $n$-vertex graph whose edge set partitions into induced copies of $F$; for $F=2K_2$ the deficiency $\\binom{n}{2}-\\mathrm{ex}^*(n,2K_2)$ is $Θ(n^{3/2})$. We study the ordered relaxation at fixed matching size, in which each part need only be induced in the union of itself with the parts that follow it; write $\\mathrm{ORS}_n(r)$ for the largest number of parts, so that $r\\,\\mathrm{ORS}_n(r)$ is the ordered analogue of $\\mathrm{ex}^*(n,rK_2)$. Our main tool is a characterisation valid for every $r$: an ordered decomposition into induced $r$-matchings is a sequence of steps that start from $K_n$ and repeatedly delete a perfect matching from $2r$ vertices currently spanning a clique. Reading a decomposition backwards turns a condition about the ordering into a reachability question that an exhaustive search can settle. For $r=2$ we determine $\\mathrm{ORS}_n(2)$ exactly at orders five through nineteen, where it takes the values $1,3,5,8,11,14,19,23,28,34,40,47,54,62,70$, and we confine $\\mathrm{ORS}_{20}(2)$ to $\\{78,79\\}$. The counting bound $\\lfloor n(n-4)/4\\rfloor$ is attained at orders five through nine and at eleven, and missed by exactly one part at every other order below twenty, so order eleven is an isolated exception, not a parity effect. Across this range the ordered deficiency equals $\\frac32n+O(1)$, and along powers of two a dyadic construction keeps it below $O(n\\log n)$; whether it is linear for all $n$ is our main open question. The structural results are formalised in Lean 4, and the searches are certified by fail-closed sweeps and an independent checker.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.14695",
  "author_total": 2,
  "authors": [
    {
      "name": "Xidan Song"
    },
    {
      "name": "Ruifeng Cao"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6d464fcabd0bv.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.14695",
  "fulltext_url": null,
  "id": "6d464fcabd0bv",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.14695",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W7203695542",
  "pdf_url": "https://arxiv.org/pdf/2608.14695",
  "pmcid": null,
  "pmid": null,
  "published": "2026-08-30",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6d464fcabd0bv.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:48Z",
      "native_id": "2608.14695",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.14695"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Ordered Ruzsa-Szemeredi Numbers at Matching Size Two",
  "title_text": "Ordered Ruzsa-Szemeredi Numbers at Matching Size Two",
  "type": "preprint",
  "updated_at": "2026-10-30T12:17:48Z",
  "url": "https://research.draconitic.com/paper/6d464fcabd0bv",
  "venue": "arXiv",
  "versions": []
}