Ordered unavoidable sub-structures in matchings and random matchings Andrzej DudekaJaros law GrytczukbAndrzej Ruci nskic

2025-04-29 0 0 767.7KB 27 页 10玖币

侵权投诉

Ordered unavoidable sub-structures in matchings and

random matchings

Andrzej DudekaJaros law GrytczukbAndrzej Ruci´nskic

April 25, 2024

Abstract

An ordered matching of size nis a graph on a linearly ordered vertex set V,

|V|= 2n, consisting of npairwise disjoint edges. There are three diﬀerent ordered

matchings of size two on V={1,2,3,4}: an alignment {1,2},{3,4}, a nesting

{1,4},{2,3}, and a crossing {1,3},{2,4}. Accordingly, there are three basic homo-

geneous types of ordered matchings (with all pairs of edges arranged in the same

way) which we call, respectively, lines,stacks, and waves.

We prove an Erd˝os–Szekeres type result guaranteeing in every ordered matching

of size nthe presence of one of the three basic sub-structures of a given size. In

particular, one of them must be of size at least n1/3. We also investigate the size of

each of the three sub-structures in a random ordered matching. Additionally, the

former result is generalized to 3-uniform ordered matchings.

Another type of unavoidable patterns we study are twins, that is, pairs of order-

isomorphic, disjoint sub-matchings. By relating to a similar problem for permuta-

tions, we prove that the maximum size of twins that occur in every ordered matching

of size nis On2/3and Ω n3/5. We conjecture that the upper bound is the correct

order of magnitude and conﬁrm it for almost all matchings. In fact, our results for

twins are proved more generally for r-multiple twins, r⩾2. 1

Mathematics Subject Classiﬁcations: 05C80, 05C30, 05C70

1 Introduction

1.1 Background

A graph Gis said to be ordered if its vertex set is linearly ordered. Let Gand Hbe two

ordered graphs with vertex sets V(G) = {v1, . . . , vm}and V(H) = {w1, . . . , wm}, and the

aDepartment of Mathematics, Western Michigan University, Kalamazoo, MI, USA

(andrzej.dudek@wmich.edu).

bFaculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland

(j.grytczuk@mini.pw.edu.pl).

cDepartment of Discrete Mathematics, Adam Mickiewicz University, Pozna´n, Poland,

(rucinski@amu.edu.pl).

1An extended abstract of this paper appears in [11].

arXiv:2210.14042v5 [math.CO] 24 Apr 2024

respective linear orders v1<··· < vmand w1<··· < wm, for some integer m⩾1. We

say that Gand Hare order-isomorphic if for all 1 ⩽i < j ⩽m,vivj∈E(G) if and

only if wiwj∈E(H). Note that every pair of order-isomorphic graphs is isomorphic, but

not vice-versa. Also, if Gand Hare distinct graphs on the same linearly ordered vertex

set V, then Gand Hare never order-isomorphic, and so all 2(|V|

2)labeled graphs on V

are pairwise non-order-isomorphic. It shows that the notion of order-isomorphism makes

sense only for pairs of graphs on distinct vertex sets.

One context in which order-isomorphism makes quite a diﬀerence is that of subgraph

containment. If Gis an ordered graph, then any subgraph G′of Gcan be also treated as

an ordered graph with the ordering of V(G′) inherited from the ordering of V(G). Given

two ordered graphs, (a “large” one) Gand (a “small” one) H, we say that a subgraph

G′⊂Gis an ordered copy of Hin Gif G′and Hare order-isomorphic. We will sometimes

denote this fact by writing G′⪯G.

All kinds of questions concerning subgraphs in unordered graphs can be posed for

ordered graphs as well (see, e.g., [32] and [5]). For example, in [3] and [9] the authors

studied Tur´an and Ramsey type problems for ordered graphs. In particular, they showed

independently that there exists an ordered matching on nvertices for which the (ordered)

Ramsey number is super-polynomial in n, a sharp contrast with the linearity of the

Ramsey number for ordinary (i.e., unordered) matchings. This shows that it makes sense

to study even such seemingly simple structures as ordered matchings. In fact, Jel´ınek [22]

counted the number of matchings avoiding (i.e., not containing) a given small ordered

matching.

1.2 Topics and organization

