## Saturation of edge-ordered graphs

Vladimir Bošković ∗

Balázs Keszegh †

August 2, 2024

## Abstract

For an edge-ordered graph G , we say that an n -vertex edge-ordered graph H is G -saturated if it is G -free and adding any new edge with any new label to H introduces a copy of G . The saturation function describes the minimum number of edges of a G -saturated graph. In particular, we study the order of magnitude of these functions. For (unordered) graphs, 0 1 -matrices, and vertex-ordered graphs it was possible to show that the saturation functions are either O (1) or Θ( n ) . We show that the saturation functions of edge-ordered graphs are also either O (1) or Ω( n ) . However, by finding edge-ordered graphs whose saturation functions are superlinear, we show that such a dichotomy result does not hold in general.

Additionally, we consider the semisaturation problem of edge-ordered graphs, a variant of the saturation problem where we do not require that H is G -free. We show a general upper bound O n ( log n ) and characterize edge-ordered graphs with bounded semisaturation function.

We also present various classes of graphs with bounded, linear and superlinear (semi)saturation functions. Along the way, we define a natural variant of the above problem, where the new edge must get the smallest label. The behaviour of the two variants shows many similarities, which motivated us to investigate the second variant extensively as well.

## 1 Introduction

An edge-ordered graph is a finite simple graph G with a linear order on its edge set E . We usually assign the edge-order using an injective labeling l : E → N , but it can equivalently be any other linear order, e.g., l : E → R . We say that an edge-ordered graph H contains an edge-ordered graph G , if G is isomorphic to a

Université Paris-Saclay, CNRS, CEA, Institut de Physique Théorique, 91191 Gif-sur-Yvette,

∗ France

Email address: vladimir.boskovic@ipht.fr

† HUN-REN Alfréd Rényi Institute of Mathematics and ELTE Eötvös Loránd University, Budapest, Hungary.

Email address: keszegh@renyi.hu

subgraph of H . Note that, an isomorphism between two edge-ordered graphs has to respect the edge-order. If H does not contain G , then we say that H avoids G .

A classical saturation problem of (not edge-ordered) graphs asks for the minimum number of edges in an n -vertex graph H such that it avoids G and adding any missing edge to H , a copy of G is created. In general, we always assume that n is a large enough integer, and we denote by sat n, G ( ) , the saturation number, the number of edges in such a graph H .

In the extremal problem of edge-ordered graphs [14] we are looking for the maximal size saturating host graph in the sense that no edge can be added with any label:

Definition 1. We are given an edge-ordered graph G . Let ex e ( n, G ) be the maximum number of edges in an edge-ordered graph H on n vertices that does not contain G as a subgraph (respecting the edge-order).

We extend the definition of saturation to edge-ordered graphs. However, when adding a non-edge, now there are several choices on how we can add it to the order of the edges of H . Unlike for vertex-ordered graphs that were studied in [6], this is not uniquely defined. Thus, we define three variants:

## Definition 2. We are given an edge-ordered graph G .

Let sat e ( n, G ) be the minimum number of edges in an edge-ordered graph H on n vertices in which adding any new edge with any new label (inserted anywhere in the linear order of edges) introduces a copy of G (that is, every label is forbidden; e stands for 'every' or 'edge-ordered').

Let sat m ( n, G ) be the minimum number of edges in an edge-ordered graph H on n vertices in which adding any new edge with a minimal label (inserted at the beginning of the linear order of edges) introduces a copy of G ( m stands for 'minimal').

Let sat s ( n, G ) be the minimum number of edges in an edge-ordered graph H on n vertices in which any new edge can be labeled by some single label (inserted somewhere in the linear order of edges) such that this introduces a copy of G ( s stands for 'some' or 'single').

In each case a (not necessarily minimal) H with the above saturation property is called a host graph and we say that H saturates G . 1

From the definition we see that if H is a saturation host graph for sat e , then H is a saturation host graph also for sat m . Similarly, if H is a host graph for sat m , then it is a host graph also for sat s . This implies the following inequalities:

## Remark 3. For every edge-ordered graph G , we have

$$s a t _ { s } ( n, G ) \leq s a t _ { m } ( n, G ) \leq s a t _ { e } ( n, G ) \leq e x _ { e } ( n, G ).$$

1 It will be always clear from the context which definition we are talking about.

Therefore, the most natural saturation function is sat e ( n, G ) , which we get from the extremal problem by searching for a minimal saturating host graph instead of a maximal one. 2 However, it turns out that in many ways instead of dealing with every possible label of the new edge, we get the same behavior already if we forbid the minimal and the maximal label. In fact, we get a lot of insight already by looking at the minimal label only, which is slightly more convenient to handle. Therefore, our center of attention is sat m through most of the paper. The consequences for sat e are discussed only afterwards, while we consider sat s only briefly compared to the other two functions.

We also consider a common variant of the saturation problem, when we do not assume that a graph H is G -free. Therefore, we only ask for a graph with minimum number of edges such that, by adding a new edge with every/minimal/some label, a new copy of G is created. This version is called semisaturation and the respective functions are denoted by ssat /ssat e m /ssat s . By definition, the following holds, which will be used throughout the paper.

Remark 4. For every edge-ordered graph G , we have

$$\ s s a t _ { e } ( n, G ) \leq s a t _ { e } ( n, G ), \ \ s s a t _ { m } ( n, G ) \leq s a t _ { m } ( n, G ), \ \ s s a t _ { s } ( n, G ) \leq s a t _ { s } ( n, G ).$$

## 1.1 History

Saturation problems were first studied by Erdős, Hajnal and Moon [10] in 1964 as an analogue of the extremal problem. In 1986 , Kászonyi and Tuza [15] characterized saturation functions for graphs by showing that a graph G has bounded saturation function if and only if G has an isolated edge, otherwise its saturation function is linear. Since then, saturation problems became an important topic in extremal combinatorics. For an updated survey, see [8]. Problems regarding saturation appear in the literature in many different variants and for diverse combinatorial objects. During the last few years, a significant progress was made in studying saturation of 0 1 -matrices, or equivalently vertex-ordered bipartite graphs. Brualdi and Cao [7] were first to investigate their saturation functions. Shortly after that, Fulek and Keszegh [11] managed to show that dichotomy holds for 0 1 -matrices too, identifying large families of matrices with linear saturation functions. On the other hand, Geneson [13] found an infinite family of matrices with bounded saturation function. Finally, Berendsohn [5] gave a complete characterization of permutation matrices with bounded saturation function.

Inspired by these interesting results about 0 1 -matrices, the authors [6] initiated the study of saturation problems on vertex-ordered graphs. They considered two different orders on vertex sets, linear and cyclic order. They proved dichotomy in both cases and they found infinite families of graphs that have bounded (respectively linear) saturation functions. However, even for perfect matching graphs (which are the natural counterparts of permutation matrices from the 0 1 -matrix setting), the complete characterization is still unknown.

2 This is why e refers to 'edge-ordered' alongside 'every'.

On the other hand, saturation problems for directed graphs were not yet studied systematically. Füredi et al. [12] showed in a different context that - → C 3 , a directed cycle of length three, has a superlinear semisaturation function. More precisely, ssat n, C ( - → 3 ) = n log n + O n ( log log n ) . This implies that the saturation function is also superlinear. In [8] they ask for a matching upper bound for sat n, C ( - → 3 ) . In fact leaving out the two special vertices from the construction of [12] shows that sat n, C ( - → 3 ) = n log n + O n ( log log n ) as well, answering this question. 3 This was observed by Alon and Fox [3].

Pikhurko [20] considered a saturation problem on the class of cycle-free directed graphs, i.e. adding any missing edge either introduces a cycle or a copy of a directed graph G , and showed that any family F of cycle-free directed graphs has sat n, ( F ) = O n ( ) with respect to this definition.

The study of extremal problems of edge-ordered graphs leads also to interesting problems. Their systematic study was started by Gerbner et al. [14]. They proved an Erdős-Stone-Simonovits type theorem which gives the exact asymptotic (a quadratic function) for the extremal function if the so-called order chromatic number of the forbidden graph is at least 3 . Thus, graphs with order chromatic number 2 are the most interesting to study further. They systematically took account of edge-ordered paths with 4 edges. This study was continued by Kucheriya and Tardos [18], [19]. They characterized connected edge-ordered graphs that have a linear extremal function and showed that for every other connected edge-ordered graph the extremal function is Ω( n log n ) , a dichotomy phenomenon similar to what happens for vertex-ordered graphs. They also showed that for edge-ordered forests of order chromatic number 2 the extremal function is n · 2 O ( √ log n ) . Note that if an edge-ordered graph contains a cycle then its extremal function is Ω( n c ) for some c &gt; 1 , which is implied by the corresponding unordered graph result.

The motivation to study extremal problems of vertex-ordered graphs came from combinatorial geometry where several natural problems can be described in such a way. It turns out that edge-ordered graphs have similar applications, as shown already in [14], and later in [1, 17].

Continuing this line of research, here we initiate the study of saturation problems of edge-ordered graphs.

## 1.2 Main results

For (unordered) graphs [15], 0 1 -matrices [11] and vertex-ordered graphs [6] it was shown that the saturation functions are either O (1) or Θ( n ) . Our main and somewhat surprising result is that there is no such dichotomy for edge-ordered

3 This construction saturating - → C 3 is the following. Let k be an appropriate even number. We take a bipartite graph with parts of size 2 k and at most ( 2 k k ) for an appropriate k , on the right side the vertices correspond to different sets of size k of the left side and then we orient an edge from w towards v E corresponding to some set E if and only if w ∈ E . It is easy to check that this graph avoids - → C 3 , as even without the ordering it does not contain a triangle. Also, adding any new edge with any orientation introduces a copy of - → C 3 .

graphs, similar to directed graphs. We first discuss sat m definition, then the remaining two.

The diamond graph is the graph we get by removing an edge from K 4 . We consider the diamond graph with different edge-orderings. We prove that for certain edge-orders, the saturation function is neither O (1) nor Θ( n ) . More specifically, we use a result by Katona and Szemerédi [16] about bipartite coverings to establish a lower bound Ω( n √ log n ) .

Furthermore, we generalize the lower bound obtained for diamond graphs to an infinite family of edge-ordered graphs. On the other hand, we prove that at least for one of these diamond graphs the saturation function is at most O ( n log n log log n ) . Additionally, we find an infinite family for which this upper bound holds. However, we do not know whether even a weaker non-trivial upper bound can be shown for arbitrary edge-ordered graphs.

We also find infinite families of graphs with bounded and linear saturation functions. Among others, if T is an edge-ordered tree, then sat m of e 0 + T is bounded, where e 0 + T denotes the graph we get from T by adding an isolated edge with minimal label. From now on e 0 (resp. e max ) always refers to the edge with minimal (resp. maximal) label and addition of graphs refers to their disjoint union.

Altogether, our examples show that the saturation functions can be bounded, linear and superlinear. In fact we show infinitely many examples for each case.

However, dichotomy holds in a weaker sense for sat m . We can show that if we assume that the minimal edge e 0 is isolated, then sat m is either bounded or linear (it is even possible but we could not prove it, that the latter case never happens). Otherwise, if the minimal edge is not isolated, then sat m is at least linear.

