Author

Xi-Dan Song

h-index 1 View on Semantic Scholar

We have 2 of 4 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Ordered Ruzsa-Szemeredi Numbers at Matching Size Two

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 $\Theta(n^{3/2})$. We study the ordered relaxation at fixed matching size, in which each part...

Xi-Dan Song, Rui-Feng Cao · 0 citations

Preprint Aug 2026

Exact Ordered Ruzsa-Szemeredi Numbers for Matchings of Size Two

An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it. Behnezhad and Ghafari introduced them to parametrize the update time of fully dynamic matching, but almost nothing is known about the numbers themselves. W...

Xi-Dan Song, Ruifeng Cao · 0 citations