Ordered matchings versus triangles via pseudorandom triangle-free graphs

@misc{chen2026ordered,
  title = {{Ordered matchings versus triangles via pseudorandom triangle-free graphs}},
  author = {Wen Chen and Qizhong Lin and Chunlin You},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19632},
  eprint = {2609.19632},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19632},
}

TY  - UNPB
TI  - Ordered matchings versus triangles via pseudorandom triangle-free graphs
AU  - Wen Chen
AU  - Qizhong Lin
AU  - Chunlin You
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.19632
UR  - https://arxiv.org/abs/2609.19632
AB  - For ordered graphs H_1,…,H_t, let rt(H_1,…,H_t) denote the least integer N such that every t-coloring of the edges of the naturally ordered complete graph on [N] contains an ordered copy of H_i in color i for some i∈[t]. We prove that a uniformly random ordered matching M on n vertices with interval chromatic number two asymptotically almost surely satisfies rt(K_3,M) =Ω(n^4/3/((log n)^1/3)). This strengthens the lower bound Ω((n/log n)^5/4) of Balko and Poljak for such random matchings and improves the general existential lower bound of Conlon, Fox, Lee and Sudakov by a factor of log n. The proof combines pseudorandom triangle-free graphs, a coarse encoding of order-preserving embeddings, and a permutation avoidance estimate derived from Brègman's inequality.
ER  -