A summary of our saturation results for sat m definition is shown in Table 1. Next we concentrate on the semisaturation problem of edge-ordered graphs. As opposed to 0 1 -matrices [11] and vertex-ordered graphs [6] where it was relatively simple to fully characterize semisaturation functions, for edge-ordered graphs it appears to be more delicate. It turns out that the examples with superlinear saturation functions also have superlinear semisaturation functions. Our main result about the semisaturation functions is a general upper bound O n ( log n ) . We are also able to characterize the edge-ordered graphs with bounded ssat m , they are the ones with isolated e 0 . Further, we identify a large family of graphs with linear semisaturation functions. Altogether, for semisaturation functions we also show infinitely many examples for each case (bounded, linear, superlinear). A summary of our semisaturation results for ssat m definition is shown in Table 2.

We further study the other two definitions that we proposed: sat e and sat s . We show several results following the proofs for sat m definition. First of all, we show a weak dichotomy for sat e , then we characterize graphs with bounded semisaturation function ssat e . Moreover, we notice that the general semisaturation bound also holds for this definition. Later on, we find infinite families with bounded, linear and superlinear (semi)saturation function. We study the family of edge-ordered graphs F k = e 0 + G k + e max , where e 0 is the minimal edge and e max is the maximal

Table 1: Review of saturation results, for missing definitions see the references.

| Graph                                                                      | sat m                   | Reference    |
|----------------------------------------------------------------------------|-------------------------|--------------|
| e 0 + G                                                                    | O (1) or Θ( n )         | Theorem 5    |
| e 0 is not isolated                                                        | Ω( n )                  | Theorem 5    |
| G , N G [ a ] = N G [ b ] , G - e 0 is bipartite                           | O ( n log n )           | Theorem 8    |
| v, w ∈ N G ( a ) ∩ N G ( b ) , l ( av ) < l ( aw ) and l ( bv ) > l ( bw ) | Ω( n √ log n )          | Theorem 18   |
| D 0 , D 1 , D 2                                                            | Ω( n √ log n )          | Corollary 19 |
| D 0 + G , l ( D 0 ) < l ( G )                                              | O ( n log n log log n ) | Corollary 23 |
| D 3 , D 4 , D 5                                                            | Θ( n )                  | Claim 24     |
| C k , k ≥ 5                                                                | Θ( n )                  | Claim 28     |
| e 0 + K r , r ≥ 2                                                          | O (1)                   | Corollary 41 |
| e 0 + F , for monotone forest F                                            | O (1)                   | Corollary 46 |

Table 2: Review of semisaturation results.

| Graph                                                                      | ssat m                  | Reference    |
|----------------------------------------------------------------------------|-------------------------|--------------|
| e 0 + G                                                                    | O (1)                   | Claim 6      |
| e 0 not isolated                                                           | Ω( n )                  | Claim 6      |
| any G                                                                      | O ( n log n ) √         | Theorem 7    |
| v, w ∈ N G ( a ) ∩ N G ( b ) , l ( av ) < l ( aw ) and l ( bv ) > l ( bw ) | Ω( n log n )            | Theorem 18   |
| D 0 , D 1 , D 2                                                            | Ω( n √ log n )          | Corollary 19 |
| D 0 + G , l ( D 0 ) < l ( G )                                              | O ( n log n log log n ) | Corollary 23 |
| e 0 = ab , N G ( a ) ∩ N G ( b ) = ∅                                       | Θ( n )                  | Theorem 25   |
| triangle-free graphs, e 0 not isolated                                     | Θ( n )                  | Corollary 26 |

edge of F k , and the underlying graph of G k is a complete graph K k . It turns out that in this case, F k can have a superlinear sat e function for certain labelings of G k . This result shows how differently sat e and sat m functions behave, since for sat m we are able to show that sat m ( n, e 0 + G ) = O n ( ) for any edge-ordered graph G . We also show that cycles of odd length have linear saturation and semisaturation functions and any edge-ordered matching has bounded saturation function. The summary of the results about sat e and ssat e functions can be seen on Table 3.

Considering sat s , note that by definition most of the results about sat s are more general than for sat m , because any condition that is imposed on the minimal

edge e 0 can be replaced by an equivalent condition on an arbitrary edge in a given graph. Nevertheless, all our results about sat s follow as corollaries of some results about sat m functions.

Table 3: Results for sat e and ssat e definitions.

| e 0 and e max isolated                                                                            | sat e ( n, G ) = O (1) or Ω( n )                               | Theorem 9    |
|---------------------------------------------------------------------------------------------------|----------------------------------------------------------------|--------------|
| e 0 and e max isolated                                                                            | ssat e ( n, G ) = O (1)                                        | Theorem 10   |
| e 0 or e max not isolated                                                                         | ssat e ( n, G ) = Ω( n )                                       | Theorem 10   |
| any G                                                                                             | ssat e ( n, G ) = O ( n log n )                                | Corollary 11 |
| ab ∈ { e 0 , e max } , v, w ∈ N G ( a ) ∩ N G ( b ) ; l ( av ) < l ( aw ) and l ( bv ) > l ( bw ) | ssat e ( n, G ) = Ω( n √ log n )                               | Corollary 50 |
| D 0                                                                                               | sat e ( n, D 0 ) = O ( n log n log log n )                     | Theorem 51   |
| G k certain edge-ordering of K k , k ≥ 5                                                          | ssat e ( n, e 0 + G k + e max ) = Ω( n √ log n )               | Theorem 52   |
| C 2 k +1 , k ≥ 1                                                                                  | sat e ( n, C 2 k +1 ) = Θ( n ) ssat e ( n, C 2 k +1 ) = Θ( n ) | Corollary 54 |
| M k matching graph                                                                                | sat e ( n, M k ) = O (1)                                       | Corollary 55 |

## 2 Dichotomies and general upper bounds

## 2.1 sat m

In the vertex-ordered setting it was possible to show that the saturation function of any graph is either bounded or linear [6]. Such a dichotomy does not hold for edge-ordered graphs in general, as we will see later. However, we can still separate between bounded and at least linear saturation functions. In addition, if the minimal edge is isolated, then we do have a dichotomy. Note that the isolated edge case was the only interesting case for vertex-ordered graphs [6], as the remaining vertex-ordered graphs all have linear saturation function.

Theorem 5. Let G be an edge-ordered graph. If the minimal edge e 0 of G is isolated, then either sat m ( n, G ) = O (1) or sat m ( n, G ) = Θ( n ) . Otherwise, if e 0 is not isolated, then sat m ( n, G ) = Ω( n ) .

Proof. Assume first that e 0 is not isolated. There cannot be two isolated vertices in a saturating host graph H , otherwise by connecting them we will not introduce a new copy of G . Thus, sat m ( n, G ) ≥ n/ 2 -1 and the result follows.

Now, we assume that e 0 is isolated. To prove that sat m ( n, G ) = O n ( ) for any G it is enough to take H to be the union of G -e 0 and n -k +2 isolated vertices, where k is the number of vertices of G . If we add an edge between any two isolated vertices, a copy of G will be obtained. Next, we can create a saturating host graph H ′ by greedily adding edges to H (a common trick for other structures as well,

e.g., for vertex-ordered graphs), such that H ′ can have at most ( ) n 2 -( n -k +2 2 ) ≤ kn edges. This implies that sat m ( n, G ) = O n ( ) . On the other hand, if G has sublinear saturation number, then for every large enough n 0 there is a host graph H 0 on n 0 vertices that has two isolated vertices. Then it is easy to see that by adding isolated vertices to H 0 we still must have a saturating host graph. Therefore, we conclude that if the saturation number is not linear, then it has to be bounded.

It is actually possible that if e 0 is isolated, then sat m is always bounded. We can prove this in the case of semisaturation.

Claim 6. Let G be an edge-ordered graph. If the minimal edge e 0 of G is isolated, then ssat m ( n, G ) = O (1) , otherwise ssat m ( n, G ) = Ω( n ) .

Proof. Assume that e 0 is not isolated. If there are two isolated vertices in the host graph H , by connecting them we do not introduce a new copy of G . Thus, sat m ( n, G ) ≥ n/ 2 -1 . This is the same proof as in Theorem 5.

Assume now that e 0 is isolated. Take H to be a graph on n vertices that has two disjoint copies of G and all the remaining vertices isolated. Then we add edges between non-isolated vertices to get a host graph with a bounded number of edges.

We now proceed to prove a general semisaturation upper bound. We denote by N G ( a ) (resp. N G [ a ] ) the open (resp. closed) neighborhood of a in G .

Theorem 7. For every edge-ordered graph G , we have ssat m ( n, G ) = O n ( log n ) .

Proof. Let G be labeled with a function l : E G ( ) → { 0 1 , , ..., m } and denote by e 0 = ab its minimal edge. We define an additional labeling function for host graphs L : E H ( ) → N 3 , where N 3 is equipped with lexicographic order. We write x.y.z for ( x, y, z ) ∈ N 3 , and x.y for ( x, y, 0) . Let N G ( a ) \ b := { a , . . . , a 1 r } and N G ( b ) \ a := { b , . . . , b 1 s } . Let k = log ⌈ n ⌉ and n &lt; n ′ determined later. Consider k disjoint copies of the graph G ab = G \{ a, b } , which we denote by G ab i , for 1 ≤ i ≤ k . For every edge e ∈ E G ( ab ) , we label the corresponding edge e i ∈ E G ( ab i ) by:

$$L ( e _ { i } ) = l ( e ). i, \text{ for all } 1 \leq i \leq k.$$

Furthermore, we add n ′ isolated vertices V = { v , ..., v 1 n ′ } .

Take k bipartitions ( X , Y i i ) of V such that every pair of vertices is separated in one of them (this can easily be done as n ′ ≤ 2 k , e.g., the i th bipartition is according to i th digit in the binary form of the indices of the vertices).

Fix some i ≤ k . Then, take all the vertices a i,j in G ab i that correspond to the neighbors of a . We add an edge between v t ∈ X i and a i,j , where j ∈ { 1 , ..., r } . We label such edges with the following function:

$$L ( v _ { t } a _ { i, j } ) = l ( a a _ { j } ). i. t, \text{ for all } 1 \leq j \leq r.$$

Analogously, we do the same for the neighbors of b , but this time by connecting them with isolated vertices v t in Y i . We label them by:

$$L ( v _ { t } b _ { i, j } ) = l ( b b _ { j } ). i. t, \text{ for all } 1 \leq j \leq s.$$

This graph has O kn ( ) edges.

We can see that by adding an edge between a vertex x i ∈ X i and a vertex y i ∈ Y i , the graph induced by G ab i and these two vertices is isomorphic to G , where the edge x y i i plays the role of the minimal edge ab .

As every pair of vertices in V is separated in some bipartition, adding an edge between any two vertices in V creates a copy of G .

Set n ′ such that this graph has exactly n vertices. By greedily adding edges between vertices that are not in V , we obtain a host graph that semisaturates G and has O n ( log n ) edges.

While the upper bound O n ( log n ) could also be true for sat m , we can prove it only for a subclass of graphs.

Theorem 8. Let G be an edge-ordered graph such that G -e 0 is bipartite and N G [ a ] = N G [ b ] , where e 0 = ab is the minimal edge. Then sat m ( n, G ) = O n ( log n ) .

