{"id":"arxiv/2608.14695","url":"https://arxiv.org/abs/2608.14695","tags":["math.CO","cs.DM"],"score":0,"title":"Ordered Ruzsa-Szemeredi Numbers at Matching Size Two","domain":"math.CO","source":"arxiv","authors":["Xidan Song","Ruifeng Cao"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}