Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.15461 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918256651010048 |
|---|---|
| author | Barát, János Freschi, Andrea Tóth, Géza |
| author_facet | Barát, János Freschi, Andrea Tóth, Géza |
| contents | A {\it 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$-vertex ordered graph that does not contain a $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$-vertex ordered graph that does not contain a non-separated $k$-matching, which has the form $\frac{3}{2}(k-1)n+Θ(k^2)$.
For the non-nested case, we show the maximum number of edges lies between $(k-1)n$ and $(k-1)n+\binom{k-1}{2}$.
We also determine the exact maximum number of edges of an $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15461 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Matchings avoiding ordered patterns Barát, János Freschi, Andrea Tóth, Géza Combinatorics A {\it 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$-vertex ordered graph that does not contain a $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$-vertex ordered graph that does not contain a non-separated $k$-matching, which has the form $\frac{3}{2}(k-1)n+Θ(k^2)$. For the non-nested case, we show the maximum number of edges lies between $(k-1)n$ and $(k-1)n+\binom{k-1}{2}$. We also determine the exact maximum number of edges of an $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. |
| title | Matchings avoiding ordered patterns |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.15461 |