Proof. We construct the graph H the same way as in Theorem 7 and we show that H is G -free. First, observe that if N G [ a ] = N G [ b ] = { a, b } , then e 0 is an isolated edge and the result follows by Claim 5. Otherwise, there exists a vertex w that creates a triangle with a and b , which means that G is non-bipartite. We will show that H given in Theorem 7 is bipartite and it follows that H avoids G . Then we again greedily extend H to get a saturating host graph for G .

Let ( X,Y ) be a bipartition of G -e 0 (which exists by the assumption of the theorem), then notice that a and b should be in the same part, say X , while all of their neighbors N ab := N G ( a ) ∩ N G ( b ) have to be in Y . Since G -e 0 is bipartite, then G ab i is also bipartite for every 1 ≤ i ≤ k . We now can construct a bipartition ( X ,Y H H ) of H , and therefore prove the claim. We take a disjoint union of all G ab i , such that the corresponding neighbors N ab i of a and b are all in Y H . Then we add the set V as defined in the proof of Theorem 7, to the set X H and we connect all the vertices in V with all the vertices in ⋃ k i =1 N ab i , which gives a desired bipartition of H . So, we can conclude that H is indeed G -free.

## 2.2 sat e

We are only able to prove a weak dichotomy for sat e . We denote by e 0 the minimal edge and by e max the maximal edge of G .

Theorem 9. Let G be an edge-ordered graph. If e 0 and e max are isolated, then either sat e ( n, G ) = O (1) or sat e ( n, G ) = Ω( n ) . Otherwise, sat e ( n, G ) = Ω( n ) .

Proof. We follow the same ideas as in the proof of Theorem 5. First we consider the case when either e 0 or e max is not isolated. Assume wlog. e 0 is not isolated, then if we label one missing edge with a minimal label between two isolated vertices of H , no copy of G is created. Therefore, H does not have two isolated vertices and we get sat e ( n, G ) ≥ n/ 2 -1 .

Let e 0 and e max be isolated, and assume that G has a sublinear saturation function. Then for a large enough n , the host graph must have at least two isolated vertices. Since they can be replaced by arbitrary many isolated vertices, without affecting saturation property, we conclude that if the saturation function is sublinear, then it has to be bounded.

Notice that in the e 0 and e max isolated case when sat e is unbounded, unlike in Theorem 5 where we proved Θ( n ) , here we only have Ω( n ) . The reason for this is detailed later.

Similarly to Claim 6, for semisaturation we can prove a stronger statement.

Theorem 10. Let G be an edge-ordered graph. If e 0 and e max are isolated, then ssat e ( n, G ) = O (1) , otherwise ssat e ( n, G ) = Ω( n ) .

Proof. Let H be a host graph on n vertices and m edges, such that H = e 1 + G 1 + G 2 + G 3 + G 4 + e m + V where G i are copies of G - { e , e 0 max } so that l ( e 1 ) &lt; l G ( 1 ) &lt; l G ( 2 ) &lt; l G ( 3 ) &lt; l G ( 4 ) &lt; l e ( m ) and V , the set of the remaining vertices of H , is a set of isolated vertices. Let e ′ = uv be an edge that we can add to H with u ∈ V isolated. We distinguish two cases:

- 1. l ( e ′ ) &gt; l G ( 2 ) . If v ∈ V ( G 2 + G 3 + G 4 + e m ) , then e 1 + G 1 + e ′ is a copy of G . Otherwise, e ′′ + G 2 + e ′ where e ′′ ∈ E e ( 1 + G 1 ) . If G 1 has no edges, then e ′ + G 2 + e m is a copy of G .
- 2. l ( e ′ ) &lt; l G ( 3 ) . Similarly, if v ∈ V ( e 1 + G 1 + G 2 + G 3 ) , then e ′ + G 4 + e m is a copy of G . Otherwise, e ′ + G 3 + e ′′ where e ′′ ∈ E G ( 4 + e m ) . If G 4 has no edges, then e 1 + G 3 + e ′ is a copy of G .

Thus, adding greedily edges to H that are not in V , we get a host graph that semisaturates G with O (1) edges.

Otherwise, if for example e 0 is not isolated, then by adding any new edge with minimal label between two vertices in V we do not create a copy of G . Therefore, the semisaturation function is at least linear.

We are also able to show the general upper bound for semisaturation. Let G rev be the edge-ordered graph obtained from G such that the underlying graph remains the same, but the linear order of its edges is reversed. By Theorem 7 we get that sat m ( n, G ) = O n ( log n ) and sat m ( n, G rev ) = O n ( log n ) . By gluing the host graphs H and H rev on the same independent set V such that l ( H rev ) &lt; l H ( ) , we get a new host graph which semisaturates G in sat e sense for any missing edge in V .

Corollary 11. For every edge-ordered graph G , we have ssat e ( n, G ) = O n ( log n ) .

Unlike for sat m definition, we do not know whether it is possible to show this upper bound for saturation function of some family similar to the one described in Theorem 8.

## 2.3 sat s

Recall that sat s ( n, G ) ≤ sat m ( n, G ) for every edge-ordered graph G . So, all the results about upper bounds can be applied to sat s definition. In this subsection, we list the main corollaries. The first result is the analogue of Theorem 5.

Corollary 12. Let G be an edge-ordered graph. If G contains an isolated edge, then either sat s ( n, G ) = O (1) or sat s ( n, G ) = Θ( n ) . Otherwise, sat s ( n, G ) = Ω( n ) .

We continue with the weak dichotomy of semisaturation functions. The proof is completely analogous to the proof of Claim 6.

Corollary 13. Let G be an edge-ordered graph. If G contains an isolated edge, then ssat s ( n, G ) = O (1) , otherwise ssat s ( n, G ) = Ω( n ) .

The general upper bound for semisaturation follows directly from Theorem 7.

Corollary 14. For every edge-ordered graph G , we have ssat s ( n, G ) = O n ( log n ) .

We conclude by defining a family of graphs for which this upper holds for the sat s function.

Corollary 15. Let G be an edge-ordered graph. If there exists an edge ab ∈ E G ( ) such that G -ab is bipartite and N G [ a ] = N G [ b ] . Then sat s ( n, G ) = O n ( log n ) .

Note that these results are more general than for sat m definition, which comes from the fact that we can usually replace the assumptions about the minimal edge e 0 to any edge in G . In Section 5, we will get back to this definition and explain several other results.

## 3 Unbounded saturation functions

In this section we deal only with sat m and ssat m , the other variations are discussed in later sections.

## 3.1 Bipartite coverings

We will need an auxiliary result about bipartite coverings of almost complete graphs.

A bipartite covering of a graph G is a collection of bipartite graphs, so that each edge of G belongs to at least one of them. The capacity of the covering is the sum of the numbers of vertices of these bipartite graphs. We need a lower bound on the capacity of a bipartite covering of almost complete graphs.

Theorem 16. [16] Let G be a graph on n vertices and let d , d 1 2 , ..., d n denote the degrees of its vertices. Then the capacity of any bipartite covering of G is at least

$$\sum _ { i = 1 } ^ { n } ( \log n - \log ( n - d _ { i } ) ).$$

This was shown by Katona and Szemerédi [16], see also the paper of Alon [2] for a generalization which also has a similar and short proof. See also the exact result of Dong and Liu [9] that in a bipartite covering of the complete graph K n there is a vertex which has incident edges from at least log n of the bipartite graphs.

Corollary 17. Let G be a graph with at most cn 2 -ϵ missing edges for some constants c, ϵ &gt; 0 and let B be a bipartite covering of G , then there is a vertex which has incident edges from c ′ log n of the bipartite graphs in B , where c ′ depends only on c and ϵ .

Proof. Let x = 2 cn 1 -ϵ . We delete at most n/ 2 vertices from G that have co-degree at least x , and denote by G ′ the obtained graph. Then G ′ has n ′ ≥ n/ 2 vertices and their co-degrees are less than x and so their degrees are more than n ′ -x -1 .

By Theorem 16, the capacity of B restricted to G ′ is at least

$$\sum _ { i = 1 } ^ { n ^ { \prime } } ( \log n ^ { \prime } - \log ( n ^ { \prime } - d _ { i } ) ) > \frac { n } { 2 } ( \log n ^ { \prime } - \log ( x + 1 ) ) = \frac { n } { 2 } ( \epsilon \log n - O ( 1 ) ),$$

where the O notation hides dependence on c and ϵ . Therefore, one of the vertices must be in at least c ′ log n bipartite graphs for some constant c ′ .

## 3.2 Superlinear saturation functions

Later we will see examples of graphs with bounded saturation function. Next we show a family of graphs that have superlinear saturation and semisaturation functions, showing that there is no dichotomy. Notice that, by Theorem 19 dichotomy does not hold neither for saturation nor for semisaturation. This most likely suggests that studying semisaturation of edge-ordered graphs might be more demanding than it was for vertex ordered graphs [6], where it was possible to fully characterize semisaturation functions.

Theorem 18. Let G be an edge-ordered graph such that its minimal edge is ab . If there exist two vertices v, w ∈ N G ( a ) ∩ N G ( b ) such that l ( av ) &lt; l aw ( ) and l ( bv ) &gt; l bw ( ) , then sat m ( n, G ) ≥ ssat m ( n, G ) = Ω( n √ log n ) .

Proof. Let H be a saturation host graph on n vertices. For a pair of vertices that do not span an edge of H , denoted by f , adding an edge at f with minimal label we should get a copy of G . Thus there exists a pair of vertices e = π f ( ) such that the four vertices f ∪ e span a copy of the structure on four vertices and five edges which is required by our assumption in which f plays the role of ab . Note that the order of labels of the two edges going from the two vertices of f to the two vertices of e is reversed. Thus, for every pair of vertices e there is a bipartition of the vertices such that every non-edge in the set π -1 ( e ) goes between the two parts of this bipartition. √

Assume on the contrary that H has less than cn log n edges for some c ≤ 1 chosen later. The non-edges of H must be covered by the sets of non-edges π -1 ( e )

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-b8c6d760-2d70-44cf-83e5-3d851c3fcad1.jpg)

w

w

w

Figure 1: Six edge-ordered diamond graphs whose minimal edge is ab .

where e is a pair of vertices in H . As each π -1 ( e ) is bipartite, we can apply Corollary 17 on the complement of H . First we choose constants c , ϵ 0 0 independently from c such that n √ log n ≤ c 0 ( n/ 2) 2 -ϵ 0 holds. Now we can apply Corollary 17 with c , ϵ 0 0 . We get that there is a vertex v in H which participates in at least c ′ log n many bipartitions that cover the non-edges of H . For each e such that π -1 ( e ) contains a non-edge that covers v , there is an edge in H from v to both vertices of e . Thus v is connected to at least c ′ log n different such pairs of vertices, therefore, to at least √ c ′ log n vertices in H . Delete v from H . Repeat this procedure n/ 2 times, in each step we can apply Corollary 17 with the same c 0 and ϵ 0 to find and delete a vertex with degree at least √ c ′ log( n/ 2) . Altogether, we have found at least n 2 √ c ′ log n edges in H . When c is small enough this contradicts our assumption that H has less than cn √ log n edges, .

Corollary 19. Let D , D , D 0 1 2 be the graphs shown in Figure 1. Then ssat m ( n, D i ) = Ω( n √ log n ) , for i ∈ { 0 1 2 , , } .

We would like now to understand better which edge-ordered graphs are not covered by Theorem 18. We will discuss later the graphs where the endvertices of the minimal edge have disjoint neighborhoods. For now, we assume that N G ( a ) ∩ N G ( b ) is non-empty.