In this paper we focus exclusively on ordered matchings, that is, ordered graphs which con-

sist of vertex-disjoint edges (and have no isolated vertices). For example, in Figure 1, we

depict two ordered matchings, M={{1,3},{2,4},{5,6}} and N={{1,5},{2,3},{4,6}}

on vertex set {1,2,3,4,5,6}with the natural linear ordering. Unlike in [22], we study

Figure 1: Exemplary matchings Mand N.

what sub-structures are unavoidable in ordered matchings. A frequent theme in both

ﬁelds, the theory of ordered graphs as well as enumerative combinatorics, are unavoidable

sub-structures, that is, patterns that appear in every member of a prescribed family of

structures. A ﬂagship example providing everlasting inspiration is the famous theorem of

Erd˝os and Szekeres [14] on monotone subsequences (see [4, 6, 7, 13, 15, 26, 31] for some

recent extensions and generalizations). In its diagonal form it states that any sequence

x1, x2, . . . , xnof distinct real numbers contains an increasing or decreasing subsequence

of length at least √n.

And, indeed, our ﬁrst goal is to prove its analog for ordered matchings. The reason why

the original Erd˝os–Szekeres Theorem lists only two types of subsequences is, obviously,

that for any two elements xiand xjwith i < j there are just two possible relations:

xi< xjor xi> xj. For matchings, however, for every two edges {x, y}and {u, w}with

x<y,u<w, and x<u, there are three possibilities: y < u ,w < y, or u<y<w

(see Figure 2). In other words, every two edges form either an alignment,a nesting, or a

crossing (the ﬁrst term introduced by Kasraoui and Zeng in [24], the last two terms coined

in by Stanley [29]). These three possibilities give rise, respectively, to three “unavoidable”

ordered sub-matchings (lines,stacks, and waves) which play an analogous role to the

monotone subsequences in the classical Erd˝os–Szekeres Theorem. (In [29], stacks and

waves consisting of kedges were called, respectively, k-nestings and k-crossings.)

Figure 2: An alignment, a nesting, and a crossing of a pair of edges.

Informally, lines, stacks, and waves are deﬁned by demanding that every pair of edges

in a sub-matching forms, respectively, an alignment, a nesting, or a crossing (see Figure 5).

In Subsection 2.1 we show, in particular, that every ordered matching of size ncontains

one of these structures of size at least n1/3. This special case was also proved by Huynh,

Joos and Wollan (see Lemma 25 in [21]). In the remainder of Section 2, we ﬁrst extend

this result to 3-uniform ordered matchings and then study the size of the largest lines,

stacks, and waves in random matchings.

Our second goal is to estimate the size of the largest (ordered) twins in ordered match-

ings. The problem of twins has been widely studied for other combinatorial structures,

including words, permutations, and graphs (see, e.g., [1, 25]). For an integer r⩾2, we

say that redge-disjoint (ordered) subgraphs G1, G2, . . . , Grof an (ordered) graph Gform

(ordered) twins in Gif they are pairwise (order-)isomorphic. The size of the (ordered)

twins is deﬁned as |E(G1)|=··· =|E(Gr)|. For ordinary matchings, the notion of r-

twins becomes trivial, as every matching of size ncontains twins of size ⌊n/r⌋– just split

the matching into ras equal as possible parts. But for ordered matchings the problem

becomes interesting. The above mentioned analog of the Erd˝os–Szekeres Theorem imme-

diately yields (again by splitting into requal parts) ordered r-twins of length ⌊n1/3/r⌋.

We provide much better estimates on the size of largest r-twins in ordered matchings

(Subsection 3.1) and random matchings (Subsection 3.2) which, not so surprisingly, are

of the same order of magnitude as those for r-twins in permutations (see [8, 10]).

1.3 Random matchings

As indicated above, we examine both questions, of unavoidable sub-matchings and of

twins, also for random matchings. A random (ordered) matching RMnis selected uni-

formly at random from all

αn:= (2n)!

n!2n

ordered matchings on vertex set [2n]. Among other results, we show that with probability

tending to 1, as n→ ∞, or asymptotically almost surely (a.a.s.), there are in RMnlines,

stacks, and waves of size, roughly, √n, as well as (ordered) twins of size Θ(n2/3).

