Partial automorphisms and level of symmetry of asymmetric graphs Valter Cingel1 , Tatiana Jajcayová1 and Ján Pastorek1,* 1 Faculty of Mathematics, Physics and Informatics Comenius University, Bratislava, Slovakia Abstract Most graphs are asymmetric, i.e. they lack any nontrivial automorphisms. Even in the case of highly symmetric graphs, removing just a single vertex from a graphical regular representation may result in a graph with a trivial automorphism group. Nevertheless, asymmetric graphs can still contain relatively large induced subgraphs which do admit nontrivial automorphisms or relatively large distinct but isomorphic induced subgraphs. Such symmetric local structures play a crucial role in Babai’s quasipolynomial algorithm for solving the Graph Isomorphism Problem. These observations called for the use of the concept of a partial automorphism of a graph Γ, which is either an isomorphism between two distinct induced subgraphs of Γ or an automorphism of one of its induced subgraphs. Based on the concept of a partial automorphism, the symmetry level of a graph Γ is defined as the ratio between the largest order of the domain of a nontrivial partial automorphism of Γ and the graph’s order |𝑉 (Γ)|. In our paper, we address several open questions concerning the symmetry levels of graphs posted by Cingel, Gál & Jajcayová (2023), and derive additional results using both computer aided and theoretical methods. We improve the best previously known lower bound for the symmetry levels of general graphs by proving that the symmetry level of any finite simple graph is at least 12 . In case of disconnected graphs without a unique isolated vertex, we prove that the symmetry level of such graphs is at least 34 . Furthermore, we present graphs that provide an answer to Question 3 posted by Cingel, Gál & Jajcayová by showing that higher symmetry level does not necessarily imply a larger number of partial automorphisms. We take the initial steps toward answering the main question of Cingel, Gál & Jajcayová. Finally, we discuss the relation between a measure of asymmetry introduced by Erdős & Rényi (1963) and the level of symmetry of graphs considered in our paper. Keywords symmetry of graphs, asymmetric graphs, partial automorphisms, graphs with small symmetry levels 1. Introduction study of partial automorphisms of graphs [6] and the related concept of the level of symmetry of graphs de- Almost all graphs are known to be asymmetric [4], fined using the order of the largest domain of a nontrivial i.e., having no nontrivial ‘global’ automorphisms. At the partial automorphism of a graph [3]. In the absence of a same time, all of them contain local symmetries. These universally accepted name, we call a graph that possesses observations remain true even if one restricts the graphs at least one nontrivial automorphism as non-asymmetric. considered to the class of regular graphs, which is the The following definitions introduce two fundamental class containing some of the most symmetric graphs - the concepts used throughout our paper. vertex-transitive graphs [8]. Taking the opposite point of view, deleting a single vertex from a (vertex-transitive) Definition 1.1 (Partial automorphism). Let Γ be a graph, graphical regular representation of odd order leads to an and let 𝐷 and 𝑅 be non-empty subsets of the vertex set asymmetric graph. It is important to note, however, that 𝑉 (Γ) of equal cardinalities. A partial automorphism 𝜙 : the distorted graph obtained this way still has many in- 𝐷 → 𝑅 is an isomorphism between the induced subgraphs duced subgraphs with nontrivial partial automorphisms Γ[𝐷] and Γ[𝑅]; where the rank of 𝜙 is the cardinality [7], which suggests that the line between symmetric and |𝐷| = |𝑅|. We say that a partial automorphism is non- asymmetric objects is surprisingly thin. Furthermore, trivial if it maps at least one vertex in 𝐷 to another (distinct) local structures exhibiting high levels of symmetry are vertex in 𝑅. of significant importance in Babai’s quasipolynomial al- Definition 1.2 (Symmetry level). Let Γ be a graph of gorithm for solving the Graph Isomorphism Problem [1]. order 𝑛 ≥ 2, and let 𝑘 be the largest postive integer for These observations provide the motivation behind the which Γ admits a nontrivial partial automorphism 𝜙 of rank 𝑘. The symmetry level of Γ is the ratio 𝑆(Γ) := 𝑛𝑘 . ITAT’24: Computational Aspects of Large-Scale Problems in Discrete Mathematics, September 20–24, 2024, Drienica, Slovakia The set of all partial automorphisms, denoted * Corresponding author. PAut(Γ), along with the operations of partial composi- $ cingel13@uniba.sk (V. Cingel); tatiana.jajcayova@fmph.uniba.s (T. Jajcayová); jan.pastorek@fmph.uniba.sk (J. Pastorek) tion and partial inverse of partial maps, forms an inverse © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License monoid, which was fully characterized for graphs by Ja- Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) jcay et al. in [6]. Some of the basic results concerning CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings partial automorphisms can be found in [5, 3, 2, 9]. Next, we use the following∑︀fact observed already in Erdős & Rényi [4]. The sum 1≤𝑖<𝑗≤𝑛 ∆𝑖𝑗 is equal to the number of ordered triples (𝑣𝑖 , 𝑣𝑗 , 𝑣𝑙 ) of vertices in Γ such 2. Addressing open questions of that Γ contains the edge {𝑣𝑖 , 𝑣𝑙 } but does not contain Cingel, Gál & Jajcayová {𝑣𝑗 , 𝑣𝑙 }, 1 ≤ 𝑖 ̸= 𝑗 ≤ 𝑛. Note that each of such triples consists of a vertex 𝑣𝑙 together with one of its neighbors In the article [3], the authors posed several questions and one of its ‘non-neighbors’. This implies that the we will address (and possibly answer) in this section. number of such triples containing 𝑣𝑙 is equal to 𝑛𝑙 (𝑛 − 1 − 𝑛𝑙 ). Hence, 2.1. Minimal level of symmetry ∑︁ 𝑛 ∑︁ Question 1 ([3]). What is the minimal level of symmetry ∆𝑖𝑗 = 𝑛𝑙 (𝑛 − 1 − 𝑛𝑙 ), (3) 1≤𝑖<𝑗≤𝑛 𝑙=1 of a graph Γ of order 𝑛 as a function of 𝑛? Although we will not settle Question 1, in what follows, and therefore log√2 𝑛 we improve the lower bound 𝑆(Γ) ≥ stated in ∑︀𝑛 2 𝑙=1 𝑛𝑙 (𝑛 − 1 − 𝑛𝑙 ) 𝑛 [3] for graphs of order 𝑛. Let Γ be a finite simple graph 𝑆(Γ) ≥ 1 − . (4) 𝑛2 (𝑛 − 1) of order 𝑛 ≥ 2, 𝑉 (Γ) = {𝑢1 , 𝑢2 , . . . , 𝑢𝑛 }, let 𝑢𝑖 and 𝑢𝑗 be two distinct vertices of Γ, and let 𝜙 be the partial Taking advantage of another simple algebraic identity map mapping the subset of vertices of 𝑉 (Γ) not con- used in Erdős & Rényi: tained in the symmetric difference of the neighborhoods (︂ )︂2 𝑁Γ (𝑢𝑖 )△𝑁Γ (𝑢𝑗 ) of 𝑢𝑖 and 𝑢𝑗 in Γ onto itself by swap- 𝑛−1 2 𝑛−1 𝑛𝑙 (𝑛 − 1 − 𝑛𝑙 ) = ( ) − 𝑛𝑙 − , ping 𝑢𝑖 and 𝑢𝑗 , 𝜙(𝑢𝑖 ) = 𝑢𝑗 and 𝜙(𝑢𝑗 ) = 𝑢𝑖 , and fixing 2 2 all vertices of Γ distinct from 𝑢𝑖 and 𝑢𝑗 and not contained in the symmetric difference 𝑁Γ (𝑢𝑖 )△𝑁Γ (𝑢𝑗 ), 𝜙(𝑢𝑙 ) = we obtain 𝑢𝑙 , for all 𝑢𝑙 ∈ 𝑉 (Γ) − (𝑁Γ (𝑢𝑖 )△𝑁Γ (𝑢𝑗 )) − {𝑢𝑖 , 𝑢𝑗 }. ∑︀𝑛 𝑛−1 2 )︀2 ) − 𝑛𝑙 − 𝑛−1 (︀ 2 𝑙=1 ( It is easy to see that 𝜙 is a partial automorphism of Γ of 𝑆(Γ) ≥ 1 − 2 2 ≥ rank |𝑉 (Γ) − (𝑁Γ (𝑢𝑖 )△𝑁Γ (𝑢𝑗 ))|. Denoting the cardi- 𝑛2 (𝑛 − 1) 2 nality of the symmetric difference of the neighbourhoods 𝑛 (𝑛−1) ∑︀𝑛 𝑛−1 2 2 𝑙=1 ( 2 ) 2 𝑛−1 of 𝑢𝑖 and 𝑢𝑗 by ∆𝑗𝑘 allows us now to derive the first 1− =1− =1− ≥ 𝑛2 (𝑛 − 1) 𝑛2 (𝑛 − 1) 2𝑛 (and in some sense, the most general) lower bound on the symmetry level of Γ that will serve as the basis of 1 . our forthcoming arguments: 2 𝑛 − min{∆𝑖𝑗 } min{∆𝑖𝑗 } 𝑆(Γ) ≥ =1− , (1) 𝑛 𝑛 In order to obtain another formulation of Theorem 2.1, where the minimum is taken over all pairs of distinct let 𝑛𝑖 denote the degree of the 𝑖-th vertex of Γ, and let vertices 𝑢𝑖 , 𝑢𝑗 ∈ 𝑉 (Γ). 𝑛𝑖𝑗 denote the cardinality of 𝑁Γ (𝑢𝑖 ) ∩ 𝑁Γ (𝑢𝑗 ), the set Using the notation introduced above and mimicking a of shared neighbors of 𝑢𝑖 and 𝑢𝑗 . Using this notation, it proof from [4] yields now the following. is easy to see that Theorem 2.1. For any simple graph Γ of order 𝑛 ≥ 2, ∆𝑖𝑗 = 𝑛𝑖 + 𝑛𝑗 − 2𝑛𝑖𝑗 − 2𝛿𝑖𝑗 , (5) 𝑛−1 1 for all 1 ≤ 𝑖 ̸= 𝑗 ≤ 𝑛, where 𝛿𝑖𝑗 = 1 if 𝑢𝑖 and 𝑢𝑗 are 𝑆(Γ) ≥ 1 − > . 2𝑛 2 distinct and adjacent, and 𝛿𝑖𝑗 = 0 otherwise. Then, Proof. Let Γ be a simple graph of order 𝑛. Using inequal- ∑︁ ∆𝑖𝑗 = ity (1) together with the obvious fact that 1≤𝑖<𝑗≤𝑛 ∑︀ ∑︁ ∑︁ ∑︁ 1≤𝑖<𝑗≤𝑛 ∆𝑖𝑗 (𝑛𝑖 + 𝑛𝑗 ) − 2 · 𝑛𝑖𝑗 − 2 · 𝛿𝑖𝑗 ≤ min {∆𝑖𝑗 } ≤ avg {∆𝑖𝑗 } = 𝑛(𝑛−1) , 1≤𝑖<𝑗≤𝑛 1≤𝑖<𝑗≤𝑛 1≤𝑖<𝑗≤𝑛 1≤𝑖<𝑗≤𝑛 1≤𝑖<𝑗≤𝑛 2 (︃ )︃ 𝑛 𝑛 ∑︁ 𝑛𝑙 ∑︁ yields ∑︀ 4𝑛𝑠 − 2 2 − 2𝑠 = (4𝑛 − 2)𝑠 − 𝑛𝑙 (𝑛𝑙 − 1) = 2 1≤𝑖<𝑗≤𝑛 ∆𝑖𝑗 𝑙=1 𝑙=1 𝑆(Γ) ≥ 1 − . (2) 𝑛2 (𝑛 − 1) two vertices and fixing all vertices not belonging to the 𝑛 𝑛 symmetric difference of their neighborhoods. In the re- maining 15% of the asymmetric graphs, all graphs were ∑︁ ∑︁ (4𝑛 − 2)𝑠 − (𝑛2𝑙 − 𝑛𝑙 ) = 4𝑛𝑠 − 𝑛2𝑙 , (6) 𝑙=1 𝑙=1 of order 10. In this subset of graphs, almost all graphs have the largest nontrivial partial automorphism of rank where 𝑠 is the size (the number of edges) of Γ. Based on (𝑛 − min{∆𝑗𝑘 }) + 1 = 𝑛 − 1, which exceeds the rank the above, we obtain the following corollary. predicted by the lower bound by 1, i.e., it is the closest possible to the considered lower bound. Moreover, the Corollary 2.2. For any simple graph Γ of order 𝑛 ≥ 2 majority of these graphs have only few nontrivial par- and size 𝑠, tial automorphisms of the maximal rank 𝑛 − 1, most of 8𝑛𝑠 − 2 𝑛 ∑︀ 2 which swap only two vertices. Finally, there were also 𝑙=1 𝑛𝑙 𝑆(Γ) ≥ 1 − . tens of graphs in which the largest rank of a nontrivial 𝑛 (𝑛 − 1) 2 automorphism exceeds the lower bound by 2 and is equal Proof. Returning to the inequality (2) and substituting to 𝑛 − min{∆𝑗𝑘 } + 2 = 𝑛 − 1. For one such example, the identity (6) yields the desired result. see Figure 2. Revisiting the more precise (1), we note that com- puter searches we have conducted yielded many asym- metric graphs of order 𝑛 and symmetry level 𝑆(Γ) = min{Δ𝑖𝑗 } 1− 𝑛 , i.e., graphs whose symmetry level matches the lower bound in (1). On the other hand, despite consid- erable computational effort, we have not found a graph with symmetry level close to 12 . In his 2023 master thesis [5], Gál found graphs of order 14 and symmetry level equal to 57 . In our own investigation, we have found dis- tinct graphs of the same order and the same symmetry level. We present one such graph Γ in Figure 1, for which 𝑆(Γ) = 57 matches the lower bound from (1). Figure 2: Graph in which min{Δ𝑗𝑘 } = 3 but there is a 𝑗̸=𝑘 nontrivial partial automorphism of rank 𝑛 − 1 which can be obtained by deleting the red vertex and acts on the remaining vertices. To complete the section, let us consider the special case of 𝑘-regular graphs. Inequality (4) applied to 𝑘-regular graphs of order 𝑛 yields 2 𝑛 ∑︀ 𝑙=1 𝑘(𝑛 − 1 − 𝑘) 2𝑛𝑘(𝑛 − 1 − 𝑘) 𝑆(Γ) ≥ 1− = 1− . Figure 1: Graph Γ with 14 vertices and symmetry level 𝑛2 (𝑛 − 1) 𝑛2 (𝑛 − 1) 𝑆(Γ) = 57 . Thus, for any fixed 𝑘 ≥ 1, and any infinite family of 𝑘-regular graphs Γ: Note that the lower bound in (1) can be computed in 𝑂(𝑛2 𝐾) time, where 𝐾 is the maximum degree in the lim 𝑆(Γ) = 1. |𝑉 (Γ)|→∞ graph. Computationally testing the relation between the lower bound in (1) and the true symmetry level of all In case of unbounded 𝑘 proportional to the order 𝑛 of graphs of order at most 10, we have learned that only the 𝑘-regular graph, 𝑘 = 𝑛 , we obtain for any infinite 𝑝 1210694 8110708 ≈ 15% of all asymmetric graphs up to the or- family of 𝑛 -regular graphs 𝑝 der 𝑛 = 10 have symmetry levels exceeding the lower min{Δ𝑖𝑗 } bound 1 − . This means that for most asym- 2 𝑛 ∑︀ 𝑙=1 𝑘(𝑛 − 1 − 𝑘) (︂ )︂ 𝑛 metric graphs of order not exceeding 10, a partial auto- lim 1 − = 𝑛→∞ 𝑛2 (𝑛 − 1) morphism of maximal rank can be obtained by swapping (︃ ∑︀𝑛 𝑛 𝑛 )︃ 2 𝑙=1 𝑝 (𝑛 − 1 − 𝑝 ) corresponding monoids for all pairs of members of the = lim 1− = 𝑛→∞ 𝑛 (𝑛 − 1) 2 infinite family. (︂ )︂ 2(𝑛(𝑝 − 1) − 𝑝) Conjecture 2.3. The order of the inverse monoid of partial = lim 1 − = 𝑛→∞ (𝑛 − 1)𝑝2 automorphisms of the graph with a smaller symmetry level 2 (𝑛𝑝 − 𝑛 − 𝑝) is larger than that of the graph of the symmetry level 1 for = 1 − 2 lim = each pair of graphs constructed in the above described way 𝑝 𝑛→∞ (𝑛 − 1) 1 from the pair in Figure 3. 2 (𝑛𝑝 − 𝑛 − 𝑝) =1− lim 𝑛 1 = 𝑝2 𝑛→∞ 𝑛 (𝑛 − 1) 𝑝 Γ1 2 (𝑝 − 1 − 𝑛 ) 2 · (𝑝 − 1) =1− lim =1− 𝑝 2 𝑛→∞ 1 − 𝑛1 𝑝2 which gives a better lower bound than the 12 from Theo- rem 2.1 for all 𝑝 > 2. 𝑆(Γ1 ) = 1, | PAut(Γ1 )| = 11033 2.2. Relations between the symmetry level of a graph and the size of its Γ2 inverse monoid of partial automorphisms Question 2 ([3]). When given two graphs of the same order, does a higher symmetry level of one of them neces- 𝑆(Γ2 ) = 87 , | PAut(Γ2 )| = 13871 sarily mean that it will also have a larger monoid of partial automorphisms? Figure 3: Graphs providing an answer to Question 2. Relying on the combination of trial and error attempts and exhaustive search of graphs of order at most 10 again, we found a pair of graphs of order 8 that provides a nega- Γ1 tive answer to Question 2, and is shown in Figure 3. While 𝑆(Γ1 ) = 1 and 𝑆(Γ2 ) = 87 , and thus 𝑆(Γ2 ) < 𝑆(Γ1 ), the graph Γ1 has fewer partial automorphisms than Γ2 ; the exact numbers being 11033 vs. 13871 partial auto- morphisms. This pair of graphs appears to be the first member of 𝑆(Γ1 ) = 1, | PAut(Γ1 )| = 195779 an infinite family of examples where every new pair is constructed from the previous pair by attaching two new Γ2 vertices (one on each side) as shown in Figure 4. Each new pair consists of a graph of symmetry level 1 and an asymmetric graph of strictly smaller symmetry level 𝑛−1 𝑛 , with the second graph apparently having a larger monoid of partial automorphisms. By determining the orders of the corresponding 9 𝑆(Γ2 ) = 10 , | PAut(Γ2 )| = 255414 monoids, we have verified this observation for the first three pairs of graphs in the family. Specifically, the Figure 4: Extension of graphs providing an answer to Ques- order of the monoid of partial automorphisms of the tion 2. more symmetric graph of order 10 consists of 195779 vs. 255414 partial automorphisms in favor of the less Based on our negative answer to Question 2, we know symmetric graph. The pattern repeats for the next pair that a higher symmetry level does not necessarily imply with 3859889 versus 5327803 partial automorphisms a larger number of partial automorphisms. This may be for graphs of order 12. As the difference between the the consequence of the fact that the absence of nontrivial orders of inverse monoids of partial automorphisms of (global) automorphism does not negatively affect the ex- the corresponding graphs keeps increasing, we formu- istence of a large number of small partial automorphisms. late our observation in the form of a conjecture. Its proof However, it might be the case that the absence of non- would require a determination of the orders of the two trivial automorphisms in a graph of order 𝑛 could have a negative impact on the number of partial automorphisms the corresponding orders of monoids of partial automor- of rank 𝑛 − 1. That is why we propose a new question. phisms. We note that the non-asymmetric graph from Figure 5 Question 3. When given two graphs of the same order has only a small automorphism group. Despite both our 𝑛, does one of them being asymmetric and another non- computational effort and trial and error attempts, we asymmetric necessarily mean that the asymmetric one will were unable to find graphs with larger automorphism have fewer partial automorphisms of rank 𝑛 − 1? groups such that some asymmetric graph of the same order 𝑛 has more partial automorphisms of rank 𝑛 − 1. 2.3. Asymmetric depth of almost all graphs Next, we address the following question. Question 4 ([3]). Does there exist a graph Γ of order 𝑛 and level of symmetry equal to 𝑛−𝑑 𝑛 for arbitrarily large 𝑑 ≥ 2? To simplify our discussion, we shall refer to 𝑑 as the asymmetric depth of Γ. By Theorem 2.1, we know that asymmetric depth cannot be greater than 12 𝑛. We pro- pose to use a probabilistic approach to build more intu- ition with regard to Question 4. Graph Γ1 with | Aut(Γ1 )| = 2 and 50 partial Recall that a graph Γ of order 𝑛 is asymmetric if and automorphisms of rank 𝑛 − 1 only if 𝑆(Γ) ≤ 𝑛−1𝑛 . That means that the result asserting that almost all graphs are asymmetric proven in [4] can be reformulated using the language of partial automor- phisms as follows. Theorem 2.4. The limit of probabilities (︂ )︂ 𝑛−1 lim 𝑃 𝑆(Γ) ≤ = 1, 𝑛→∞ 𝑛 where 𝑃 𝑆(Γ) ≤ 𝑛−1 (︀ )︀ 𝑛 represents the probability that the symmetry level of a randomly chosen graph Γ of order 𝑛 does not exceed 𝑛−1 𝑛 . This formulation raises the question of whether the constant asymmetric depth 1 in the above formula can be Graph Γ2 with | Aut(Γ2 )| = 1 and 666 partial replaced with any fixed integral asymmetric depth 𝑑 ≥ 1. automorphisms of rank 𝑛 − 1 We feel that the following conjecture stated originally in [2] is very likely true as well. Figure 5: Graphs Γ1 and Γ2 of order 𝑛 = 19 which provide a negative answer to Question 3. Conjecture 2.5. Let 𝑑 ≥ 1 be an integer. The limit of probabilities We again answer this question in negative by con- (︂ )︂ 𝑛−𝑑 structing two graphs of order 19 shown in Figure 5. The lim 𝑃 𝑆(Γ) ≤ = 1, 𝑛→∞ 𝑛 first one, Γ1 , is non-asymmetric with | Aut(Γ1 )| = 2 and has 50 partial automorphisms of rank 𝑛 − 1. The where 𝑃 (︀𝑆(Γ) ≤ 𝑛−𝑑 )︀ represents the probability that second graph, Γ2 , is asymmetric, | Aut(Γ2 )| = 1, but it the symmetry level of𝑛a randomly chosen graph Γ of order has 666 partial automorphisms of rank 𝑛 − 1. Thus, we 𝑛 does not exceed 𝑛−𝑑 . have shown that if a graph is asymmetric, we cannot ex- 𝑛 pect it to have necessarily fewer partial automorphisms So far, we were unable to prove this conjecture. How- of rank 𝑛−1 than more symmetric graphs, which further ever, it might be easier to address a closely related ques- emphasises the need to improve our understanding of tion which focuses exclusively on partial automorphisms the correspondence between the symmetry levels and which are also automorphisms of some induced subgraph of a graph Γ. In order to formalize our reformulation, we partial automorphisms of a given graph. Therefore, be- define the adjusted level of symmetry of a graph Γ, 𝑆 ′ (Γ), fore computing partial automorphisms, we minimise the to be the ratio of the order of a largest non-asymmetric branching factor by introducing the following ad hoc induced subgraph of Γ and the order of Γ. heuristics. Clearly, for any graph Γ, 𝑆 ′ (Γ) ≤ 𝑆(Γ), since Γ can also have partial automorphisms that do not have the 1. Eliminating complements since 𝑆(Γ) = 𝑆(Γ̃) same domain and range (are not nontrivial automor- [3]. phisms of an induced subgraph). 2. Utilising the result of Theorem 2.1 and by com- We believe the following conjecture might be shown puting the bound using min{∆𝑗𝑘 } for some ver- to be true if one could show that if we remove a constant tices 𝑣𝑗 , 𝑣𝑘 , omitting the graphs which have small number of randomly chosen vertices from a large random min{∆𝑗𝑘 }. graph, we will again have a large random graph of a 3. Omitting the graphs with many small or large smaller order, which is also likely to be asymmetric. A degrees since for increasing the 𝑑, most of the formal proof of this statement would however require vertices of the asymmetric graphs should have a very careful manipulation of the concepts from the theory degree roughly equal to 𝑛2 [5]. of random graphs. With these ideas, we parallelised the search through Conjecture 2.6. Let 𝑑 ≥ 1 be an integer. The limit of the space of asymmetric graphs that are possible to be probabilities reached by extending the previous database of record (︂ )︂ graphs from [5]. After roughly three days of computa- ′ lim 𝑃 𝑆 (Γ) ≤ 𝑛−𝑑 = 1, tions, we found a new record graph with 𝑛 = 27, 𝑑 = 7. 𝑛→∞ 𝑛 It turns out that while most of the graphs are asymmet- (︀ ′ ric, with our computations we find that most have only where 𝑃 𝑆 (Γ) ≤ 𝑛−𝑑 )︀ 𝑛 represents the probability that rather small 𝑑. We analysed the record graphs, but due the adjusted symmetry level of a randomly chosen graph Γ to lack of any clear global structure of these graphs, we of order 𝑛 does not exceed 𝑛−𝑑 𝑛 . were unable to extend our example to larger graphs. To further our experiments with regard to Question 4, 2.4. Computer assisted searches for we changed the approach by considering very "symmet- graphs of increasing asymmetric ric" graphs and making them asymmetric. Specifically, we considered 𝑛-dimensional hypercubes which have depth the property that min{∆𝑗𝑘 } increases with growing 𝑛, Since the above probabilistic arguments appear to sug- while they remain arc-transitive. Instead of necessarily gest a positive answer to Question 4, we set to find removing vertices from these graphs, we noticed that an explicit construction of an infinite family of graphs multiple 𝑛-dimensional hypercubes can be joined asym- with increasing asymmetric depth. For this reason, we metrically. For example, one can glue hypercubes to- set to investigate the record graphs that increase 𝑑 in gether and construct two columns of 𝑛-dimensional hy- 𝑆(Γ) ≥ 𝑛−𝑑 𝑛 . Previously, the record 𝑑 for the graph percubes, the first column with two 𝑛-dimensional hyper- symmetry level found in [3] was 𝑆(Γ) ≥ 𝑛−𝑑 𝑛 ; 𝑑 = 5; cubes and the second column with three 𝑛-dimensional which means that one can delete any subset of up to 4 hypercubes; with the adjacent hypercubes sharing an vertices without obtaining a graph admitting nontrivial (𝑛 − 1)-dimensional hyperface. For 𝑛 = 2, see Figure 6. partial automorphisms. As 𝑛 increases, we add some diagonals to each hypercube Some graphs of order 9 can already have millions of to prevent the early occurrence of mirror symmetry. This partial automorphisms. To determine the asymmetry allowed us to computationally increase 𝑑 starting with depth 𝑑, we have to look at isomorphisms between all in- 𝑑 = 1 for 2-dimensional-hypercubes, to 𝑑 = 5 for 5- duced subgraphs of decreasing order until we find some dimensional-hypercubes. For this construction, we have nontrivial(︀partial not yet proved that increasing the dimension 𝑛 of the )︀ automorphism. In a graph of order 𝑛, there are 𝑛−𝑑 induced subgraphs of order 𝑛 − 𝑑. For hypercubes, necessarily makes 𝑑 grow indefinitely and 𝑛 each of these induced subgraphs, we have to compute cover all 𝑑 ≥ 2. In fact, our construction skipped 𝑑 = 4. its automorphism group, and then determine isomor- phisms between all combinations of induced subgraphs of order 𝑛 − 𝑑. Thus, computing the whole inverse monoid for a graph is already intractable for rather small graphs. However, taking advantage of the inequality 𝑛−min{Δ𝑗𝑘 } 𝑆(Γ) ≥ 𝑛 , determining the parameter 𝑆(Γ) can be done without computing the entire monoid of and 𝑢𝑗 and fixing all other vertices of Γ is an automor- phism of Γ. If 𝐶1 = {𝑢1 } is the unique component of cardinality 1, any non-trivial partial automorphism 𝜙 of Γ ∖ {𝑢1 } (Γ with 𝑢1 removed) can be extended by adding 𝜙(𝑢1 ) = 𝑢1 . Using the above theorem and Theorem 2.1, it is possible to prove the following corollary. Corollary 3.2. Let Γ be a disconnected graph without a unique isolated vertex. Then 𝑆(Γ) ≥ 34 . Proof. Let Γ be a disconnected graph of order 𝑛 without a unique isolated vertex with components 𝐶1 , 𝐶2 , ..., 𝐶𝑐 . Figure 6: Asymmetric graph constructed of 2-dimensional If there are at least two isolated vertices in Γ, then hypercubes. 𝑆(Γ) = 1. If Γ contains no isolated vertices, let 𝐶𝑗 denote a smallest component of Γ. Then, |𝑉 (𝐶𝑗 )| ≤ 𝑛2 . Theorem 2.1 yields that 𝑆(𝐶𝑗 ) ≥ 12 . Therefore, by Theo- rem 3.1, 3. Further results on symmetry levels of graphs 1 ∑︁ 𝑛𝑆(Γ) ≥ |𝑉 (𝐶𝑗 )| + |𝑉 (𝐶𝑖 )| = 2 𝑖∈{1,...,𝑐}∖{𝑗} 3.1. Disconnected graphs and graphs with 1 1 small cut sets = |𝑉 (𝐶𝑗 )| + (𝑛 − |𝑉 (𝐶𝑗 )|) = 𝑛 − |𝑉 (𝐶𝑗 )| ≥ 2 2 As we have seen at the end of Section 2.1, certain 1 1 3 ≥ 𝑛 − · 𝑛 = 𝑛. classes of graphs allow further improvements on the 2 2 4 lower bounds on their symmetry levels. A slightly dif- ferent version of the following theorem was proven for disconnected graphs in [2]. Furthermore, if a graph Γ has a relatively small vertex cut set, it is usually possible to remove a small number of Theorem 3.1. Let Γ be a disconnected graph of order 𝑛 vertices from Γ and obtain a disconnected graph, which with 𝑐 components 𝐶1 , 𝐶2 , ..., 𝐶𝑐 . will have a level of symmetry at least 34 . (i) For every 𝐶𝑗 , 1 ≤ 𝑗 ≤ 𝑐, of cardinality bigger than Corollary 3.3. Let Γ be a graph of order 𝑛 with a vertex one, we obtain the following lower bound for the 3 (𝑛−|𝑆|−1) symmetry level of Γ: separator 𝑆. Then 𝑆(Γ) ≥ 4 𝑛 . Moreover, if Γ∖𝑆 does not contain a unique isolated vertex, then 𝑆(Γ) ≥ 3 (𝑛−|𝑆|) |𝑉 (𝐶𝑗 )| · 𝑆(𝐶𝑗 ) 1 ∑︁ 4 . 𝑆(Γ) ≥ + |𝑉 (𝐶𝑖 )|. 𝑛 𝑛 𝑛 𝑖∈{1,...,𝑐}∖{𝑗} Proof. Let Γ be a graph of order 𝑛 with a vertex separator 𝑆. If Γ ∖ 𝑆 contains a unique isolated vertex 𝑣, then by (ii) If at least two of the components 𝐶1 , 𝐶2 , ..., 𝐶𝑐 are Corollary 3.2 𝑆(Γ∖𝑆∖{𝑣}) ≥ 34 . Therefore, by removing of cardinality 1, 𝑆(Γ) = 1. 3 (𝑛−|𝑆|−1) 𝑆 and 𝑣 from Γ, we obtain 𝑆(Γ) ≥ 4 𝑛 . If Γ ∖ (iii) If exactly one of the components 𝐶1 , 𝐶2 , ..., 𝐶𝑐 𝑆 does not contain a unique isolated vertex, then by 3 (𝑛−|𝑆|) is of cardinality 1, say, 𝐶1 = {𝑢1 }, 𝑆(Γ) = Corollary 3.2 𝑆(Γ) ≥ 4 . 1+(𝑛−1)𝑆(Γ∖{𝑢1 }) 𝑛 𝑛 . Corollary 3.4. Let 𝑠 ∈ N. Let Γ𝑘 be an infinite family Proof. We only provide a quick sketch of the proof that is of graphs such that every graph in this infinite family has based on ideas introduced in Section 2.1. If |𝑉 (𝐶𝑗 )| > 1, a vertex separator of size at most 𝑠. Then a partial automorphism acting on a subset of 𝐶𝑗 the same way as one of the partial automorphisms of 𝐶𝑗 of the lim 𝑆(Γ𝑘 ) ≥ 3 . rank |𝑉 (𝐶𝑗 )|𝑆(𝐶𝑗 ) and fixing vertices in all components 𝑘→∞ 4 distinct from 𝐶𝑗 has the rank appearing in part (i) of the theorem. If at least two components, 𝐶𝑖 = {𝑢𝑖 } and 𝐶𝑗 = {𝑢𝑗 }, are of cardinality one, the map swapping 𝑢𝑖 3.2. Relation to measure of asymmetry introduced by Erdős & Rényi In their 1963 paper [4], Erdős & Rényi considered a measure of asymmetry that might at first appear quite dif- ferent from the one we consider in our paper. Their idea is based on deleting edges to obtain a non-asymmetric graph. Definition 3.5 (Degree of asymmetry). The degree of asymmetry of a graph Γ, 𝐴− (Γ), is the minimum number of edges that need to be deleted so that Γ becomes non- asymmetric. As we have already pointed out in Section 2.1, both the general bounds for the symmetry levels proven therein and the degree of asymmetry results of Erdős & Rényi rely on the same idea of considering the minimum of the symmetric difference of the neighbourhoods over all pairs of vertices. This often results in asymmetric depth and degree of asymmetry of a graph being equal. Figure 7: A graph where 𝑑 = 1 and 𝐴− (Γ) = 3. The graph This is further confirmed by the corresponding results was constructed by trial and error from three disjoint cycles of concerning forests as listed in Table 1. length 14 and one isolated vertex. We connected the isolated vertex to the first cycle in such a way that the vertex and the first cycle resulted in an asymmetric graph. This was done as 𝐴− (Γ) 𝑑 𝑆(Γ) follows. We connected the isolated vertex to some starting 1 1 1 general lower bound 2 𝑛 2 𝑛 2 vertex from the cycle. We continued in the clockwise direction 𝑛−1 where we omitted the possible edge to the next neighbouring lower bound for forests 1 1 𝑛 [3] vertex. We made two subsequent edges and again omitted the Table 1 next vertex. Lastly, we connected three subsequent vertices to Comparison of lower bounds for the parameters 𝐴− (Γ), 𝑑 the isolated vertex and omitted the remaining ones. We made and 𝑆(Γ) where 𝑛 is the order of the considered graph. The the same kind of connections to the second cycle. We rotated results in the first column come from [4]. the second cycle counterclockwise with the step of 5. We then linked the cycles as shown. Thus, all of the asymmetry is linked to just the one special vertex. It is therefore natural to ask how big can the differ- ence between these two parameters be in general graphs. When addressing this question, we constructed graphs for which 3 = 𝐴− (Γ) > 𝑑 = 1, where 𝑑 corresponds to the number of vertices that have to be removed from Γ 4. Final remarks to obtain a non-asymmetric subgraph. One such graph In this paper, we established that the level of symmetry can be seen in Figure 7. of any simple graph is at least 12 , and for disconnected On the other hand, there are also graphs where graphs without a unique isolated vertex, it is at least 𝐴− (Γ) < 𝑑; e.g., the graph in Figure 8 for which 3 (and is even more for many other classes of graphs). 𝐴− (Γ) = 1 and 𝑑 = 3. We also entertained the ques- 4 By answering Question 2, we exhibited computationally tion of what is the maximum possible difference between that a higher level of symmetry does not imply a larger 𝐴− (Γ) and 𝑑. We have empirically discovered that find- number of partial automorphisms; further emphasising ing graphs for which the difference would be greater than the importance of studying local symmetries. We have two is rather hard. We formulate questions inspired by also applied probabilistic and computational methods to our results in the most generalized form in Question 5. build more intuition in understanding Question 4. Despite the generality of this question, we believe that For the implementation and testing of our algorithms the answer is positive for any pair 𝑎 and 𝑑. Some kind we used the mathematical software system - SageMath, of a generalization of either the graph in Figure 7 or theversion 10.1 [11] taking advantage of the existence of ex- graph in Figure 8 might be a good starting point in the tensive and useful libraries in the Sage ecosystem. In de- construction of such graphs. termining the inverse monoids of the considered graphs, Question 5. Does there exist for any pair of positive in- we used the interface to the system for discrete computa- tegers 𝑎 and 𝑑 a graph Γ such that 𝐴− (Γ) = 𝑎, and the tional algebra - GAP, version 4.12.2 [10]. We also used asymmetry depth of Γ is equal to 𝑑? GAP to represent the inverse monoids of partial automor- Proceedings of the 23rd Conference Information Tech- nologies – Applications and Theory (ITAT), pages 191–196, 2023. [4] P. Erdős and A. Rényi. Asymmetric graphs. Acta Mathematica Academiae Scientiarum Hungarica, (14):295–315, 1963. [5] M. Gál. Symmetries of Combinatorial Structures. Diploma thesis, Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics, 2023. [6] R. Jajcay, T. Jajcayová, N. Szakács, and M. B. Szen- drei. Inverse monoids of partial graph automor- phisms. Journal of Algebraic Combinatorics, 53(3): 829–849, 2021. [7] T. Jajcayova. On the Interplay Between Global and Local Symmetries. Algebraic Graph Theory International Webinar AGTIW, 2021. URL http: //euler.doa.fmph.uniba.sk/AGTIW.html. [8] J. H. Kim, B. Sudakov, and V. H. Vu. On the asymme- try of random regular graphs and random graphs. Random Structures & Algorithms, 21(3-4):216–224, Figure 8: Graph where 𝑑 = 3 and 𝐴− (Γ) = 1. All of the 2002. ISSN 1042-9832. doi: 10.1002/rsa.10054. asymmetry is linked to the red edge. [9] J. Pastorek and T. Jajcayová. Asymmetric graphs and partial automorphisms. In Proceedings of the 59th Czech-Slovak Conference on Graph Theory, Tro- phisms of graphs. All our computations were utilised on janovice, Czech Republic, June 3-7 2024. URL a computer with a 12th Gen Intel Core i5-12450H proces- https://graphs.vsb.cz/csgt2024/. sor, 4400 MHz, 8 cores, 12 logical processors, and 32GB [10] The GAP Group. GAP – groups, algorithms, and of RAM. programming, version 4.12.2, 2023. URL https:// www.gap-system.org. [11] The Sage Developers. Sagemath, the sage mathe- 5. Acknowledgements matics software system (version 10.1), 2023. URL https://www.sagemath.org. We are grateful to Robert Jajcay for his helpful advice and suggestions. The second and the third authors acknowledge support from VEGA - 1/0437/23 and SK-AT-23-0019 grants. 6. Bibliography [1] L. Babai. Graph isomorphism in quasipolyno- mial time [extended abstract]. In Proceedings of the Forty-Eighth Annual ACM Symposium on The- ory of Computing, STOC ’16, pages 684–697, New York, NY, USA, June 2016. Association for Com- puting Machinery. ISBN 978-1-4503-4132-5. doi: 10.1145/2897518.2897542. [2] V. Cingel. Dolné ohraničenia maximálnej hod- nosti netriviálnych čiastočných automorfizmov jednoduchých grafov. Bachelor thesis, Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics, 2024. [3] V. Cingel, M. Gál, and T. B. Jajcayová. Partial sym- metries and symmetry levels of graphs – a census.