Remark 20. Let { u , u 1 2 , ..., u k } := N G ( a ) ∩ N G ( b ) , for k ≥ 1 . We can assume wlog. that l ( au 1 ) &lt; ... &lt; l au ( k ) . If l ( bu 1 ) &lt; ... &lt; l bu ( k ) does not hold, then there exist 1 ≤ i &lt; j ≤ k such that l ( au i ) &lt; l au ( j ) and l ( bu i ) &gt; l bu ( j ) , which by Theorem 18 implies that G has a superlinear saturation function.

We now proceed by establishing an upper bound for D 0 which is close to its lower bound.

$$L = \begin{matrix} i _ { 2 } \begin{bmatrix} j _ { 1 } \\ 1 & 2 & 7 & 8 \\ 3 & 4 & 5 & 6 \end{bmatrix}$$

Figure 2: A matrix L that satisfies the sat property for columns 1 and 3 , its graph H which saturates D 0 for the corresponding non-edge.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-165e1e4a-13f8-409c-9615-305657ca36cf.jpg)

## Theorem 21.

$$\ s s a t _ { m } ( n, D _ { 0 } ) \leq s a t _ { m } ( n, D _ { 0 } ) = O \left ( n \frac { \log n } { \log \log n } \right ).$$

Proof. We show the upper bound by constructing a certain labeling of the complete bipartite graph H = K k,n (for appropriate small k ) which will be a host graph for D 0 . Since D 0 is non-bipartite, it follows that H is D 0 -free regardless of its labels. We will label the edges of H such that it saturates D 0 for the non-edges within the ¯ K n part, at the end we just greedily extend this graph with edges put within the ¯ K k part to get a host graph for D 0 . This time, we assume that the labeling function takes values in R + .

An alternative way to look at this problem is to describe the labeling in terms of the biadjacency matrix of H that we denote by L = ( ℓ i,j ) 1 ≤ ≤ i k, 1 ≤ ≤ j n with entries from R + . We say that a matrix L satisfies the sat property if the following holds: for every two column indices 1 ≤ j , j 1 2 ≤ n , there exist two row indices 1 ≤ i 1 , i 2 ≤ k such that we have ℓ i 2 ,j 1 &lt; ℓ i 1 ,j 1 &lt; ℓ i 1 ,j 2 &lt; ℓ i 2 ,j 2 . It is easy to see that if we label the edges of H according to an L that satisfies the sat property, then we get a host graph that saturates D 0 for the non-edges within the ¯ K n part of H (the sat property is enough but not necessary for that). Notice that L has the sat property if and only if for every pair of columns the subgraph defined by these two columns has the sat property. See Figure 2 for an illustration.

First, let us assume that n = k ! for some k ∈ N and show that the matrix L of size k × n which will be determined below satisfies the sat property. We partition the elements of the matrix L into blocks ( B i,j ) 1 ≤ ≤ i k, 1 ≤ ≤ j i ! such that the i th row is equipartitioned into i ! blocks:

$$B _ { i, j } = \{ \ell _ { i, \frac { ( j - 1 ) n } { i! } + 1 }, \dots, \ell _ { i, \frac { j n } { i! } } \}.$$

Considering how the blocks in each row partition the columns, we can observe this partition for any given row is a refinement compared to the row above, that is, for each block B in the ( i -1) th row there are exactly i blocks in the i th row such that their columns equipartition the columns of B . See Figure 3 for an example.

The labeling will be such that within any block the labels are in increasing order, that is, ℓ i,j 1 &lt; ℓ i,j 2 for any two entries in the same block whenever j 1 &lt; j 2 .

Figure 3: A matrix L and its blocks for the case n = 6 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-552968a8-d4a6-4d70-bb8c-5a6c16ae7822.jpg)

Additionally, for any two blocks their labels can be separated, that is, for any two blocks B i 1 ,j 1 , B i 2 ,j 2 all the elements of B i 1 ,j 1 are smaller (or larger) than all the elements of B i 2 ,j 2 . We denote this by B i 1 ,j 1 &lt; B i 2 ,j 2 (or B i 1 ,j 1 &gt; B i 2 ,j 2 ).

The labeling is defined row by row. First, we label the entries in B 1 1 , , the first row of the matrix, with any n different positive real numbers in increasing order. Then we proceed to the second row, by labeling B 2 1 , and B 2 2 , such that B 2 1 , &lt; B 1 1 , &lt; B 2 2 , . Note that, if we take any two columns j 1 and j 2 such that j 1 ≤ n 2 &lt; j 2 , then these two columns and the first two rows of the matrix L define a submatrix that has the sat property. We continue with the third row by labeling the blocks such that

$$B _ { 3, 1 } < B _ { 2, 1 } < B _ { 3, 2 } < B _ { 1, 1 } < B _ { 3, 3 } \text{ and } B _ { 3, 4 } < B _ { 1, 1 } < B _ { 3, 5 } < B _ { 2, 2 } < B _ { 3, 6 }.$$

See again Figure 3, for an example when n = 6 and observe that it satisfies the sat property.

In a general step, if we assume that i -1 rows are labeled for i ≥ 2 , then we label the i th row as follows. We take any j such that 1 ≤ j ≤ ( i -1)! and we want to label all the blocks in row i that share a column with B i -1 ,j . These are exactly the blocks B i, ( j -1) +1 i , . . . , B i,ji and we label them such that

$$B _ { i, ( j - 1 ) i + 1 } < A _ { 1 } < B _ { i, ( j - 1 ) i + 2 } < \dots < A _ { i - 1 } < B _ { i, j i },$$

where { A , . . . , A 1 i -1 } are the blocks that share a column with B i -1 ,j (including B i -1 ,j ), (as there is exactly one such block in each row). Additionally, these are indexed in an increasing order, i.e., A &lt; 1 · · · &lt; A i -1 . In the example above, if we want to label the block B 3 2 , , then A 1 := B 2 1 , , A 2 := B 1 1 , .

Next we prove by induction on i that if we take any two columns j 1 and j 2 that correspond to different blocks in the i th row, then these two columns and the first i rows of the matrix L define a submatrix that has the sat property. This holds for i = 2 . Suppose i &gt; 2 and the two columns correspond to different blocks of the row i -1 , then this holds by induction. Finally, if i &gt; 2 and the two columns were separated first in the i th column, say they are in blocks B 1 and B 2 , where B 1 comes first (has smaller column indices). By the definition of labeling, we have B &lt; B 1 2 . Also, in each earlier row there is a block that contains both columns and there is one such block A in some row i ′ for which B &lt; A &lt; B 1 2 . As within A the

entries are in the increasing order, the four entries in these two columns and in rows i, i ′ show that the submatrix indeed has the sat property.

When we reach the last row, we get that the blocks are all singletons and we stop. As each column is separated in this last row, by the inductional claim each pair of columns define a submatrix with the sat property and thus the whole matrix L also has the sat property, as required.

To describe k in terms of n we can use Stirling's formula to obtain k log k = Θ(log n ) , which is equivalent to

$$\frac { c _ { 1 } \log n } { \log k } \leq k \leq \frac { c _ { 2 } \log n } { \log k },$$

for some positive constants c 1 and c 2 . From the first inequality we can get that c 1 log n ≤ k log k ≤ k 2 which is equivalent to √ c 1 log n ≤ k . If we plug this into the second inequality we get

$$k \leq \frac { c _ { 2 } \log n } { \log \sqrt { c _ { 1 } \log n } } = O \left ( \frac { \log n } { \log \log n } \right ).$$

Thus we get a labeling of H from the matrix L . Finally, we greedily keep adding edges with minimal labels to H within the K k part until the graph saturates D 0 . As the number of edges in H is at most kn + ( ) k 2 , the theorem follows.

We now handle the case when there is no k ∈ N such that n = k ! . In this case set k to be the smallest number with n &lt; k ! and determine the k × n matrix L the same way except that when defining the blocks in the i th row, instead of equipartitioning the columns of each block in the ( i -1) th row, we now partition them to i almost equal size blocks (i.e., the difference of their sizes is at most one). Note that since ( k -1)! &lt; n , then in ( k -1) th row, each block is of size at least one. Only in the last row we may have blocks of size zero, but this does not change asymptotically the result and it is straightforward to check that the same proof works.

Even though the bounds are not far, determining the exact order of magnitude of sat m ( n, D 0 ) is left open. We can generalize this upper bound for further graphs. In order to state this result, we introduce the following notation: for two edgeordered graphs (usually disjoint subgraphs of some graph) we write l ( F 1 ) &lt; l F ( 2 ) if all the labels of F 1 are smaller than all the labels of F 2 .

Lemma 22. Let F 1 and F 2 be two edge-ordered graphs such that sat m ( n, F 1 ) = O f n ( ( )) , where f ( n ) = Ω( n ) and l ( F 1 ) &lt; l F ( 2 ) . Then sat m ( n, F 1 + F 2 ) = O f n ( ( )) .

Proof. Let H F ( 1 ) be the host graph for F 1 , and assume F 2 has k vertices. Then we take a union H F ( 1 ) + F ∗ 2 , where F ∗ 2 is a relabeled copy of F 2 such that l ( H F ( 1 )) &lt; l ( F ∗ 2 ) . We argue that this construction indeed avoids F 1 + F 2 . Assume there is a copy of F 1 in H F ( 1 ) + F ∗ 2 , clearly it cannot be found in the part H F ( 1 ) , so it has to have at least one edge in F ∗ 2 . In that case F 2 has to be found in the rest of F ∗ 2 , which is not possible because of its size.

Notice that by adding any edge within H F ( 1 ) we get a copy of F 1 + F 2 , and we can greedily add any other edge if it does not create a copy of F 1 + F 2 , which only adds at most kn + k 2 edges. Since f ( n ) is at least linear, we get that sat m ( n, F 1 + F 2 ) = O f n ( ( )) .

Using this result, we can generalize the upper bound obtained for D 0 to an infinite family of edge-ordered graphs.

Corollary 23. Let G be an edge-ordered graph, such that l ( D 0 ) &lt; l G ( ) . Then

$$\ s s a t _ { m } ( n, D _ { 0 } + G ) \leq s a t _ { m } ( n, D _ { 0 } + G ) = O \left ( n \frac { \log n } { \log \log n } \right ).$$

## 3.3 Linear saturation functions

We discuss now the remaining three graphs that have the diamond graph as their underlying graph.

Claim 24. For i ∈ { 3 4 5 , , } we have sat m ( n, D i ) = Θ( n ) , where D i are the graphs as shown in Figure 1.

Proof. By Theorem 5, it is enough to show that sat m ( n, D i ) = O n ( ) for all i ∈ { 3 4 5 , , } . Take H to be a host graph on n vertices such that its underlying graph is a complete bipartite graph K 2 ,n -2 . Denote the vertices of H by u , u 1 2 on one side and v , ..., v 1 n -2 on the other side. With a proper edge-ordering we will be able to define for each D i a saturating graph H i that has linearly many edges, from where the conclusion will follow. Notice also that since in all the cases the underlying graph of H i is bipartite, and D i is not, we can easily conclude that H i is D i -free. Therefore, we will only need to check that H i actually saturates D i .

We start with D 3 , the following labeling of H gives H 3 :