There are two other ways of generating RMnwhich we are going to utilize in the

proofs. Besides the above deﬁned uniform scheme, we deﬁne the online scheme as follows.

For an arbitrary ordering of the vertices u1, . . . , u2none selects uniformly at random a

match, say uj1, for u1(in 2n−1 ways), then, after crossing out u1and uj1from the

list, one selects uniformly at random a match for the ﬁrst uncrossed vertex (in 2n−3

ways), and so on. Note that the total number of ways to select a matching this way

is (2n−1)(2n−3) ·. . . ·3·1 = (2n−1)!! which equals αn. A third equivalent way

to generate RMnis particularly convenient when one intends to apply concentration

inequalities available for random permutations. The permutation based scheme boils down

to just generating a random permutation Π := Πnof [2n] and “chopping it oﬀ” into a

matching {Π(1)Π(2),Π(3)Π(4),...,Π(2n−1)Π(2n)}. Note that this way each matching

corresponds, as it should, to exactly n!2npermutations. We will stick mostly to the

uniform scheme, applying the other two only occasionally.

1.4 Gauss codes

A convenient representation of ordered matchings can be obtained in terms of double

occurrence words over an n-letter alphabet, in which every letter occurs exactly twice

as the label of the ends of the corresponding edge in the matching. For instance, our

two exemplary matchings can be written as M=ABABCC and N=ABBCAC (see

Figure 3). In fact, this is a special case of an elementary combinatorial bijection between

ordered partitions of a set and permutations with repetitions. A minor nuisance here is

that ordered matchings correspond to unordered partitions, so every permutation of the

letters yields the same matching. Nevertheless, we will sometimes use this representation

to better illustrate some notions and ideas.

Interestingly, this type of words was introduced and studied already by Gauss [18] as

a way of encoding closed self-intersecting curves on the plane (with points of multiplicity

at most two). Indeed, denoting the self-crossing points by letters and traversing the curve

in a ﬁxed direction gives a (cyclic) word in which every letter occurs exactly twice (by

the multiplicity assumption) (see Figure 4). A general problem studied by Gauss was to

characterize those words that correspond to such curves. He found himself a necessary

condition, but a full solution (in terms of some quite involved constraints on an auxiliary

Figure 3: Exemplary matchings M=ABABCC and N=ABBCAC.

graph of crossing pairs) was obtained much later (see [28] for a brief history and further

references).

It is, perhaps, also worthwhile to mention that ordered matchings constitute a special

case of structures, known as Puttenham diagrams, that found an early application in the

theory of poetry (see [27, 33]). A basic idea is simple: a rhyme scheme of a poem can

be encoded by a word in which same letters correspond to rhyming verses. Of particular

interest here are planar rhyme schemes which are nothing else but ordered matchings

without crossings, or more generally, noncrossing partitions (see [30]).

Figure 4: A curve with Gauss code ABCCBDDA.

2 Unavoidable sub-matchings

Let us start with formal deﬁnitions. Let Mbe an ordered matching on the vertex set

[2n], with edges denoted as ei={ai, bi}so that ai< bi, for all i= 1,2, . . . , n, and

a1<··· < an. We say that an edge eiis to the left of ejand write ei< ejif ai< aj. That

is, in ordering the edges of a matching we ignore the positions of the right endpoints.

We now deﬁne the three basic types of ordered matchings:

•Line: a1< b1< a2< b2<··· < an< bn,

•Stack: a1< a2<··· < an< bn< bn−1<··· < b1,

•Wave: a1< a2<··· < an< b1< b2<··· < bn.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Orderedunavoidablesub-structuresinmatchingsandrandommatchingsAndrzejDudekaJaroslawGrytczukbAndrzejRuci´nskicApril25,2024AbstractAnorderedmatchingofsizenisagraphonalinearlyorderedvertexsetV,|V|=2n,consistingofnpairwisedisjointedges.TherearethreedifferentorderedmatchingsofsizetwoonV={1,2,3,4}:analignm...

展开>> 收起<<

Ordered unavoidable sub-structures in matchings and random matchings Andrzej DudekaJaros law GrytczukbAndrzej Ruci nskic.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Ordered unavoidable sub-structures in matchings and random matchings Andrzej DudekaJaros law GrytczukbAndrzej Ruci nskic

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: