Matchings avoiding ordered patterns

János Barát · 2025

Read Matchings avoiding ordered patterns by János Barát (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-15461.txt.

Introduction

Janos Barat, Andrea Freschi, and Geza Toth study matchings that avoid ordered patterns in a 2025 combinatorics paper. In an ordered graph the vertices come in a fixed line, and two disjoint edges can sit separated, nested, or crossing. For each pattern type, the question is how many edges a graph can have without containing a matching where every pair shows that pattern.

Exact answers were known for four of six cases. The authors settle the non separated case, with a maximum near three halves of (k minus 1) times n. For the non nested case they pin the maximum between two close bounds. They also solve a related question about alternating paths of a given length.

Catalog record

CREATORJános Barát
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-15461

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Matchings avoiding ordered patterns Thanks: Supported by ERC Advanced Grants “GeoScape”, no. 882971 and “ERMiD”, no. 101054936. E-mail: [email protected] . Thanks: Supported by National Research, Development and Innovation Office, NKFIH, K-131529, ADVANCED-152590 and ERC Advanced Grant “GeoScape” 882971. E-mail: [email protected] János Barát Abstract A vertex-ordered graph is a graph equipped with a linear ordering of its vertices. A pair of independent edges in an ordered graph can exhibit one of the following three patterns: separated, nested or crossing. We say a pair of independent edges is non-separated if it is either crossing or nested. Non-nested and non-crossing pairs are defined analogously. We are interested in the following Turán-type problems: for each of the aforementioned six patterns, determine the maximum number of edges of an n n -vertex ordered graph that does not contain a k k -matching such that every pair of edges exhibit the fixed pattern. Exact answers have already been obtained for four of the six cases. The main objective of this paper is to investigate the two remaining open cases, namely non-separated and non-nested matchings. We determine the exact maximum number of edges of an n n -vertex ordered graph that does not contain a non-separated k k -matching, which has the form 3 2 ​ ( k − 1 ) ​ n + Θ ⁡ ( k 2 ) \frac{3}{2}(k-1)n+\Theta(k^{2}) . For the non-nested case, we show the maximum number of edges lies between ( k − 1 ) ​ n (k-1)n and ( k − 1 ) ​ n + ( k − 1 2 ) (k-1)n+\binom{k-1}{2} . We also determine the exact maximum number of edges of an n n -vertex ordered graph that does not contain an alternating path of given length. We discuss some related problems and raise several conjectures. Furthermore, our results and conjectures yield consequences to certain Ramsey-type problems for non-nested matchings and alternating paths. 1 Introduction A (vertex-)ordered graph is a graph equipped with a linear ordering on its vertex set. For simplicity, we always assume that an n -vertex ordered graph has vertex set [n]:=\{1,2,\dots,n\} i.e., the first n positive integers. In recent years, there has been accelerating interest on Turán-type questions for ordered graphs, see e.g. [ 17 ] . For a family of unordered graphs \mathcal{H} , the Turán number ex(n,{\mathcal{H}}) denotes the maximum number of edges of an n -vertex graph, which does not contain a copy of any H\in{\mathcal{H}} . The celebrated Erdős–Stone–Simonovits theorem determines ex({n,\mathcal{H}}) asymptotically for \mathcal{H} fixed, provided \mathcal{H} contains no bipartite graph. Analogous notions exist for ordered graphs. We say an ordered graph G contains a copy of an ordered graph H if there exists an injective graph isomorphism from H to G , which preserves the order of the vertices. Definition 1.1 . Given a family of ordered graphs \mathcal{H} , we write ex_{<}(n,\mathcal{H}) to denote the maximum number of edges in an ordered graph with vertex set [n] not containing any copy of H\in\mathcal{H} . Pach and Tardos established an analogue of the Erdős–Stone–Simonovits theorem in the ordered setting. The crucial parameter here is the interval chromatic number \chi_{<}(H) , defined as the size of a smallest proper interval colouring of H . Theorem 1.2 (Pach and Tardos [ 16 ] ) . For any ordered graph H , we have ex_{<}(n,H)=\left(1-\frac{1}{\chi_{<}(H)-1}+o(1)\right)\frac{n^{2}}{2}. As in the unordered setting, Theorem 1.2 does not provide an asymptotic formula when \chi_{<}(H)=2 , or |V(H)| and n are comparable in size. There has been great interest in studying the \chi_{<}(H)=2 case, sometimes assuming further that the underlying ordered graph can be partitioned into two independent intervals. This setting naturally corresponds to (0,1) -matrices. The extremal theory of (0,1) -matrices include fundamental results by Füredi-Hajnal [ 8 ] and Marcus–Tardos solving the Stanley-Wilf conjecture [ 14 ] . In this paper, we are interested in Turán-type problems for ordered matchings. In order to formulate these questions precisely, we introduce some notation. Let \mathbb{N} denote the set of positive integers. For every a,b\in\mathbb{N} with a\leq b , we write [a,b]:=\{a,a+1,\dots,b\} for the set of integers between a and b (included). We call such a set an interval and the size of an interval is the number of integers in it. Definition 1.3 (Separated, nested and crossing edges) . Let xy and uv be two independent (i.e., vertex-disjoint) edges with x,y,u,v\in\mathbb{N} such that x<y and u<v . We say xy and uv are • separated if the intervals [x,y] and [u,v] are disjoint, • nested if the interval [x,y] contains [u,v] or vice versa, and • crossing otherwise. See Figure 1 for a drawing of these patterns. Figure 1: From left to right: separated, nested and crossing pairs. Definition 1.4 ( k -matchings with special patterns) . A matching is a collection of independent edges. A matching consisting of k\in\mathbb{N} edges is called a k -matching . For any matching whose vertices are positive integers, we say such matching is: • separated if every pair of its edges are separated, • nested if every pair of its edges are nested, • crossing if every pair of its edges are crossing, • non-separated if every pair of its edges are not separated, • non-nested if every pair of its edges are not nested, • non-crossing if every pair of its edges are not crossing. As a convention, we denote a separated (resp. nested and crossing) k -matching as \text{Sep-}\mathcal{M}_{k} (resp. \text{Nest-}\mathcal{M}_{k} and \text{Cross-}\mathcal{M}_{k} ). Similarly, we denote a non-separated (resp. non-nested and non-crossing) k -matching as \neg\text{Sep-}\mathcal{M}_{k} (resp. \neg\text{Nest-}\mathcal{M}_{k} and \neg\text{Cross-}\mathcal{M}_{k} ). Turán-type problems for these special matchings have been previously considered in the literature, although not systematically, for example under a different terminology or setting. The exact values of ex_{<}(n,\,\cdot\,) for separated, nested, crossing and non-crossing k -matchings have been determined for all values of k and n . See the next subsection for a formal presentation of these results. The main goal of this paper is to study the remaining two cases: non-separated and non-nested matchings. A summary of all exact results, or best bounds, can be found in Table 1 . This includes our new results for non-separated and non-nested matchings. k -matching Maximum number of edges in [n] without a k -matching References Separated |E(T(n+1,k))|-k+1 [ 7 ] Nested 2(k-1)n-(k-1)(2k-1) [ 7 ] Crossing 2(k-1)n-(k-1)(2k-1) [ 5 ] Non-Separated \frac{3}{2}(k-1)n-\frac{1}{2}(2k-1-\{n+1\}_{k})(k-1+\{n+1\}_{k}) New, see Theorem 2.1 Non-Nested \in[(k-1)n,(k-1)n+\binom{k-1}{2}] New, see Theorem 2.5 Non-crossing (k-1)n [ 13 ] Table 1: The values in the table hold for every n,k\in\mathbb{N} with n\geq 2k . Here T(n+1,k) denotes the k -partite Turán graph on n+1 vertices and \{n+1\}_{k} denotes the residue of n+1 divided by k . We also obtain sharp results for the Turán number of the alternating path (see Theorem 2.10 ) and for ex_{<}(n,\text{Cross-}\mathcal{M}_{k},\text{Sep-}\mathcal{M}_{k}) (i.e., when we forbid a crossing and a separated k -matching). Recently, there has been a lot of research on ordered Ramsey numbers [ 1 , 6 , 17 ] , where a monochromatic copy of a small ordered target graph is searched in a large 2-edge-coloured large host graph. We show that Turán-type results for alternating paths and non-nested matchings can yield better bounds for the analogous Ramsey-type problems. 1.1

Read the complete text