$$l ( u _ { 1 } v _ { i } ) = 2 i - 1 \text{ and } l ( u _ { 2 } v _ { i } ) = 2 i, \text{ for all } i \in \{ 1, 2, \dots, n - 2 \}.$$

To check that H 3 saturates D 3 , connect an edge v v i j for any 1 ≤ i &lt; j ≤ n -2 and label it with zero. Then, notice that the graph induced by four vertices u , u 1 2 , v , v i j is isomorphic to D 3 . We can add the edge u u 1 2 for example with the largest label, this does not affect the linearity of sat m ( n, D 3 ) .

We continue with the case D 4 , the following labeling of H gives H 4 :

$$l ( u _ { 1 } v _ { i } ) = i \text{ and } l ( u _ { 2 } v _ { i } ) = n - 2 + i, \text{ for all } i \in \{ 1, 2, \dots, n - 2 \}.$$

Again, as in the previous case H 4 saturates D 4 , as after adding an edge between v i and v j labeled with zero, the graph induced by these two vertices and u 1 and u 2 is isomorphic to D 4 . We can add the edge u u 1 2 with the largest label, this does not affect the linearity of sat m ( n, D 4 ) . Thus, we are done.

Finally, we treat the case D 5 , the following labeling of H gives H 5 :

$$l ( u _ { 1 } v _ { i } ) = i \text{ and } l ( u _ { 2 } v _ { i } ) = 2 n - 3 - i, \text{ for all } i \in \{ 1, 2, \dots, n - 2 \}.$$

This can be checked analogously to the previous two cases.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-f705854d-7ef2-460a-be6f-fa51aed9ea5d.jpg)

Theorem 25. Let G be an edge-ordered graph and let ab be the minimal edge in G such that deg a ( ) ≥ 2 . If N G ( a ) ∩ N G ( b ) = ∅ , then ssat m ( n, G ) = Θ( n ) .

Proof. The lower bound follows from Claim 6. For the upper bound let N G ( a ) \ { } b = { u , u 1 2 , ..., u s } and N G ( b ) \ { a } = { v , v 1 2 , ..., v t } , and assume that G has r vertices. Furthermore, let H ′ be the graph obtained by taking the union of G \{ a, b } and ¯ K n -r +2 (the complement of the complete graph, that is, an independent set), whose set of vertices we denote by { w , w , ..., w 1 2 n -r +2 } . Then, the host graph H on n vertices is obtained by adding edges u w i k and v w j k to H ′ , for i ∈ [ s ] , j ∈ [ t ] , and k ∈ [ n -r +2] . We label them as follows: L u w ( i k ) = l ( u a .k i ) , and L v w ( j k ) = l ( v b .k j ) , while all the remaining edges keep the same labels as in G .

Notice that H semisaturates G for the edges inside ¯ K n -r +2 . Indeed, if we add any edge of the form w w i j for i, j ∈ [ n -r +2] , it will have a role of the minimal edge ab in the new copy of G .

We can greedily add a linear number of edges incident to the part G \ { u, v } to get a semisaturating host graph.

A natural family that satisfies these conditions is the family of triangle-free graphs (such that e 0 is not isolated).

Corollary 26. Let G be a triangle-free edge-ordered graph, whose minimal edge is not isolated. Then ssat m ( n, G ) = Θ( n ) .

Corollary 27. Let G be a non-bipartite edge-ordered graph. Let e 0 = ab ∈ E G ( ) be the minimal edge and assume that G -e 0 is bipartite and N G ( a ) ∩ N G ( b ) = ∅ , then sat m ( n, G ) = Θ( n ) .

Proof. We use the same construction as in Theorem 25. To verify that the host graph is G -free, notice that we obtain the host graph by taking the bipartite graph G -ab and replacing the vertices a and b by arbitrary many vertices which are connected to N G ( a ) ∪ N G ( b ) . This means that the host graph H remains bipartite and consequently it cannot contain a copy of non-bipartite graph G .

From this statement, we get that the cycles of odd degree have linear saturation function. We discuss now even cycles, as well as certain families of paths.

Claim 28. Let C k be any edge-ordered cycle graph on k ≥ 5 vertices. Then sat m ( n, C k ) = Θ( n ) .

Proof. Let H be the host graph obtained from the construction described in Theorem 25 and let V = { v , ..., v 1 n -k +2 } be the independent set in it. Let u u 1 2 be the minimal edge in C k , and let u 0 (resp. u 3 ) be the other neighbor of u 1 (resp. u 2 ). Assume there is a copy of C k in H , then clearly there should be at least two vertices from V in such a cycle, v i and v j . Note that both of these vertices have degree two, so both of their incident edges have to be in the copy of C k . However, they are both connected to the vertices u 0 and u 3 . Therefore, we get that v , v i j , u 0 , u 3 form a 4 -cycle, but since we assumed that k ≥ 5 , we get a contradiction.

̸

Claim 29. Let P k be a path on the vertex set { u , u 1 2 , ..., u k } for k ≥ 4 , such that l ( u u 2 3 ) = 0 and l ( u k -2 u k -1 ) = 0 , where 0 is the minimal edge-label. Then sat m ( n, P k ) = Θ( n ) .

̸

Proof. Following the same procedure as in Theorem 25, we only need to show that the host graph is P k -free. We will show that its underlying graph does not have any path on k vertices, regardless of its labels.

Consider first the case when k ≥ 6 and l ( u u i i +1 ) = 0 , for some i ∈ { 3 , ..., k - } 3 . Then after we delete the vertices u i and u i +1 , we get two paths u u ...u 1 2 i -1 and u i +2 u i +3 ...u k . Then we connect u i -1 and u i +2 with all the vertices in the set V = { v , ..., v 1 n -k +2 } and we obtain the host graph H .

Assume on the contrary, that there is a copy of P k in H . Then there must be at least two vertices from V in such a copy. Moreover, these two vertices must be connected either through u i -1 or u i +2 . Suppose wlog. it is u i +2 , but then none of the vertices u j , j &gt; i +2 can be in the copy of the path P k . However, this means that our path can have at most i +2 vertices, which is not enough since we assumed that i ≤ k -3 . Contradiction.

It remains to check the case when l ( u u 1 2 ) = 0 (or by symmetry l ( u k -1 u k ) = 0 ). We can see that again two vertices from the independent set V are necessary, and they are connected through u 3 . But this only gives a copy of P 3 , while we assumed that k ≥ 4 . So, we get a contradiction again.

Using a very similar construction to the one in Claim 24 that was used to prove the linearity of the saturation function of D 4 , we are able to generalize this result in terms of the semisaturation function.

Claim 30. Let G be an edge-ordered graph with labels l : E G ( ) → N and let ab be the minimal edge in G , such that for all w ∈ N G ( a ) ∩ N G ( b ) we have l ( aw ) = l ( bw ) + 1 . Then, ssat m ( n, G ) = Θ( n ) .

Proof. Assume that G has k +2 vertices for some k ∈ N . Then we create H starting with a copy of G \{ u, v } keeping the same labels and n -k isolated vertices denoted by v , ..., v 1 n -k . Then we add an edge between v i and w for all 1 ≤ i ≤ n -k and w ∈ N G ( a ) ∪ N G ( b ) and label them with

$$L ( v _ { i } w ) = \begin{cases} l ( a w ). i, & \text{if $w \in N_{G}(a)$} \\ l ( b w ). i, & \text{if $w \in N_{G}(b) \, \bigwedge N_{G}(a)$}. \end{cases}$$

As usual, it is simple to check that H semisaturates G for the edges inside ¯ K n -k and then we can greedily add at most a linear number of edges to get a semisaturating host graph.

Claim 30 served as a warm-up to the following more general statement, for which first we need to introduce some notations.

Definition 31. Let l ( E ′ ) = { l ( e ): e ∈ E ′ } , where E ′ ⊆ E G ( ) . We say that l ( E ′ ) forms an interval in l ( G ) if there is no other edge e ∈ E G ( ) such that l ( e 1 ) &lt; l ( e ) &lt; l e ( 2 ) , for some e , e 1 2 ∈ E ′ .

We write l ( E ′ ) &lt; l E ( ′′ ) , if l ( e ′ ) &lt; l e ( ′′ ) for all e ′ ∈ E ′ and e ′′ ∈ E ′′ . In Remark 20, we discussed the labeling of graphs for which Theorem 18 cannot be applied. In the following, we treat a special case of this family.

Theorem 32. Let G be an edge-ordered graph with labels l : E G ( ) → N and e 0 = ab its minimal edge. We denote by { u , u 1 2 , ..., u k } := N G ( a ) ∩ N G ( b ) and we write l ( au i ) = a i and l ( bu i ) = b i for all 1 ≤ i ≤ k . We assume that a 1 &lt; a 2 &lt; ... &lt; a k and b 1 &lt; b 2 &lt; ... &lt; b k . Let

$$A _ { 1 } = \{ a _ { 1 }, \dots, a _ { c _ { 1 } } \}, A _ { 2 } = \{ a _ { c _ { 1 } + 1 }, \dots, a _ { c _ { 2 } } \}, \dots, A _ { d } = \{ a _ { c _ { d - 1 } + 1 }, \dots, a _ { c _ { d } } \},$$

$$B _ { 1 } = \{ b _ { 1 }, \dots, b _ { c _ { 1 } } \}, B _ { 2 } = \{ b _ { c _ { 1 } + 1 }, \dots, b _ { c _ { 2 } } \}, \dots, B _ { d } = \{ b _ { c _ { d - 1 } + 1 }, \dots, b _ { c _ { d } } \},$$

for some 0 = c 0 ≤ c 1 ≤ ... ≤ c d = k . If for all 1 ≤ i ≤ d A i &lt; B i and A i ∪ B i form an interval in l ( G ) , then ssat m ( n, G ) = Θ( n ) . See Figure 4 for an example.

Proof. Assume that G has m + 2 vertices for some m ∈ N . We create H from a copy of G \ { a, b } , keeping the same labels and from n -m isolated vertices denoted by V = { v , ..., v 1 n -m } . Then we add an edge v w i , for all 1 ≤ i ≤ n -m and w ∈ N G ( a ) ∪ N G ( b ) and label them as follows:

$$L ( v _ { i } w ) = \begin{cases} a _ { c _ { s } + 1 }. i. j, & \text{if $w=u_{j},c_{s}+1\leq j\leq c_{s+1}$,} \\ l ( a w ). i, & \text{if $w\in N_{G}(a) \, \bigwedge N_{G}(b)$,} \\ l ( b w ). i, & \text{if $w\in N_{G}(b) \, \bigwedge N_{G}(a)$.} \end{cases}$$

Adding an edge in V creates a copy of G with some labeling. It remains to check that this copy is labeled as in G . We add an edge v v i j to H , for 1 ≤ i &lt; i ′ ≤ n -m . The edge v v i i ′ has to play the role of ab in the copy of G . It is enough to check that the neighbors of v i and v i ′ are labeled correctly. If w ∈ N G ( a ) △ N G ( b ) , then l ( aw .i ) is mapped to l ( aw ) (resp. l ( bw .i ) is mapped to l ( bw ) ). If w ∈ N G ( a ) ∩ N G ( b ) , then for all 0 ≤ s ≤ d -1 the interval { a c s +1 .i. ( c s + 1) , ..., a c s +1 .i.c s +1 , a c s +1 .i . ′ ( c s + 1) , ..., a c s +1 .i .c ′ s +1 } is mapped to the interval { a c s +1 , ..., a c s +1 , b c s +1 , ..., b c s +1 } . For example, the interval { a , a 2 3 , b 2 , b 3 } in Figure 4, is given in the host graph by the interval { 6 .i. 2 6 , .i. 3 6 , .i . ′ 2 6 , .i . ′ 3 } .

