{"id":"arxiv/2609.19632","url":"https://arxiv.org/abs/2609.19632","tags":["math.CO"],"score":0,"title":"Ordered matchings versus triangles via pseudorandom triangle-free graphs","domain":"math.CO","source":"arxiv","authors":["Wen Chen","Qizhong Lin","Chunlin You"],"reviews":0,"subject":"math.CO","summary":"For ordered graphs $H_1,\\ldots,H_t$, let $\\rt(H_1,\\ldots,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\\in[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) =Ω\\left(\\frac{n^{4/3}}{(\\log n)^{1/3}}\\right). \\] This strengthens the lower bound $Ω((n/\\log n)^{5/4})$ of Balko and Poljak for such random matchings and improves the general existential…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}