WorksMathematics
Full immersions in Eulerian group-labeled graphs
Abstract
An immersion of a graph H in a graph G is full if the immersion uses every edge of G. We give a structure theorem for group-labeled Eulerian graphs excluding a fixed group-labeled graph as a full immersion.
Introduction
In this paper, we extend the well-developed theory of structure theorems for graphs excluding a fixed immersion to what we call full immersions in group labeled graphs. A primary goal in doing so is to develop tools for analyzing vertex minors in graphs which are obtained from circle graphs by adding a fixed number of vertices arbitrarily attached to the rest of the circle graph.
All graphs in this paper are finite and possibly have both loops and parallel edges. A graph contains a graph as an immersion if there exists a function whose domain is such that:
and for all , ;
for all edges with distinct ends and , is a walk with endpoints and ; for all loops attaching to the vertex , is a non-empty closed walk which starts and ends at ;
For every edge , the walk uses each edge at most once; for all distinct edges , the walks and are pairwise edge disjoint.
The vertices are the branch vertices of the immersion, and the walks for are denoted the branch walks. In the literature, a distinction is made between weak and strong immersions, where strong immersions have the additional requirement that no branch vertex be contained as an internal vertex of a branch walk. However, for our purposes here, we make no such distinction and use immersion to refer to what has historically been called weak immersion. Immersions were introduced by Nash-Williams in [12] where he conjectured that graphs are well quasi-ordered under immersion containment. As part of their graph minors series, Robertson and Seymour affirmed the conjecture [16] and general structure theorems for graphs excluding a fixed immersion were independently proven in [4, 19].
We present a structure theorem for excluded full immersions in group labeled graphs. An immersion of a graph in a graph is full if every edge of is contained in the union of the edge sets of the branch walks.
Given a group , a -labeled graph is an undirected graph where each edge is assigned both an orientation and a label in . Informally, when considering immersions in group-labeled graphs, the sequence of edges in a branch walk has a weight in obtained by the product of the weights on the edges of the walk, where for each edge on the walk, we right-multiply by when traversing an edge according to the orientation, and right-multiply by when traversing the edge contrary to the orientation. Some care is needed to rigorously deal with the orientations and we give the exact definition below. Group-labeled graphs have been used in a number of contexts: graph embeddings and coverings [8, 9], symmetry-forced rigidity [1, 10, 18] (i.e., bar and joint frameworks where every non-rigid motion breaks a specified symmetry), as well as structural [5, 7, 17] and extremal [13, 14] properties of matroids.
A primary motivation for studying full immersions in Eulerian group-labeled graphs comes from the structure theory of excluded vertex minors. A circle graph is the intersection graph of a family of chords of a circle. Circle graphs play a central role in the area, including Bouchet’s characterization by excluded vertex minors [3] and the vertex-minor grid theorem [6]. Equivalently, for a circle graph there exists a 4-regular multigraph with for which a fixed Eulerian tour encodes the adjacencies in : two vertices are adjacent in exactly when their occurrences alternate along the tour [2, 15]. In this representation, local complementation at a vertex corresponds to changing the Euler tour by rerouting at the vertex , and vertex-minor containment in is reflected by full immersion in the corresponding 4-regular graphs. This correspondence extends naturally to graphs obtained from circle graphs by adding vertices with arbitrary neighborhoods. Consider a graph obtained by adding a vertex to with an arbitrary neighborhood in . The neighborhood of can be encoded by a -labeling of the edges of , with adjacency determined by the parity of the sum of the labels along the portion of the Euler tour between the two occurrences of a vertex. Labeled full immersions in the labeled then allow us to study vertex-minors within . For graphs obtained by adding vertices to the circle graph , we can again encode their neighborhoods coordinatewise by labels in in . Thus, full immersions in group-labeled graphs provide a framework for studying vertex minors in graphs which are nearly circle graphs.
In general, we will follow standard graph theoretic notation. Given a graph and a set of vertices , we write (or simply when is clear from the context) for the set of all edges of with exactly one end in . If consists of a single vertex , we write . We will use to refer to the set . For a set and , we will use the notation for .
Group-labeled Graphs
We now introduce the notation to work with orientations of edges in group labeled graphs. Given a graph , for each edge of we define two distinct oriented edges which we denote by and . We call the underlying edge of an oriented edge and will refer to as an orientation of the edge . An oriented edge has a tail and a head, each of which is an endpoint of the underlying edge . If has two distinct endpoints, then the head and tail are distinct vertices. Moreover, it holds for all oriented edges that the head of is equal to the tail of . We say that is oriented from its tail to its head. We write for the set of all oriented edges arising from the edges of . Depending on the context, we will want to consider the degree of a vertex either taking into account possible loops or not. To that end, we adopt the following convention. The degree of a vertex , denoted , is plus twice the number of loops incident to . We will use as notation to indicate . Note that and always have the same parity, regardless of the presence of loops.
Let be a group. We denote the group operation multiplicatively and the identity by . A -labeling of a graph is a function such that for any edge of . We call the label of an oriented edge . Throughout the article, we adopt the convention that for any labeling function . A -labeled graph is a pair where is a graph and is a -labeling of . There is an equivalence relation on -labelings defined as follows. Given a -labeled graph , a vertex , and a group element , shifting by at means to append at the beginning of the label of each oriented edge with tail and to append at the end of the label of each oriented edge with head . Thus, if is an oriented loop at , then its new label after shifting is . Likewise, if is an oriented edge whose tail is and whose head is not , then its new label is . This is the inverse of , which is the new label of . We say that a -labeling of is a shifting of if it can be obtained by a (finite) sequence of such shifts.
A trail in a graph is a sequence of oriented edges , , such that the underlying edges are all distinct, and for each , the head of equals the tail of . Note that the endpoints of the edges need not be distinct; the same vertex may be visited multiple times. The tail of is the tail of and the head of is the head of . We call the head and tail of its ends. We use to refer to the set of vertices which are either heads or tails of oriented edges in . We write to refer to the undirected edges of which are the underlying edges of oriented edges contained in . We say two trails and are edge disjoint if . Given a group-labeling of , the label of is . The inverse of is the trail which is the sequence of edges in the reverse order and with the reverse orientation. Thus . The transitions of are the ordered pairs for . Thus has transitions. We view transitions of the form and as being equivalent; thus has the same transitions as .
Immersions
We now extend the definition of immersions to group-labeled graphs.
Let be a group. We say that a -labeled graph admits an immersion of a -labeled graph if there exist a shifting of and a function which injectively maps to and which maps to trails in such that
for any oriented edge , the trails and are inverses,
for any distinct edges and of , the trails and are edge-disjoint, and
for any oriented edge of , the tail of is mapped to the tail of , the head of is mapped to the head of , and .
We say that is an immersion of into . As in the case of undirected graphs, we call the image of under the branch vertices and the image of under the branch trails. The transitions of an immersion are the transitions of its branch trails. The labeling is an accommodating labeling of the immersion; in general, an accommodating labeling will not necessarily be unique.
A graph contains a graph as a near-full immersion if there is an -immersion such that there is at most one non-trivial component after deleting edges of in , and moreover, the component , if it exists, contains a branch vertex of . For a vertex , if the component , when it exists, contains the vertex , we say contains as an -near-full immersion. The definition extends analogously to group labeled immersions.
Observation 1.1. If has an -near-full immersion of , and has a -near-full immersion of with , then has a -near-full immersion of .
Our primary tool in proving the structure theorem for excluded full immersions in Eulerian group labeled graphs is the following theorem which says that excluding a fixed near-full immersion implies excluding some larger group labeled immersion with no further requirements on the edge set which it utilizes.
Theorem 1.2. Let be a finite group. For every -labeled graph there exists a -labeled graph such that for every Eulerian 4-edge-connected -labeled graph and for every vertex , if contains as an immersion, then contains as an -near-full immersion.
The structure theorem
The structure theorem for Eulerian group-labeled graphs excluding a fixed graph as a full immersion builds on the structure of graphs excluding a group-labeled immersion. We give the notation necessary to state the structure theorem for excluded group-labeled immersions (without the requirement that they be nearly full), and then present the statement for excluded full group-labeled immersions.
A tree-cut decomposition of a graph is a pair such that is a tree and is a collection of pairwise-disjoint (possibly empty) subsets of whose union is . The sets in are the bags of the decomposition.
Roughly, the structure theorem for excluded group-labeled immersions says that each bag either 1) has a “torso” with few high degree vertices, or 2) has “almost all of its edges” labeled over a proper subgroup.
So, let be a graph, and let be a tree-cut decomposition of . Given a bag , the torso of is the graph obtained from as follows. Let be the components of . For each , let . Then is created by identifying each non-empty set to a single vertex, which we call a new vertex of the torso. We keep parallel edges, but we remove any loops at the new vertices.
Now, let be a group, let be a -labeled graph, and let . Then a certificate for is a tuple so that is a set of edges of with and is a shifting of so that the -labels of orientations of the edges in generate a proper subgroup of . The value of a certificate is
This counts the edges of , except edges with both ends in are counted twice.
Theorem 1.3 ([11]). For any finite group and positive integers and , there is an integer so that the following holds for any 2-edge-connected -labeled graph which forbids an immersion of some -vertex -labeled graph where each vertex is incident to at most edges. There exist a shifting of and a tree-cut decomposition of such that for every bag , at least one of the following holds.
There are at most vertices in the torso of of degree greater than , and none of them are the new vertices of the torso.
There exists so that is a certificate for of value at most .
We are now able to state the structure theorem for excluded full group labeled immersions in Eulerian graphs. The theorem finds the same structure as Theorem 1.3 unless the total edge labels of and differ in an elementary abelian -group quotient of .
Theorem 1.4. Let be a finite group. For every Eulerian -labeled graph with at least one edge, there exists a positive integer such that the following holds. Let be a -edge-connected Eulerian -labeled graph with no full immersion. Then one of the following holds.
There exists a normal subgroup of such that is isomorphic to for some nonnegative integer , and over this quotient labeling the sum of the edge labels in differs from that in .
There exist a shifting of and a tree-cut decomposition of such that for every bag , at least one of the following holds.
(a) There are at most vertices in the torso of of degree greater than , and none of them are the new vertices of the torso.
(b) There exists such that is a certificate for of value at most .
The proof of Theorem 1.4 is presented in § 4.
Outline
The paper is organized as follows. In § 2, we present Theorem 2.1 showing that if a -edge-connected -labeled Eulerian graph has many edge disjoint circuits sharing a common vertex each with label not in a fixed subgroup of , then the edge set of the whole graph can be partitioned into edge disjoint circuits through each with label outside . This packing result is used in § 3 to prove Theorem 1.2 which states that excluding a fixed group-labeled as a near-full immersion in a -edge-connected Eulerian graph implies that does not contain a larger as a group labeled immersion without the requirement that it be nearly full. Already, Theorem 1.2 together with Theorem 1.3 yields a structure theorem for excluded near-full immersions in -edge-connected group-labeled Eulerian graphs. Finally, in § 4, we determine when a near-full immersion can be extended to a full immersion, providing the final ingredient needed to prove Theorem 1.4.
Decomposing to circuits labeled outside of a subgroup
Let be a group, let be a subgroup of , let be a -labeled graph, and let be a vertex of .
A circuit in is a trail whose head and tail are equal; we say that it begins and ends at that vertex. Given a vertex of , an -packing of is a collection of pairwise edge-disjoint circuits so that each circuit begins and ends at . We say that the -packing saturates if . We call an -packing an -packing if every circuit has label outside of . Similarly, an -decomposition is an -packing so that every edge of is in for some .
This section is dedicated to proving the following theorem.
Theorem 2.1. Let be a positive integer. Let be a group, let be a subgroup of , let be a -labeled Eulerian graph which is 4-edge-connected, and let be a vertex of such that there exists an -packing of size . Then there exists an -decomposition of size at least .
We proceed to introduce the set-up needed to establish Theorem 2.1 above. Fix an Eulerian, 4-edge-connected -labeled graph , a vertex , and an -packing which saturates . We refer to each nontrivial connected component of as an unused component of . Note each unused component is an Eulerian subgraph of . We write for the auxiliary bipartite graph whose vertices in one part are the circuits in , in the other the unused components of , and vertices in distinct parts are adjacent if and only if the corresponding parts share a vertex. Whenever is clear from the context we drop the subscript. Given a vertex of we write for the degree of in ; whenever we speak of the degree of a circuit or an unused component we implicitly mean their degree in .
Let be an unused component of of degree one, and the unique circuit which contains a vertex of . We define the closure of , denoted by , to be a containment minimal set so that and contains at most two edges in . Observe that this notion is well-defined given saturates and thus contains and intersects in exactly two edges. Moreover, if both contain and satisfy , then so does . To see this, notice that must contain and not , and if has an edge in , then it has at least two edges in because it is an -circuit. By submodularity of the cut-function, the number of edges of in is at most two, as required. It follows that is uniquely defined. Finally, we note that as deleting any vertex not contained in either or does not change how many boundary edges intersect .
We call an unused component of of degree one flexible if the unique circuit incident to in is also of degree one in the auxiliary graph.
Symmetrically, we call inflexible if has degree at least two. An important consequence of the former definition is that always intersects some other circuit in the packing whenever is flexible. We formalize this in the lemma below.
Lemma 2.2. Let be a 4-edge-connected Eulerian group-labeled graph, a vertex of , an -packing which saturates , and a flexible unused component of that is adjacent to in . Then there is some different from such that .
Proof. Consider the cut . Since this contains at most two edges in and is 4-edge-connected, there exists a trail in from to , internally disjoint from , that is edge-disjoint from . Consider the last oriented edge of with underlying edge and head contained in . The edge cannot lie in by definition, nor in because . Evidently, the edge cannot lie in a different unused component of , since in that case must either lie in implying that the degree of in is at least two, contradicting our assumptions, or lie in contrary to being a component. We conclude that there exists some other circuit such that and thus has a vertex in . □
Dually to the closure, we consider the notion of an ear decomposition of into . This is a sequence so that
for each , is a non-empty subtrail of that is edge-disjoint from with both ends in ; and
for each , the sequence can be reordered into a subtrail of .
Note that we allow each to be a circuit. We call the ears of this decomposition. We say that the ear decomposition is maximal if there is no trail so that is also an ear decomposition of into . The lemma below establishes that the notion of a maximal ear decomposition is dual to the closure.
Lemma 2.3. Let be a 4-edge-connected Eulerian group-labeled graph, a vertex of , an -packing saturating , and an unused component of of degree one adjacent to in . If is a maximal ear decomposition of into , then .
Proof. We first show that by induction on ; this holds for since by definition. Assuming , then since is a subtrail of which is disjoint from the previous ears, and contains at most two edges from , it must be that as needed. Indeed otherwise contains at least two edges in as well as the first and last edge of with an end in . Fix . By the previous paragraph, . Let be an ordering of the sequence such that is a subtrail of . If a vertex in occurs along before the beginning of , let be the subtrail of from the last such occurrence to the beginning of . Then is an ear decomposition of into violating our choice of a maximal ear decomposition. Similarly, if a vertex of occurs along strictly after the end of , we again get a contradiction to the maximality of our ear decomposition. We conclude that the occurrences of vertices of along form exactly the interval occupied by , and therefore . As , it follows that , completing the proof.
We note that while the above establishes that the underlying set of vertices in the maximal ear decomposition is unique, the number of ears or their order is not necessarily unique. However, this notion still gives rise to a meaningful way of measuring the complexity of unused components of degree one in an -packing, which we now define.
For a flexible unused component of adjacent to in , we let the rank of in , denoted by , be the minimum such that there is a maximal ear decomposition of into and some different from with the property that . For flexible unused components Lemmas 2.2 and 2.3 imply that such always exists, and also by definition . For an inflexible unused component of we define . Furthermore, we define the rank of , denoted by , to be the minimum of over all unused components of of degree one if there is at least one such component, and 0 otherwise.
We are now ready to proceed with the proof of the main theorem of this section which we repeat here for convenience.
Theorem 2.1. Let be a positive integer. Let be a group, let be a subgroup of , let be a -labeled Eulerian graph which is 4-edge-connected, and let be a vertex of such that there exists an -packing of size . Then there exists an -decomposition of size at least .
To briefly summarize the argument, under the theorem’s assumptions, we show there is an -packing with the property that every circuit has degree at most one and every unused component has degree at least two in . Consequently, this leads to a small number of unused components which can be greedily absorbed in the packing.
Proof of Theorem 2.1. We choose an -packing in subject to the following conditions, satisfied in the order listed below:
contains exactly many circuits and at least of these have labels outside of ;
the number of edges covered by is maximized;
the number of unused components of of degree at least two is maximized;
the rank of is minimized.
In general, any -circuit with group value not in which visits internally can be decomposed into two distinct -circuits, at least one of which has group value not in . Along with the fact that is Eulerian, we conclude that there exists an -packing which satisfies property 1 and, consequently, properties 1-4. The assumptions of Theorem 2.1 imply that there exists such a collection; we proceed to prove a few claims about its structure.
Claim: for all circuits with .
Proof: Let satisfy and assume for a contradiction that there is some unused component which shares a vertex with . Let be the circuit obtained by joining an Eulerian tour of to at a common vertex, and the collection obtained from by swapping with . It follows that still satisfies condition 1 while the number of edges covered by is now strictly larger; contradiction. It follows that for every with .
Claim: for all circuits with .
Proof: Fix some with , and assume for a contradiction that , i.e. there are two distinct unused components and which both share vertices with . Suppose
where the tail of is , the tail of is and , and the tail of is and . Let be an Eulerian circuit in starting and ending at , and likewise define . Consider the following elements of
and observe that
It follows that one of , , and must lie outside . We may therefore appropriately glue , , or both at to obtain a strictly bigger circuit with . By swapping and we obtain a new collection of circuits covering strictly more edges than before that still satisfies condition 1, giving rise to a contradiction once again. ■
Claim: for all unused components of .
Proof: By connectivity of , every unused component must have degree at least one. Assume for a contradiction that there is an unused component of degree one. First
note that by the two claims above any unused component of degree one is flexible. Let be such a component with the property that , i.e. its rank is minimal over all unused components of degree one. Let be the unique circuit of adjacent to in . By the first claim, we know that . Moreover, fix a maximal ear decomposition of into and distinct from with the property that . We shall construct a new -packing with the property that, either the number of unused components of degree at least two is strictly larger than that of , or it has the same number of unused components of degree at least two as but its rank is strictly smaller than that of ; both of these lead to a contradiction to the choice of .
Towards this goal, consider any vertex . First note that cannot be a vertex in as this would contradict the minimality of ; in particular, cannot be an endpoint of . Choose a pair of subtrails and by arbitrarily “breaking” at , i.e. non-empty subtrails of having as head and tail, respectively, and satisfying . Since is a subtrail of , we may also rewrite as , where is the subtrail from to containing and is a subtrail from to containing . Similarly, we let where is a subtrail of from to and is a subtrail of from to .
Next, we claim that at least one of the sets or has at least as many -circuits labeled outside as the collection .
Consider the following elements of
and observe that
and that
Since it follows that either or . Hence, if , the claimed property holds for one of the two sets or . On the other hand, if then at least one of the two factors in all four equations above must be outside and again the desired property holds through a simple checking of the cases.
Let us assume without loss of generality that the claim above holds for the set . We complete the proof by showing that the collection of -circuits obtained from by replacing circuits and with circuits and yields a contradiction to the choice of .
We first verify that the collection is at least as good as with respect to conditions 1, 2, and 3. Condition 1 is clearly satisfied given the previous claim. Moreover, the edges covered by are by definition precisely the same as the edges covered by , and so condition 2 is also satisfied. Consider an unused component of of degree at least two. Any adjacency to a circuit other than and is also present in , and cannot meet since otherwise . If meets , then also meets at least one of or . We conclude is of degree at least two in and condition 3 holds for .
There are now two cases to distinguish.
Both and intersect : By definition, this means that the degree of in is two. Combined with the observations above, this implies that strictly improves on condition 3 over which gives us the desired contradiction.
Only one of and intersects : By assumption, has degree exactly one in . Since satisfies conditions 1–3, the first two claims hold for as well and we see that the unique circuit meeting has degree one in and label not in . Thus, is flexible and its rank is finite. In this case it must be that is at least two. Indeed, if , then by definition of ear decompositions, the endpoint of each for that is not is a vertex of . Therefore by construction both and would intersect , contrary to our assumption.
Now, without loss of generality assume that . Let be the subtrail of obtained from concatenating the ears in the appropriate order. Note that, since , is non-empty. Additionally, by our assumptions, implying in particular that is either a subtrail of , or a subtrail of . Moreover, while , implying that is in fact a subtrail of , and so in particular a subtrail of . As such, is a valid ear decomposition of into . Let be the endpoint of other than . By the definition of an ear, . Since and , we have . Given that every ear decomposition can be trivially extended to a maximal ear decomposition, it follows that the -circuit witnesses that the rank of in is at most . In particular, the rank of is strictly smaller than that of , a contradiction completing the proof of the claim.
Let be the number of circuits of the packing with label not in , and let be the number of unused components. The claims imply . Choose for each unused component one incident circuit; these chosen circuits are distinct and all have labels not in . Insert an Euler tour of each unused component into its assigned circuit. Concatenate the resulting circuits and all circuits of the original packing labeled in , at , to form a single circuit , provided the collection is non-empty. The other circuits together with cover every edge of . If is absent, the unchanged circuits already form the required decomposition. If is present and is not in , keep the circuit . Otherwise concatenate at with one of the unchanged circuits; the resulting circuit has label not in . In every case, the resulting decomposition has at least circuits.
Making an immersion near-full
We first discuss the “universal” group-labeled graphs which we look for as (near-full) immersions.
For positive integers and , we define the -flower to be the graph on vertices so that for each , there are parallel edges between and . We call the center vertex of the flower. If is an immersion of a flower into a graph , then we call the branch vertex of corresponding to the center of the flower the branch center. A petal is a subgraph of the flower consisting of , some , and the parallel edges between them. Note that if is a graph on vertices where each vertex has degree at most , then the -flower admits as an immersion; we map to , and then we greedily map to two-edge walks of the flower.
Let be a finite group. The -rich flower is the -labeled graph where the graph is the -flower and, for all and , there exist oriented edges from to with label . Note that if is a -labeled graph on vertices where each vertex has degree at most , then the -rich flower admits as an immersion. To see this, first map to as before. Then select one arbitrary orientation of each edge of , and map to a two-edge trail which begins with an edge labeled by the identity and oriented towards the center, and ends with a -labeled edge oriented away from the center.
The goal of this section is to prove the following theorem which essentially allows us to reduce the question of finding large rich flowers as near-full immersions in 4-edge-connected Eulerian group-labeled graphs to finding (even larger) rich flowers as immersions.
Theorem 3.1. Let be a finite group and and be positive integers. Let and be integers such that and . Suppose is a 4-edge-connected Eulerian -labeled graph such that there exists an immersion of a -rich flower with center in . Then there exists an -near-full immersion of a -rich flower with center in . Moreover, if and are the sets of branch vertices of and , respectively, then , and, specifically, .
The main technical difficulty is the following lemma, which is used to “disentangle” an -decomposition from a flower immersion.
Lemma 3.2. Fix an integer . Let be a finite group, let be a proper subgroup of , and let be a 4-edge-connected Eulerian -labeled graph. Suppose that contains an -near-full immersion of a -labeled Eulerian graph where has every edge incident to a single vertex . Let be an accommodating labeling of the immersion. Furthermore, suppose that contains an -decomposition of size at least . Then has an -near-full immersion of a graph obtained from by deleting at most edges and adding loops at with label outside .
Proof. For the duration of the proof, labels refer to the fixed shifting of . We first extend the -near-full immersion to a full immersion of the graph obtained from by possibly adding a single loop at with the appropriate -label (if the -near-full is in fact a full immersion, then we do not add ). For notational convenience we will assume . We partition into circuits each beginning and ending at such that
at least of them have label outside , and
the size of the symmetric difference of transitions of and transitions of is minimized.
We note that we minimize transitions with respect to only after extending it to a full immersion. Some choice of exists because contains an -decomposition of size at least . Order the circuits such that have label outside , and have label in for some . We partition into and .
We claim that for any branch trail of , either every edge of is contained in or every edge of is contained in . Suppose otherwise, and let be a pair of edges in such that is a transition of and is in a circuit , is in a circuit , and exactly one of is in . By possibly reversing the orientation of we may assume and , and similarly we may orient such that is in and is in . Let such that is the last edge of , and let such that is the first edge of , where possibly or is empty. If both are empty, consider removing and from and adding . This circuit has label , so the same number of circuits in the new collection are labeled outside . Furthermore this adds the transition to the collection, contradicting the choice of .
Hence we may assume one of is nonempty. Consider replacing in by the circuits . Note that this adds the transition to the collection while only removing transitions which do not appear in . Thus is a better choice of circuits unless . However because this would imply
a contradiction. This completes the proof that every trail of has all edges entirely contained in one of .
We now claim that there are at most circuits with label outside in , that is, . Suppose for a contradiction that . First, we observe that every branch trail of has all its edges in a single circuit of . If not, some branch trail has a transition whose edges belong to distinct circuits and . Reconnecting these circuits as above adds this transition and removes only transitions not belonging to . The resulting collection still contains at least circuits with label outside , contradicting the choice of .
Choose a circuit with label outside which does not contain any edge of , if is defined. Let be the subgraph of consisting of the edges whose branch trails have their edges in . Since the extended immersion is full, these branch trails partition . By construction, every vertex of has even degree. Moreover, every edge of is incident with , so we conclude that is connected and has an Eulerian tour beginning and ending at .
Following this Eulerian tour through the corresponding branch trails gives a circuit beginning and ending at with but possibly changing the order and orientation of the edges of . Every edge of has label in , and hence . Furthermore, contains every transition of on these edges. The circuit must omit at least one such transition, as otherwise it would itself be a concatenation of complete branch trails, possibly reversed, and would therefore have label in , which is not the case. Since and have the same number of transitions, it follows that replacing by strictly decreases the symmetric difference with the transitions of . This replacement leaves circuits with label outside , again contradicting the choice of . We conclude that .
Hence there are at most circuits in with label outside . Let be the subgraph of which includes only edges whose corresponding trails are contained in . We claim that is formed from by deleting at most edges. Let be the set of edges incident to , including loops, which appear as the first or last edge of a branch trail of beginning or ending at , respectively. We will show that for any circuit with , contains at most two edges in . This implies the claim as follows. Note that as every edge in is incident to , every branch trail of contains some edge in . Then an edge is in if and only if contains an edge of . Thus , proving the claim.
Suppose to reach a contradiction that a circuit for contains at least three edges in . Choose one of these edges which is neither the first nor the last edge of , and consider its end at where its branch trail begins or ends. This end occurs at an internal visit of to , giving a transition with the head of and the tail of equal to . Since the chosen end is an end of a branch trail, this transition does not belong to . Let where the last edge of is and the first edge of is . Note that , so one of these circuits has label outside . Then we can modify by replacing with the two circuits to contradict the choice of to minimize the symmetric difference with the transitions of .
We then find the desired -near-full immersion as follows. On we take the circuits as immersions of loops, and on we take restricted to .
This accounts for all edges except possibly edges of if and edges of if it exists and its branch trail lies in . Each such subset of edges, if it is nonempty, forms a circuit through , and we conclude that the -near-full immersion exists as claimed, completing the proof. □
The near-full conclusion in the statement of the lemma is necessary in general. Already for and , the total label of determines the parity of , and may force rather than .
We need one more type of flower in order to build up to rich flowers. We say that a -labeled graph is a -generating flower if there exists a generating set for so that , the graph is an -flower, and for all and , there exist oriented edges from to with label . We call the generator.
Our main strategy will be to start with a flower with every edge labeled by the identity, and grow generating flowers for larger and larger subgroups until we have a rich flower. Hence we need the following two lemmas, which give the starting and ending point of the process.
The first is a Ramsey-type lemma for flowers in group-labeled graphs.
Lemma 3.3 ([11]). Let be a finite group, let and be positive integers, and let be a -labeled graph so that is a -flower with center . Then there is an -near-full immersion of the -rich flower with center into and the peripheral branch vertices are precisely the peripheral vertices of .
The second lemma shows that for large enough , every -generating flower is “universal”.
Lemma 3.4 ([11]). Let be a finite group and and be positive integers. Then any -generating flower with center admits an -near-full immersion of the -rich flower with center mapping its peripheral branch vertices bijectively to the peripheral vertices of .
The above lemmas, as originally stated in [11] as lemmas 4.2 and 4.1, respectively, do not specify the branch vertices beyond the center vertex of the star and do not specify that the immersion is -nearly full. The stronger statements above follow immediately from the proofs in [11] and we omit the derivation here.
We are now ready to prove the main result which we repeat here for convenience.
Theorem 3.1. Let be a finite group and and be positive integers. Let and be integers such that and . Suppose is a 4-edge-connected Eulerian -labeled graph such that there exists an immersion of a -rich flower with center in . Then there exists an -near-full immersion of a -rich flower with center in . Moreover, if and are the sets of branch vertices of and , respectively, then and, specifically, .
Proof. By possibly decreasing by one, we assume is even with . Let be the branch center of the -rich flower immersion. Consider arbitrarily extending this to a full immersion, so has a full immersion of the -flower with branch center and arbitrary labels. By Lemma 3.3, this immerses the -rich flower with branch center . Because every edge of the rich flower is incident to , this is in fact an -near-full immersion.
Thus by Observation 1.1, has an -near-full immersion of the -rich flower with branch center . Note also that for any proper subgroup of , and any shifting of , has an -packing of size . This holds because the original rich flower has such a packing for every proper subgroup, and shifting simultaneously conjugates the labels of all circuits based at .
We now find a -generating flower as an -near-full immersion in whose branch vertices belong to and whose center maps to , such that
is a subgroup of ,
is even with ,
, and
subject to the above, is as large as possible.
Note that some choice exists by taking the -rich flower. We now claim that such a choice must have . If this holds, then we have a -generating flower as an -near-full immersion. We then apply Lemma 3.4 and Observation 1.1 to obtain a -rich flower as an -near-full immersion in , with branch vertices contained in and branch center , as required.
Suppose to reach a contradiction that is an -near-full immersion of a -generating flower for a proper subgroup of . Note that because is even, is Eulerian. Let be an even integer such that , and let . Note that because and , we have . Hence , so such a choice of exists.
Let be an accommodating labeling for . By the preceding observation, contains an -packing of size . By Theorem 2.1, therefore contains an -decomposition of size at least . By Lemma 3.2, contains an -near-full immersion of a graph obtained from by deleting at most edges and adding loops at with label outside . We then delete the petals which had the most edges deleted. If is odd, we discard one additional petal so that exactly petals remain. Each remaining petal had at most edges deleted. By possibly ignoring some branch trails of the immersion (and utilizing Observation 1.1), we see that has an -near-full immersion of the graph obtained from the -generating flower by adding loops at with label outside . We then take of these loops which have the same label . Let be the subgroup generated by . By sacrificing trails with identity label on each petal, we obtain an -near-full immersion of the -generating flower with branch center . Because is a proper subgroup of , is an integer, and hence at least 2. Thus
Therefore this immersion contradicts the choice of .
Theorem 1.2, which we restate for convenience, now follows easily.
Theorem 1.2. Let be a finite group. For every -labeled graph there exists a -labeled graph such that for every Eulerian 4-edge-connected -labeled graph and for every vertex , if contains as an immersion, then contains as an -near-full immersion.
Proof. Fix a vertex . Let and . Let be the -rich flower.
There is an immersion of into mapping to the center of such that every unused edge of is incident with its center, making an -near-full immersion.
Choose and satisfying the bounds in Theorem 3.1, and let be the -rich flower. We claim is the desired -labeled graph. Suppose that is Eulerian and 4-edge-connected and contains as an immersion. By Theorem 3.1, contains as a near-full immersion at its center. Composing this immersion with and applying Observation 1.1 gives an -near-full immersion of in , as required.
Extending a near-full immersion
In this section we discuss under what conditions the near-full immersion in Theorem 1.2 can be replaced by a full immersion. This cannot always be the case: suppose that and are Eulerian graphs labeled over for some such that the sum of all edge weights in is different from the sum of all edge weights in (note that orientation doesn’t matter because every element is its own inverse and the group is abelian, so this sum is well defined). Moreover, the sum is invariant under shifting: shifting at a vertex changes the total by the vertex’s degree times the shifting element, which is always zero because the graph is Eulerian. Then it cannot be that contains as a full immersion, even though can contain arbitrary group labeled immersions. It turns out that this is in some sense the only restriction.
We first need some notions from group theory. The commutator subgroup of a group , denoted , is the subgroup generated by all the commutators, that is, all elements of the form for . It is well known that is a normal subgroup and that is abelian; in fact, for any normal subgroup of , is abelian if and only if contains the commutator subgroup. We denote by the set . We note that is a subgroup of . To see this, modulo the group is abelian, so the product of two squares is a square and the inverse of a square is a square, implying is a subgroup. Since it contains , it is normal as well. Finally, we note that if is a finite group then is isomorphic to for some ; the group is abelian and every element squares to the identity.
Theorem 4.1. Let be a finite group. For every Eulerian -labeled graph with at least one edge there exists a -labeled graph such that for any 4-edge-connected Eulerian -labeled graph with no full immersion, one of the following holds.
There exists a normal subgroup of such that is isomorphic to for some , and over this quotient labeling the sum of the edge labels in is different than that of .
does not contain as an immersion.
We note as before that in the first option, the sum over the labeling of all edges of is well defined because the quotient group is isomorphic to . Since is Eulerian, this sum is also invariant under shifting. In fact, in option 1 we may take . It is not hard to see that for any Eulerian -labeled graphs and such that option 1 holds, does not contain as a full immersion.
Proof of Theorem 4.1. Fix an arbitrary vertex incident with an edge of and consider the -labeled graph obtained from by adding loops of label at , for each . Applying Theorem 1.2 to yields a -labeled graph such that, if contains as an immersion, then contains as an -near-full immersion. If does not contain as an immersion we immediately conclude. We may therefore assume that contains an -near-full immersion of . For simplicity we also assume that . Fix an accommodating labeling for , and use this labeling for all circuit and trail labels below. Since is Eulerian, shifting does not change its total label in any elementary abelian 2-group quotient. Thus if outcome 1 holds for the labeling it holds as well for the original labeling.
If there are unused edges, let be an Eulerian circuit of their unique non-trivial component, starting and ending at , and fix . If there are no unused edges, let and omit from the concatenations below. Assume to reach a contradiction that option 1 does not hold. Our goal is to concatenate , if present, with the branch trails of corresponding to the added loops, in such a way that the product of all the labels is the identity; in this case we are done, as we may discard the branch trails of corresponding to the added loops, obtaining an -near-full immersion of in the process, append the discarded branch trails to , if present, in a way that gives us a circuit starting and ending at and labeled by the identity, and then append to any branch trail of corresponding to an edge of incident with in order to obtain as a full immersion.
Indeed, assuming outcome 1 does not hold, it must in particular not hold with respect to . Over this quotient, the sum of the labels of the edges in the branch trails of equals the total label of , and hence that of . Moreover, the total label of the branch trails corresponding to the added loops is the identity, since each label occurs an even number of times. Consequently, the image of in is the identity, and therefore .
Let . The subgroup generated by all squares is normal, and its quotient has every element of order at most two, so that quotient is abelian. Thus this subgroup contains , and consequently equals . Since the squares generate , we may write for some , where because a shortest such expression has distinct partial products. If , we take . For each , select two previously unused branch trails of corresponding to added loops of label , and orient both to have label under . There are sufficient copies, since we use at most copies of any label. Concatenating these trails in the specified order gives label . For each label, an even number of its added loops remain unused. Pair these loops, and for each pair traverse one corresponding branch trail in its prescribed orientation and the other in reverse, so that the pair contributes the identity. Concatenate , if present, with the selected trails and then these remaining pairs. The resulting circuit begins and ends at , contains every residual edge and every edge of the added-loop branch trails exactly once, and has label , as desired.
We conclude with the proof of Theorem 1.4, which we restate here.
Theorem 1.4. Let be a finite group. For every Eulerian -labeled graph with at least one edge, there exists a positive integer such that the following holds. Let be a 4-edge-connected Eulerian -labeled graph with no full immersion. Then one of the following holds.
There exists a normal subgroup of such that is isomorphic to for some nonnegative integer , and over this quotient labeling the sum of the edge labels in differs from that in .
There exist a shifting of and a tree-cut decomposition of such that for every bag , at least one of the following holds.
(a) There are at most vertices in the torso of of degree greater than , and none of them are the new vertices of the torso.
(b) There exists such that is a certificate for of value at most .
Proof of Theorem 1.4. Fix and , and let be the graph supplied by Theorem 4.1. Let , and fix a positive integer such that every vertex of is incident to at most edges. Let
In particular, .
Let be a 4-edge-connected Eulerian -labeled graph with no full immersion. If the first outcome of Theorem 4.1 holds, then the first outcome of Theorem 1.4 holds as well. Thus we may assume that does not contain as an immersion. Theorem 1.3 gives a shifting of and a tree-cut decomposition of satisfying the second outcome of Theorem 1.4, completing the proof. □
Declaration of AI use
ChatGPT-6 Astra was used in proofreading and editing the final manuscript, identifying a number of typos as well as mathematical issues in the proof of Theorem 4.1 and Lemma 3.2.
References
- [1]D. I. Bernstein. Generic symmetry-forced infinitesimal rigidity: Translations and rotations. SIAM Journal on Applied Algebra and Geometry, 6(2):190 – 215, 2022.arxiv.org/abs/2003.10529
- [2]A. Bouchet. Caractérisation des symboles croisés de genre nul. Comptes Rendus de l’Académie des Sciences de Paris, Séries A-B, 274:A724–A727, 1972.
- [3]A. Bouchet. Circle graph obstructions. Journal of Combinatorial Theory, Series B, 60(1):107–144, 1994.DOI
- [4]M. DeVos, J. McDonald, B. Mohar, and D. Scheide. A note on forbidding clique immersions. The Electronic Journal of Combinatorics, 20(3):P55, 2013.arxiv.org/abs/1207.2117
- [5]J. Geelen, B. Gerards, and G. Whittle. Solving Rota’s conjecture. Notices Amer. Math. Soc., 61(7):736–743, 2014.DOI
- [6]J. Geelen, O.-j. Kwon, R. McCarty, and P. Wollan. The grid theorem for vertex-minors. Journal of Combinatorial Theory, Series B, 158:93 – 116, 2023.
- [7]A. M. H. Gerards. On Tutte’s characterization of graphic matroids—a graphic proof. J. Graph Theory, 20(3):351–359, 1995.
- [8]J. L. Gross. Voltage graphs. Discrete Mathematics, 9(3):239–246, 1974.
- [9]J. L. Gross and T. W. Tucker. Generating all graph coverings by permutation voltage assignments. Discrete Mathematics, 18(3):273–283, 1977.DOI
- [10]V. E. Kaszanitzky, B. Schulze, and S.-i. Tanigawa. Global rigidity of periodic graphs under fixed-lattice representations. Journal of Combinatorial Theory. Series B, 146:176 – 218, 2021.arxiv.org/abs/1612.01379
- [11]R. McCarty, C. McFarland, and P. Wollan. The structure of group-labeled graphs forbidding an immersion. arXiv preprint arXiv:2603.08820, 2026.arxiv.org/abs/2603.08820
- [12]C. S. J. A. Nash-Williams. On well-quasi-ordering trees. In M. Fiedler, editor, Theory of Graphs and Its Applications (Proceedings of the Symposium, Smolenice, 1963), pages 83–84, Prague, 1964. Publishing House of the Czechoslovak Academy of Sciences.
- [13]P. Nelson and Z. Walsh. The extremal function for excluding geometry minors over prime fields. SIAM J. Discrete Math., 36(3):2100–2120, 2022.DOI
- [14]J. Paat, I. Stallknecht, Z. Walsh, and L. Xu. On the column number and forbidden submatrices for Δ-modular matrices. SIAM J. Discrete Math., 38(1):1–18, 2024.arxiv.org/abs/2212.03819
- [15]R. C. Read and P. Rosenstiehl. On the Gauss crossing problem. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloquia Mathematica Societatis János Bolyai, pages 843–876. North-Holland, Amsterdam–New York, 1978.
- [16]N. Robertson and P. Seymour. Graph minors XXIII. Nash-Williams’ immersion conjecture. Journal of Combinatorial Theory, Series B, 100(2):181–205, 2010.
- [17]P. Seymour. On Tutte’s characterization of graphic matroids. Ann. Discrete Math., 8:83–90, 1980.DOI
- [18]S.-i. Tanigawa. Matroids of gain graphs in applied discrete geometry. Trans. Amer. Math. Soc., 367(12):8597–8641, 2015.arxiv.org/abs/1207.3601
- [19]P. Wollan. The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47–66, 2015.arxiv.org/abs/1302.3867