We conclude that H indeed semisaturates G for a non-edge in the independent set V . Finally, we can add linearly many edges to H to get a semisaturating host graph.

Extremal functions of edge-ordered graphs. As we mentioned in Remark 3, the extremal function ex e ( n, G ) provides an upper bound for every definition of saturation function. Kucheriya and Tardos [19] characterized connected edgeordered graphs with linear extremal function. Note that any connected graph has at least linear saturation function by Theorem 5. This means that we can apply their results to get more examples of graphs with linear saturation function. In particular, their results include trees with certain edge-orderings, which we did not discuss here. By Corollary 26 we get that any edge-ordered tree (which is not a single edge) has a linear semisaturation function. However, we do not have the

Figure 4: { a , b 1 1 } = { 3 4 , } { , a , a 2 3 , b 2 , b 3 } = { 6 7 8 9 , , , } { , a , b 4 4 } = { 13 14 , } .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-352c5305-095a-481b-aa73-d6b89e065fa6.jpg)

same result for saturation. On the other hand, the extremal functions for paths already have more complicated behaviour. It was shown in [14] that extremal functions of certain paths on four edges can be Θ( n log n ), or even ( ) n 2 , while we just showed that for almost all paths the saturation function is linear. From Corollary 26 we get that edge-ordered forests have linear semisaturation functions, we do not know if the analogous result holds for saturation functions. It was shown in [14] that for any edge-ordered star forest we have the almost linear upper bound ex n, G ( ) = n 2 ( α n ( )) c , where α n ( ) is the inverse Ackermann function.

## 4 Bounded saturation functions

In this section, we only deal with sat m and ssat m , the other variations are discussed in later sections. Claim 6 characterizes edge-ordered graphs with bounded ssat m , they are exactly those in which e 0 is isolated. It may actually be true that the same holds for sat m . We consider special cases of edge-ordered graphs with isolated e 0 and prove that they have bounded sat m .

As we showed in Theorem 5, the saturation function can be bounded only if the minimal edge of a graph G is isolated. In the following, we consider a construction which will help us prove that for many edge-ordered graphs the saturation function is indeed bounded.

Definition 33. Let G be an edge-ordered graph whose edges are labeled with the set [ m ] . Take three copies of G , which are denoted by G 1 , G 2 and G 3 , such that each G i is labeled with a map k → 3( k -1) + i , for k ∈ [ m ] and i ∈ { 1 2 3 , , } . We denote by a b i i the corresponding minimal edge of G i . Finally, we obtain T G ( ) by merging the following pairs of vertices: a 1 and b 3 , a 2 and b 1 , a 3 and b 2 .

Lemma 34. Let G be an edge-ordered graph labeled with the set [ m ] , and let H be

Figure 5: Graph T G ( ) obtained by merging three copies of an A B -graph G .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-78e0ca74-f691-4708-9c28-ff7991622d86.jpg)

the union of T G ( ) and a set of isolated vertices. Then H semisaturates e 0 + G for any non-edge uv , where at least one of the vertices is isolated.

Proof. Assume that u is an isolated vertex and v is arbitrary. Then there must exist i ∈ { 1 2 3 , , } such that v / ∈ V ( G i ) . Therefore, uv + G i contains a copy of e 0 + G .

Therefore, to show that sat m ( n, e 0 + G ) is bounded for some G , it is enough to verify that T G ( ) does not contain e 0 + G .

Definition 35. We say that G is an A B -graph if it is obtained from two disjoint connected graphs G A and G B and adding a minimal edge e 1 = ab such that a ∈ V ( G A ) and b ∈ V ( G B ) .

Theorem 36. Let F = e 0 + G , where G is an A B -graph labeled with the set [ m ] . Then sat m ( n, F ) = O (1) .

Proof. We consider a host graph H which is a union of T G ( ) and isolated vertices. We also assume that a b i i connects the components G i,A and G i,B , as shown in Figure 5.

To show that H is F -free, we assume the contrary. First, we consider the case when none of the three minimal edges of H (that is, the edges a a , a a , a 1 2 2 3 3 a 1 ) are contained in the copy of F . Notice that by deleting these edges from H we would get a graph with three connected components, such that each of them has | V ( G ) | -1 vertices. Therefore, H cannot contain F in this case. Otherwise one such edge, wlog. a a 1 2 is contained in the copy of F and has to play the role of the minimal edge e 0 in the copy of F . However, H \ { a , a 1 2 } has connected components only of size at most | V ( G ) | -1 and thus it cannot contain G , which gives a contradiction.

We can easily see that any edge-ordered tree is an A B -graph.

Corollary 37. Let T be an edge-ordered tree, then sat m ( n, e 0 + T ) = O (1) .

Observation 38. Let H F ( ) be a saturation graph of F such that sat m ( n, e 0 + F ) = O (1) . Let G be an edge-ordered graph, such that l min ( G &lt; l ) min ( F ) . 4 .Then H F ( ) avoids G + F .

Using this observation, we can extend Theorem 36 to certain disconnected graphs.

Theorem 39. Let G = ∑ k i =1 G i be a disjoint union of A B -graphs such that, | V ( G i ) | ≤ | V ( G i +1 ) | and l min ( G i ) &lt; l min ( G i +1 ) for all 1 ≤ i ≤ k -1 . Then it follows that sat m ( n, e 0 + G ) = O (1) .

Proof. Let H be a union of a set of isolated vertices and of ∑ k i =1 T G ( i ) such that for edges e i ∈ T G ( i ) and e j ∈ T G ( j ) we have l ( e i ) &lt; l e ( j ) . It is simple to check that H indeed semisaturates e 0 + G apart from O (1) edges. To show that it also avoids e 0 + G , we assume the contrary and proceed by induction. The case k = 1 follows by Theorem 36. Then we assume that the claim holds for all 1 ≤ j ≤ k -1 .

We distinguish two cases. First, assume there is a copy e 0 + G in H such that G k is in T G ( k ) . In that case, by the inductional hypothesis either e 0 or another G j , for j &lt; k is also in T G ( k ) , but this is not possible by Observation 38. Second, assume there is a copy of G k in T G ( j ) for some j &lt; k . Since we assumed that | V ( G j ) | ≤ | V ( G k ) | , it follows that the copy of G k contains at least one of the edges in T G ( j ) that correspond to the minimal edge of G j , since by deleting these three edges we get three connected components of size | V ( G j ) | -1 . This implies that ∑ j -1 i =1 T G ( i ) contains a copy of e 0 + ∑ j -1 i =1 G i , which is not possible by the inductive hypothesis.

We identify several other families of edge-ordered graphs for which T G ( ) allows us to show that their saturation functions are bounded.

Claim 40. Let F = e 0 + G , such that G is connected and there exist no pair of vertices u, v ∈ V ( G ) for which at least one of the graphs G \{ u, v } , G \{ u } , G \{ } v is disconnected. Then sat m ( n, F ) = O (1) .

Proof. We use again the same construction T G ( ) as a host graph and we need to show that it avoids F . Notice first that a copy of G cannot be identically any of the graphs G 1 , G 2 and G 3 . So, it means that the copy of G has to be found in the union of either two or three of these graphs. Also a copy of G cannot contain any of the three edges a a , a a , a 1 2 2 3 3 a 1 , as there is no edge in that case which has the role of e 0 .

Assume wlog. that G is in the union of G 1 and G 2 , then a 3 is certainly in the copy of G , otherwise the graph would not be connected. But then a 3 is a vertex separator, which is not possible by assumption. We then assume that G can be contained in all three copies. In that case all three vertices a , a 1 2 , a 3 have to be in

4 Here l min ( G ) denotes the minimal label of G .

the copy of G . Moreover, since G is connected there should be at least two vertices among them, wlog. a 1 and a 2 such that there is a path of length at least two between them (recall that the edge a a 1 2 is not in the copy of G ). So, if we delete the vertices a 1 and a 2 , the copy of G becomes disconnected which contradicts our assumption.

Corollary 41. Let K r be a complete graph for r ≥ 2 with arbitrary labeling. Then sat m ( n, e 0 + K r ) = O (1) .

Claim 42. Let F = e 0 + G , where G is a connected graph whose minimal edge is ab and deg a ( ) ≥ deg b ( ) &gt; deg v ( ) for all v ∈ V ( G ) \ { a, b } . Then sat m ( n, F ) = O (1) .

Proof. We again want to show that T G ( ) is F -free. Notice that the only vertices that have large enough degrees to have the role of the vertices a and b , are the vertices a 1 , a 2 and a 3 . So, the minimal edge of G must connect two of these vertices, but then there is no edge in T G ( ) that can play the role of e 0 , which leads to a contradiction.

We now identify another family with bounded saturation function, but this time without using the construction T G ( ) . Instead of three copies of the graph G , now we use only two and add a few additional edges.

Theorem 43. Let F = e 0 + G , such that there exists a vertex v ∈ V ( G ) , which we call the peak , of degree d / ∈ { 0 2 , } whose incident edges are labeled with the set { 1 , ..., d } (the rest of the edges get larger labels) and G -v is connected. Then sat m ( n, F ) = O (1) .

Proof. We proceed by constructing a host graph H that semisaturates F . We first join two copies of G at the peak v and we denote the two disjoint parts by G ′ and G ′′ . Then we consider the neighbors { v , v 1 2 , ..., v d } ⊂ V ( G ′ ) of v and we label each edge l ( vv i ) = 3( i -1)+1 for 1 ≤ i ≤ d . Additionally, we label by l ( vu i ) = 3( i -1)+2 , where u i is the neighbor of v in G ′′ for all 1 ≤ i ≤ d . Moreover, we add the edges between u 1 and all the v i and we label them with l ( u v 1 i ) = 3 i . The remaining edges in G ′ and G ′′ can be any labels greater than 3 d that respect the edge-order inherited from G . See Figure 6 for a construction. As usual, the remaining vertices are isolated.

First, we want to show that H is F -free. We treat the case d = 1 separately by observing that no matter which edge we take to play the role of e 0 , the copy of G must be contained in either G ′ or G ′′ . That is not possible, since G is larger than any of them. From now on, we consider the case d ≥ 3 . Assume on the contrary that H is not F -free and assume that in a copy of F we have a peak p / N ∈ H [ v ] . In that case, we can notice that none of the edges connecting two vertices of N H [ v ] can be in the copy of G . However the rest of the graph H contains two connected components with less than | V ( G ) | vertices, a contradiction.

Let p = v be the peak, in that case one of the edges u v , ..., u 1 1 1 v d must play the role of e 0 in the copy of F . Thus, if we remove v from the copy of G , we get

Figure 6: A saturation graph if the peak has degree d = 3 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-2d2f4dfc-c69c-45aa-8231-67537a1d7531.jpg)

a disconnected graph, as some of its neighbors are in G ′ and the other are in G ′′ contrary to our assumption that G -v is connected.

