ÐÓ°ÉÂÛ̳

Speaker: , associate professor of mathematics, University of West Virginia

Title: Ramsey Numbers of Cross-Free Matchings in Ordered Graphs

Abstract: An \emph{ordered graph} is one whose vertices are linearly ordered. A pair of edges \(\{uv,xy\}\) in an ordered graph with distinct endpoints may be \emph{separated} (e.g. \(u<v<x<y\)), \emph{nested} (e.g. \(u<x<y<v\)) or \emph{crossing} (e.g. \(u<x<v<y\)). An ordered graph \(G\) is \emph{cross-free} if \(G\) does not contain a pair of crossing edges.

Let \(\mathsf{CF}_m\) be the family of ordered graphs on \(2m\) vertices whose edge set forms a cross-free perfect matching. Many classical extremal problems extend naturally to ordered graphs. For a family of ordered graphs \(\mathcal{F}\), the \emph{multi-color Ramsey number} of \(\mathcal{F}\), denoted \(R(\mathcal{F}; k)\) is the minimum \(n\) such that every \(k\)-edge-coloring of the \(n\)-vertex complete ordered graph contains a monochromatic copy of some member of \(\mathcal{F}\). In 2022, Bárat, Gyárfás, and Tóth proved that \(R(\mathsf{CF}_2; k) > k+3\). We prove that \(k + (1-o(1))\sqrt{(4/\pi)k} \le R(\mathsf{CF}_2; k) \le k+1+\left\lceil {\sqrt{2k}} \right\rceil\).

Discrete Applied Math Seminar