Assume now that the peak is p = v i for some 1 ≤ i ≤ d . As G is larger than G ′ , the copy of G has a vertex outside G ′ . The peak p must have at least one neighbor in G ′ (as it has only two further incident edges in H ) and such an edge has larger label than any edge between G ′ , p , and G ′′ . Therefore, no edge in the copy of G -v can use the edges between G ′ , p , and G ′′ and so G -v is a disconnected graph, a contradiction. A similar argument works for p ∈ { u , ..., u 2 d } . It remains to check if u 1 can be the peak. Clearly, u v 1 and u v 1 1 cannot be in the copy of G as there would be no choice for the minimal edge. Thus, one neighbor of the peak has to be in G ′′ , and for the same reason as in the previous case, we get that u 1 cannot be the peak.

It remains to show that H is F -saturated for the non-edges incident to isolated vertices. Indeed, if we take an isolated vertex and connect it with any vertex in G ′ or G ′′ , we get a new copy of F . If we connect it with v , then u 1 can have the role of the peak and together with G ′ we get a copy of F .

Finally, we can add a bounded number of edges greedily between non-isolated vertices to get a required host graph.

Lemma 44. Let F = ∑ k i =1 F i be such that l ( F i ) &lt; l F ( j ) for all 1 ≤ i &lt; j ≤ k and sat m ( n, e 0 + F i ) = O (1) , for all 1 ≤ i ≤ k , where F i are connected. Then it follows that sat m ( n, e 0 + F ) = O (1) .

Proof. Let H be a union of ∑ k i =1 H F ( i ) and isolated vertices, where H F ( i ) is the non-isolated part of the saturation graph of F i . Additionally we label H such that l ( H F ( i )) &lt; l H F ( ( j )) for all 1 ≤ i &lt; j ≤ k . It is simple to see that H semisaturates e 0 + F apart from O (1) edges. So, it remains to check that it also avoids e 0 + F .

We proceed by induction on k . The case k = 1 follows directly by assumption. Assume on the contrary that for k the claim fails. As the claim holds for k -1 by inductive hypothesis, ∑ k -1 i =1 H F ( i ) contains no copy of e 0 + ∑ k -1 i =1 F i . This implies that there is a copy of F j in H F ( k ) for some j ≤ k -1 , and clearly a copy of F k in H F ( k ) since l ( F j ) &lt; l F ( k ) . But this is not possible by Observation 38.

The previous result allows us to take a monotone union of any connected graphs that we previously showed to have bounded saturation function. Among others, this generalizes Corollary 37.

Definition 45. Let F be a monotone forest if F = ∑ k i =1 T i such that every T i is a tree and l ( T i ) &lt; l T ( j ) for all 1 ≤ i &lt; j ≤ k .

Corollary 46. For every monotone forest F , we have sat m ( n, e 0 + F ) = O (1) .

## 5 sats and ssats

Recall that in Definition 2, we stated two more definitions of saturation function. The reason why we do not have a unique definition is that we have a choice on how to label the missing edge. So far, we worked with the definition where a new edge always gets the minimal label.

Another interesting definition of saturation allows a new edge to introduce a copy of a given edge-ordered graph G for some label and we denoted this saturation function by sat s ( n, G ) . As we already mentioned at the beginning sat s ( n, G ) ≤ sat m ( n, G ) , which means that all the upper bounds that we proved for sat m definition hold for sat s as well. This also includes the general O n ( log n ) upper bound for semisaturation. Again, with an analogous proof it follows that there is no dichotomy in this framework either. However, this time the result is obtained for a more restricted family of graphs:

Corollary 47. Let G be an edge-ordered graph. If for every edge ab ∈ E G ( ) there exist v, w ∈ N G ( a ) ∩ N G ( b ) such that l ( av ) &lt; l aw ( ) and l ( bv ) &gt; l bw ( ) , then sat s ( n, G ) ≥ ssat s ( n, G ) = Ω( n √ log n ) .

̸

Notice that none of the diamond graphs shown on Figure 1 satisfy this property. However, we can take a K 4 and label it as shown on Figure 7. Moreover, for K k with k ≥ 5 the following edge-order is also suitable: label the vertices with [ k ] and then for every i = j in [ k ] the edge ij gets label min( | j - | i , k -| j - | i ) , that is, the cyclic distance between i and j when taken modulo k . Then we perturb the labels slightly so there are no equal labels on the edges. It is easy to check that this edge-order satisfies the assumption of Corollary 47 for every k ≥ 5 .

Corollary 48. For every k ≥ 4 , there exists an edge-ordered graph G k with underlying graph K k , such that sat s ( n, G k ) ≥ ssat s ( n, G k ) = Ω( n √ log n ) .

Note that, from the inequality sat s ( n, G ) ≤ sat m ( n, G ) we get that whenever a graph G has linear sat m function and it contains no isolated edges, then it also has linear sat s function. This implies that the cycles and paths we discussed in Claims 28 and 29 also have linear saturation function for this definition. Moreover, we can use the same approach as in Theorem 25 to find an even larger family of edge-ordered graphs with linear semisaturation function.

Corollary 49. Let G be an edge-ordered graph which has no isolated edges. If there exists an edge ab ∈ E G ( ) such that N G ( a ) ∩ N G ( b ) = ∅ , then ssat s ( n, G ) = Θ( n ) .

Figure 7: An example of edge-ordered K 4 with a superlinear sat s function.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-e09bb440-2e63-44b3-bf64-3f8249c0f4e7.jpg)

## 6 sate and ssate

The most natural saturation definition for edge-ordered graphs seems to be sat e ( n, G ) where we allow the new edge to have any label inserted in the linear order of the edges of the host graph H . In this section we state several results about this variant. We left these to the be last as most of the forthcoming results follow from the results that we have already proved.

Recall that for all edge-ordered graphs we have sat m ( n, G ) ≤ sat e ( n, G ) . Therefore, all the lower bounds that we showed for sat m also hold for sat e definition. Most importantly, this gives us a family of edge-ordered graphs with superlinear semisaturation (and saturation) function. The next result follows directly from Theorem 18.

Corollary 50. Let G be an edge-ordered graph. If ab ∈ { e , e 0 max } and there exist two vertices v, w ∈ N G ( a ) ∩ N G ( b ) such that l ( av ) &lt; l aw ( ) and l ( bv ) &gt; l bw ( ) , then sat e ( n, G ) ≥ ssat e ( n, G ) = Ω( n √ log n ) .

We now show the upper bound for the diamond graph D 0 .

## Theorem 51.

$$\ s s a t _ { e } ( n, D _ { 0 } ) \leq s a t _ { e } ( n, D _ { 0 } ) = O \left ( n \frac { \log n } { \log \log n } \right ).$$

Proof. We start by H = K k,n , the host graph that we constructed in the proof of Theorem 21. Recall that H was labeled by R + . We add now two more vertices u 1 and u 2 , and we connect them with the independent set in H that we denote by V = { v , . . . , v 1 n } . We label the edges as follows:

$$l ( u _ { 1 } v _ { i } ) = - 3. i \text{ and } l ( u _ { 2 } v _ { i } ) = - 1. i \text{ for all } 1 \leq i \leq n.$$

We also add the edge u u 1 2 and label it by l ( u u 1 2 ) = -2 . Notice that by adding any edge between two vertices in V and labeling it by any positive number, we obtain a copy of D 0 , where the new edge plays the role of bv , the maximal edge in D 0 (See Figure 1). Recall that from Theorem 21, if any edge in V is added with negative label or zero, a new copy of D 0 is created. Therefore we get a host graph that semisaturates D 0 for any non-edge in V for any real label.

It remains to check that the host graph avoids D 0 , so we assume the contrary. Notice that by deleting the edge u u 1 2 , we get a complete bipartite graph. Therefore, since D 0 is not bipartite, u u 1 2 has to be in the copy of D 0 . Even more, u u 1 2 has to play the role of the minimal edge ab . But that is not possible, because l ( u v 1 i ) &lt; l u u ( 1 2 ) for all 1 ≤ i ≤ n . This implies that u u 1 2 cannot be the minimal edge, which gives a contradiction. Finally, we can add greedily edges between k +2 vertices without introducing a copy of D 0 , which does not affect the order of magnitude of the saturation function.

Recall that by Theorem 9 if G is an edge-ordered graph in which e 0 and e max are isolated, then either sat e ( n, G ) = O (1) or sat e ( n, G ) = Ω( ) n . Otherwise, sat e ( n, G ) = Ω( n ) . Here we show why Ω( n ) was necessary in the statement already for the e 0 + G + e max part, a behaviour that is different from that of sat m function in Theorem 5.

Theorem 52. For every k ≥ 5 , there exists an edge-ordered graph G k with underlying graph K k , such that sat e ( n, e 0 + G k + e max ) = Ω( n √ log n ) .

Proof. Let G k be an edge-ordered graph with underlying graph K k . We denote F k = e 0 + G k + e max . Let H be a host graph saturating F k for sat e . Take a nonedge. Adding it as a new edge e with any label should introduce a copy of F k . Note that there are only finitely many essentially different labels (one between each pair of consecutive labels in F k ), so we only concentrate on them.

We claim that there must be a label for which in the introduced copy of F k the new edge e does not play the role of e 0 nor e max of F k . Assume on the contrary and take the smallest label such that e plays the role of e max in a copy F ′ k of F k (this exists, as when we choose the largest label for e then e must play the role of e max ). Take the next smallest possible label for e (this again must exist as the current label could not have been the smallest), then e must play the role of e 0 in a copy F ′′ k of F k . Let G ′ k and G ′′ k be the K k part of F ′ k and F ′′ k , respectively. Notice that all the labels of the edges of G ′ k are smaller than the labels of the edges of G ′′ k , except possibly of the edge that appears in both of them. Therefore, their vertex sets intersect in at most two vertices. In addition the edge that plays the role of e max in F ′′ k can again have at most one common vertex with G ′ k . Therefore, there are at least two vertices in G ′ k , which are not in F ′′ k . This edge can also play the role of e 0 in F ′′ k instead of e , contradicting that H avoids F k .

Thus, for each non-edge we can add it with an appropriate label such that we get a copy of F k in which the new edge e plays the role of an edge in G k . That is, adding e with this label must introduce a new copy of G k . This means that H is semisaturating G k for ssat s , therefore sat e ( n, e 0 + G k + e max ) = | H | ≥ ssat s ( n, G k ) . Applying Corollary 48 gives that there is an appropriate G k such that ssat s ( n, G k ) = Ω( n √ log n ) , finishing the proof.

One might wonder if the main observation in the previous proof holds in some generality, that is, if sat e ( n, e 0 + G + e max ) = Ω( ssat s ( n, G )) always. We have seen that this holds if G is an edge-ordered complete graph on at least 5 vertices. Here

Figure 8: F = e 0 + G + e max , where G is the cherry graph and an almost host graph H for F .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-f760158d-caa1-48c1-abf5-3a0bd1109662.jpg)

we give an example that shows that this is not true already for a graph G with two edges. Let G be the unique edge-ordered cherry graph (has two edges on three vertices). By Corollary 13 ssat s ( n, G ) = Ω( n ) . On the other hand we claim that F = e 0 + G + e max has sat e ( n, F ) = O (1) . Let H be the graph on n vertices such that n -8 of the vertices are isolated, on the remaining 8 vertices we have two K 4 's, labeled as shown on Figure 8. It is easy to check that H avoids F yet adding any new edge incident to at least one isolated vertex with any label introduces a copy of F . Therefore, by greedily adding further edges between the two K 4 's if necessary, we get a saturating host graph on n vertices and O (1) edges.

Furthermore, notice that if two copies G ′ and G ′′ of a graph G , such that l ( G ′ ) &lt; l G ( ′′ ) , can be edge-disjointly added on | V ( G ) +1 | vertices, then sat e ( n, e 0 + G + e max ) = O n ( ) . Indeed, the host graph can be obtained by adding a vertex disjoint cherry with minimal and maximal edge to this graph on | V ( G ) +1 | vertices (the two copies of G have labels that form two intervals of l ( G ) ), as well as arbitrary many isolated vertices. This graph clearly avoids e 0 + G + e max and by adding an edge with any label between two isolated vertices we get a copy of e 0 + G + e max . Thus by adding O n ( ) edges we get a host graph. With this construction, we can produce many examples that have at most linear saturation function.

We can observe that the analogue of Corollary 27 also holds for sat e definition. However, we need to add a condition that G -e max also becomes bipartite. By gluing two host graphs together, we can see that we still keep the bipartite property, which means that the host graph remains G -free. See Figure 9 for an example.

Corollary 53. Let G be a non-bipartite edge-ordered graph. Let e 0 = ab and e max = cd such that G -e 0 and G -e max are bipartite and N G ( a ) ∩ N G ( b ) = N G ( c ) ∩ N G ( d ) = ∅ , then sat e ( n, G ) = Θ( n ) .

From this we get the following explicit infinite family of graphs that have linear ssat e and sat e function.

Corollary 54. Let C 2 k +1 be an edge-ordered cycle graph. Then for every k ≥ 1 ,

$$\ s a t _ { e } ( n, C _ { 2 k + 1 } ) = \Theta ( n ) \ a n d \ s s a t _ { e } ( n, C _ { 2 k + 1 } ) = \Theta ( n ).$$

To finish this section, we also present an infinite family of edge-ordered graphs with bounded sat e function. Since all edge-ordered matching graphs with fixed

Figure 9: Underlying bipartite graph that saturates C 5 for a non-edge in { v , v 1 2 , v 3 , v 4 , v 5 } .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00457v1-figure-d7d18949-0a27-4826-a939-74f4c4bc2e08.jpg)

number of edges are isomorphic to each other, in this case saturation problem is equivalent to saturation problem of unordered graphs. Therefore, we get from [15] that:

Corollary 55. Let M k be an edge-ordered matching graph. Then

$$\ s a t _ { e } ( n, M _ { k } ) = O ( 1 ) \, \, f o r \ e v e r y \ k \, \geq 1.$$

## 7 Open questions

We conclude by highlighting the most interesting problems left open.

We do not have any example of an edge-ordered graph with linear sat m saturation function whose minimal edge is isolated. The construction T G ( ) (as in Figure 5) seems like a good candidate to show that such a graph does not exist.

$$\text{Conjecture } 5 6. \ L e t \ F = e _ { 0 } + G, \text{ then } s a t _ { m } ( n, F ) = O ( 1 ).$$

Note that the analogous statement for sat e definition, where we replace e 0 with e 0 + e max , is not true, as we have seen earlier.

Theorem 25 shows that if the endvertices of the non-isolated minimal edge of G have disjoint neighborhoods, then the semisaturation function of G is linear. So far, we do not have a counterexample and it is possible that this family has linear saturation function, as well.

Conjecture 57. Let G be an edge-ordered graph and let ab be the minimal edge in G such that deg a ( ) ≥ 2 . If N G ( a ) ∩ N G ( b ) = ∅ , then sat m ( n, G ) = Θ( n ) .

The previous two conjectures raise a question whether in general for a given graph, the order of magnitude of sat m and ssat m are always the same. We do not have a counterexample for this claim. However, they do not have necessarily the same exact values, for example one can show that sat m ( n, M k ) = 3( k -1) and ssat m ( n, M k ) = k +1 , for k ≥ 2 . For sat e definition, we already have some counterexamples. Theorem 10 and Theorem 52 give edge-ordered graphs with bounded ssat e function, but superlinear sat e function.

The main open question that remains, is to find a general upper bound for saturation function. We expect to have a non-trivial upper bound and we state it in terms of sat e which implies the same upper bound for sat m .

## Conjecture 58. For every edge-ordered graph G , we have sat e ( n, G ) = O n ( 1+ (1) o ) .

It seems plausible to expect that the same upper bound as for semisaturation can be proven. Therefore, we also state the following stronger conjecture.

Conjecture 59. For every edge-ordered graph G , we have sat e ( n, G ) = O n ( log n ) .

Besides that, it might be possible that the general upper bound depends on the chosen definition.

We can check that the construction given in the proof of Theorem 7, indeed gives a saturation upper bound for many graphs. However, for some cases, such as certain families of trees, the construction only gives a semisaturation upper bound.

The semisaturation problem can be studied separately and we managed to understand the behaviour of semisaturation functions slightly better. The major question is whether the upper bound can be improved, or at least can we find an example when the bound is achieved.

## Problem 60. Is there an edge-ordered graph G such that ssat e ( n, G ) = Θ( n log n ) ?

Studying thoroughly the diamond graph D 0 was helpful to understand how the saturation functions behave for more general families of edge-ordered graphs. In fact, we were able to extend the lower and upper bounds to infinite families of graphs. One possible direction is to study further the saturation function of D 0 , which would again most likely lead to a more general result. On the other hand, D 0 is the only connected edge-ordered graph for which we showed an upper bound O ( n log n log log n ) . Can we extend this result to a more general family of connected edge-ordered graphs?

We were able to show at least three different behaviours of saturation functions. A natural question is if there are more than that, or more generally, are there finitely or infinitely many different orders of magnitude for saturation functions of edge-ordered graphs? Analogous question for semisaturation functions is also open.

Recently, the saturation functions of sequences were studied [4]. They showed that the saturation function is either bounded or at least linear. It would be interesting to investigate whether an example with a superlinear saturation function

can be found, or to show that the usual dichotomy holds. Regarding semisaturation functions, they showed that they are at most linear, which is not the case for edge-ordered graphs.

## Acknowledgements

Part of this research was performed while the first author was visiting the Institute for Pure and Applied Mathematics (IPAM), which is supported by the National Science Foundation (Grant No. DMS-1925919).

Research supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences, by the National Research, Development and Innovation Office - NKFIH under the grant K 132696 and FK 132060, by the ÚNKP-23-5 New National Excellence Program of the Ministry for Innovation and Technology from the source of the National Research, Development and Innovation Fund and by the ERC Advanced Grant 'ERMiD'. This research has been implemented with the support provided by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, financed under the ELTE TKP 2021-NKTA-62 funding scheme.

## References

- [1] Eyal Ackerman and Balázs Keszegh. On the number of tangencies among 1-intersecting x-monotone curves. European Journal of Combinatorics , 118:103929, 2024.
- [2] Noga Alon. On bipartite coverings of graphs and multigraphs, 2023. arXiv: 2307.16784 .
- [3] Noga Alon and Jacob Fox. personal communication, 2024.
- [4] Anand, Jesse Geneson, Suchir Kaustav, and Shen-Fu Tsai. Sequence saturation, 2024. arXiv:2405.06202 .
- [5] Benjamin Aram Berendsohn. An exact characterization of saturation for permutation matrices. Comb. Theory , 3(1):Paper No. 17, 35, 2023.
- [6] Vladimir Bošković and Balázs Keszegh. Saturation of Ordered Graphs. SIAM J. Discrete Math. , 37(2):1118-1141, 2023.
- [7] Richard A. Brualdi and Lei Cao. Pattern-avoiding (0,1)-matrices and bases of permutation matrices. Discrete Applied Mathematics , 304:196-211, 2021.
- [8] Bryan L. Currie, Jill R. Faudree, Ralph J. Faudree, and John R. Schmitt. A survey of minimum saturated graphs. The Electronic Journal of Combinatorics , DS19, 2021.

| [9]   | Jinquan Dong and Yanpei Liu. On the decomposition of graphs into complete bipartite graphs. Graphs Combin. , 23(3):255-262, 2007.                                                         |
|-------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [10]  | Paul Erdős, András Hajnal, and John W. Moon. A problem in graph theory. The American Mathematical Monthly , 71(10):1107-1110, 1964.                                                       |
| [11]  | Radoslav Fulek and Balázs Keszegh. Saturation problems about forbidden 0-1 submatrices. SIAM J. Discret. Math. , 35(3):1964-1977, 2021.                                                   |
| [12]  | Zoltán Füredi, Peter Horák, Chandra M. Pareek, and Xuding Zhu. Minimal oriented graphs of diameter 2. Graphs and Combinatorics , 14:345-350, 1998.                                        |
| [13]  | Jesse Geneson. Almost all permutation matrices have bounded saturation functions. Electron. J. Comb. , 28(2):P2.16, 2021.                                                                 |
| [14]  | Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gá- bor Tardos, and Máté Vizer. Turán problems for edge-ordered graphs. J. Combin. Theory Ser. B , 160:66-113, 2023. |
| [15]  | László Kászonyi and Zsolt Tuza. Saturated graphs with minimal number of edges. Journal of Graph Theory , 10(2):203-210, 1986.                                                             |
| [16]  | Gyula Katona and Endre Szemerédi. On a problem of graph theory. Studia Sci. Math. Hungar. , 2:23-28, 1967.                                                                                |
| [17]  | Balázs Keszegh and Dömötör Pálvölgyi. The number of tangencies between two families of curves. Combinatorica , 43(5):939-952, Oct 2023.                                                   |
| [18]  | Gaurav Kucheriya and Gábor Tardos. A characterization of edge-ordered graphs with almost linear extremal functions. Combinatorica , 43(6):1111- 1123, 2023.                               |
| [19]  | Gaurav Kucheriya and Gábor Tardos. On edge-ordered graphs with linear extremal functions, 2023. arXiv:2309.10558 .                                                                        |
| [20]  | Oleg Pikhurko. The minimum size of saturated hypergraphs. Combinatorics, Probability and Computing , 8(5):483-492, 1999.                                                                  |
Vladimir Bošković Balázs Keszegh
Saturation of edge-ordered graphs
For an edge-ordered graph $G$, we say that an $n$-vertex edge-ordered graph
$H$ is $G$-saturated if it is $G$-free and adding any new edge with any new
label to $H$ introduces a copy of $G$. The saturation function describes the
minimum number of edges of a $G$-saturated graph. In particular, we study the
order of magnitude of these functions. For (unordered) graphs, $0$-$1$
matrices, and vertex-ordered graphs it was possible to show that the saturation
functions are either $O(1)$ or $\Theta(n)$. We show that the saturation
functions of edge-ordered graphs are also either $O(1)$ or $\Omega(n)$.
However, by finding edge-ordered graphs whose saturation functions are
superlinear, we show that such a dichotomy result does not hold in general.
  Additionally, we consider the semisaturation problem of edge-ordered graphs,
a variant of the saturation problem where we do not require that $H$ is
$G$-free. We show a general upper bound $O(n \log n)$ and characterize
edge-ordered graphs with bounded semisaturation function.
  We also present various classes of graphs with bounded, linear and
superlinear (semi)saturation functions. Along the way, we define a natural
variant of the above problem, where the new edge must get the smallest label.
The behaviour of the two variants shows many similarities, which motivated us
to investigate the second variant extensively as well.