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 1 . In case of disconnected graphs without a unique isolated vertex, we prove that the symmetry level 2 of such graphs is at least 3 . Furthermore, we present graphs that provide an answer to Question 3 posted by Cingel, Gál & Jajcayová by showing that4higher 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.
study of partial automorphisms of graphs [
Almost all graphs are known to be asymmetric [
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($T. cJainjcgaeyl1o3v@á)u;jnainb.ap.sakst(oVr.ekC@infgmelp)h;t.uatniiabnaa.s.jkaj(cJa.yPoavsato@refmk)ph.uniba.s 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
JaCPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) jcay et al. in [
. Note that each of such triples and therefore
∑︁ 1≤ <≤ 2. Addressing open questions of
In the article [
Although we will not settle Question 1, in what follows,
we improve the lower bound (Γ) ≥
[
{1, 2, . . . , }, let and be two distinct vertices of Γ , and let be the partial map mapping the subset of vertices of (Γ) tained in the symmetric diference of the neighborhoods Γ()△Γ( ) of and in Γ onto itself by swapping and , () = and ( ) = , and fixing all vertices of Γ distinct from and and not contained in the symmetric diference Γ()△Γ( ), () = , for all ∈ (Γ) − (Γ()△Γ( )) − { , }.
It is easy to see that is a partial automorphism of Γ of rank | (Γ) − (Γ()△Γ( ))|. Denoting the cardinality of the symmetric diference of the neighbourhoods of and by ∆ allows us now to derive the first (and in some sense, the most general) lower bound on the symmetry level of Γ that will serve as the basis of our forthcoming arguments: (2) (3) (4)
In order to obtain another formulation of Theorem 2.1, let denote the degree of the -th vertex of Γ , and let denote the cardinality of Γ() ∩ Γ( ), the set of shared neighbors of and . Using this notation, it is easy to see that ∆ = + − 2 − 2 , (5) for all 1 ≤
̸= ≤ distinct and adjacent, and = 0 otherwise. Then,
, where = 1 if and are ∑︁ 1≤ <≤ 4 − 2 ∑︁ ( + ) − 2
· =1 (︃ )︃ 2
∑︁ 1≤ <≤ − 2
· − 2 = (4 − 2) −
∑︁ 1≤ <≤
∑︁ 1≤ <≤ ∆ = ≤ ∑︁ ( − 1) = =1 =1 (4 − 2) − ∑︁(2 − ) = 4 − ∑︁ ,
2 =1 (6) where is the size (the number of edges) of Γ . Based on the above, we obtain the following corollary. and size , Corollary 2.2. For any simple graph Γ of order ≥ 2
min{Δ } , i.e., graphs whose symmetry level matches
the lower bound in (1). On the other hand, despite
considerable computational efort, we have not found a graph
with symmetry level close to 12 . In his 2023 master thesis
[
57 matches the lower bound from (1). morphism of maximal rank can be obtained by swapping 15% of all asymmetric graphs up to the or- family of -regular graphs lim →∞ ︂( 1 − maining 15% of the asymmetric graphs, all graphs were of order 10. In this subset of graphs, almost all graphs have the largest nontrivial partial automorphism of rank ( −
min{∆ }) + 1 = − to − see Figure 2. predicted by the lower bound by 1, i.e., it is the closest possible to the considered lower bound. Moreover, the majority of these graphs have only few nontrivial partial automorphisms of the maximal rank − which swap only two vertices. Finally, there were also
tens of graphs in which the largest rank of a nontrivial automorphism exceeds the lower bound by 2 and is equal min{∆ } + 2 = − 1. For one such example,
̸= the -regular graph, = , we obtain for any infinite =1 ( − 1 −
) )︃
lim
rem 2.1 for all > 2.
which gives a better lower bound than the 12 from
Theo2.2. Relations between the symmetry
level of a graph and the size of its
inverse monoid of partial
automorphisms
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 negative 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 automorphisms.
This pair of graphs appears to be the first member of monoid of partial automorphisms. an infinite family of examples where every new pair is constructed from the previous pair by attaching two new 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
By determining the orders of the corresponding monoids, we have verified this observation for the first three pairs of graphs in the family. Specifically, the order of the monoid of partial automorphisms of the more symmetric graph of order 10 consists of 195779 vs. 255414 partial automorphisms in favor of the less symmetric graph. The pattern repeats for the next pair with 3859889 versus 5327803 partial automorphisms for graphs of order 12. As the diference between the orders of inverse monoids of partial automorphisms of corresponding monoids for all pairs of members of the infinite family.
Conjecture 2.3. The order of the inverse monoid of partial automorphisms of the graph with a smaller symmetry level is larger than that of the graph of the symmetry level 1 for each pair of graphs constructed in the above described way from the pair in Figure 3.
(Γ1) = 1, | PAut(Γ1)| = 11033 (Γ2) = 78 , | PAut(Γ2)| = 13871 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 would require a determination of the orders of the two However, it might be the case that the absence of nontrivial automorphisms in a graph of order could have a negative impact on the number of partial automorphisms the corresponding orders of monoids of partial automorof rank − 1. That is why we propose a new question. phisms.
Question 3. When given two graphs of the same order , does one of them being asymmetric and another nonasymmetric necessarily mean that the asymmetric one will have fewer partial automorphisms of rank − 1? ︂( ︂(
We note that the non-asymmetric graph from Figure 5 has only a small automorphism group. Despite both our computational efort and trial and error attempts, we were unable to find graphs with larger automorphism 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
≥ 2?
Question 4 ([
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 propose to use a probabilistic approach to build more intuition with regard to Question 4.
Recall that a graph Γ of order is asymmetric if and only if (Γ) ≤
− 1 . That means that the result asserting
that almost all graphs are asymmetric proven in [
Theorem 2.4. The limit of probabilities →∞ lim (Γ) ≤ − 1 )︂
= 1, where (︀ (Γ) ≤ does not exceed − 1 and has 50 partial automorphisms of rank − 1. The second graph, Γ 2, is asymmetric, | Aut(Γ 2)| = 1, but it has 666 partial automorphisms of rank −
1. Thus, we have shown that if a graph is asymmetric, we cannot expect it to have necessarily fewer partial automorphisms of rank − 1 than more symmetric graphs, which further emphasises the need to improve our understanding of the correspondence between the symmetry levels and which are also automorphisms of some induced subgraph
1 be an integer. The limit of
[
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 heuristics.
1 be an integer. The limit of the space of asymmetric graphs that are possible to be induced subgraph of Γ and the order of Γ .
Clearly, for any graph Γ , ′(Γ) ≤
(Γ) , since Γ can also have partial automorphisms that do not have the same domain and range (are not nontrivial automorphisms of an induced subgraph).
We believe the following conjecture might be shown to be true if one could show that if we remove a constant number of randomly chosen vertices from a large random graph, we will again have a large random graph of a smaller order, which is also likely to be asymmetric. A formal proof of this statement would however require very careful manipulation of the concepts from the theory of random graphs. 2.4. Computer assisted searches for graphs of increasing asymmetric depth
Since the above probabilistic arguments appear to suggest a positive answer to Question 4, we set to find an explicit construction of an infinite family of graphs with increasing asymmetric depth. For this reason, we set to investigate the record graphs that increase in
− . Previously, the record for the graph
symmetry level found in [
− ; = 5; partial automorphisms.
Some graphs of order 9 can already have millions of
partial automorphisms. To determine the asymmetry
[
min{∆ }. 1. Eliminating complements since (Γ) =
(Γ˜)
2. Utilising the result of Theorem 2.1 and by
computing the bound using min{∆ } for some
vertices , , omitting the graphs which have small
3. Omitting the graphs with many small or large
degrees since for increasing the , most of the
vertices of the asymmetric graphs should have a
degree roughly equal to 2 [
With these ideas, we parallelised the search through
reached by extending the previous database of record
graphs from [
It turns out that while most of the graphs are asymmetric, with our computations we find that most have only rather small . We analysed the record graphs, but due to lack of any clear global structure of these graphs, we were unable to extend our example to larger graphs.
To further our experiments with regard to Question 4, we changed the approach by considering very "symmetric" graphs and making them asymmetric. Specifically, we considered -dimensional hypercubes which have the property that min{∆ } increases with growing , while they remain arc-transitive. Instead of necessarily removing vertices from these graphs, we noticed that multiple -dimensional hypercubes can be joined asymmetrically. For example, one can glue hypercubes together and construct two columns of -dimensional hypercubes, the first column with two -dimensional hypercubes and the second column with three -dimensional hypercubes; with the adjacent hypercubes sharing an
1)-dimensional hyperface. For = 2, see Figure 6.
As increases, we add some diagonals to each hypercube to prevent the early occurrence of mirror symmetry. This allowed us to computationally increase starting with dimensional-hypercubes. For this construction, we have not yet proved that increasing the dimension of the hypercubes, necessarily makes grow indefinitely and cover all ≥ 2. In fact, our construction skipped = 4. depth , we have to look at isomorphisms between all in- = 1 for 2-dimensional-hypercubes, to = 5 for 5duced subgraphs of decreasing order until we find some nontrivial partial automorphism. In a graph of order , there are (︀ − )︀ induced subgraphs of order − . For each of these induced subgraphs, we have to compute its automorphism group, and then determine isomorphisms 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 automorphism 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 . (ii) If at least two of the components 1, 2, ..., are of cardinality 1, (Γ) = 1 .
and from Γ , we obtain (Γ) ≥ 34 (−| |− 1) . If Γ ∖ (iii) If exactly one of the components 1, 2, ..., does not contain a unique isolated vertex, then by i1s+o(f− c1a)rd(iΓn∖a{lit1y})1., say, 1 = {1}, (Γ) = Corollary 3.2 (Γ) ≥ 43 (−| |) .
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. Further results on symmetry
levels of graphs 3.1. Disconnected graphs and graphs with
small cut sets
As we have seen at the end of Section 2.1, certain
classes of graphs allow further improvements on the
lower bounds on their symmetry levels. A slightly
different version of the following theorem was proven for
disconnected graphs in [
Theorem 3.1. Let Γ be a disconnected graph of order with components 1, 2, ..., . (i) For every , 1 ≤ ≤ , of cardinality bigger than one, we obtain the following lower bound for the symmetry level of Γ :
Furthermore, if a graph Γ has a relatively small vertex cut set, it is usually possible to remove a small number of vertices from Γ and obtain a disconnected graph, which will have a level of symmetry at least 34 .
Corollary 3.3. Let Γ be a graph of order with a vertex separator . Then (Γ) ≥ 34 (−| |− 1) . Moreover, if Γ ∖ does not contain a unique isolated vertex, then (Γ) ≥ 34 (−| |) .
Proof. Let Γ be a graph of order with a vertex separator . If Γ ∖ contains a unique isolated vertex , then by Corollary 3.2 (Γ ∖ ∖{}) ≥ 43 . Therefore, by removing 3.2. Relation to measure of asymmetry
introduced by Erdős & Rényi
In their 1963 paper [
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 nonasymmetric.
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 diference 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
general lower bound 12 12 21 vertex from the cycle. We continued in the clockwise direction
lower bound for forests 1 1 − 1 [
It is therefore natural to ask how big can the diference 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 Γ to obtain a non-asymmetric subgraph. One such graph can be seen in Figure 7.
On the other hand, there are also graphs where − (Γ) < ; e.g., the graph in Figure 8 for which − (Γ) = 1 and = 3. We also entertained the question of what is the maximum possible diference between − (Γ) and . We have empirically discovered that finding graphs for which the diference would be greater than two is rather hard. We formulate questions inspired by our results in the most generalized form in Question 5.
Despite the generality of this question, we believe that the answer is positive for any pair and . Some kind of a generalization of either the graph in Figure 7 or the graph in Figure 8 might be a good starting point in the construction of such graphs.
Question 5. Does there exist for any pair of positive integers and a graph Γ such that − (Γ) = , and the asymmetry depth of Γ is equal to ?
In this paper, we established that the level of symmetry of any simple graph is at least 12 , and for disconnected graphs without a unique isolated vertex, it is at least 34 (and is even more for many other classes of graphs). By answering Question 2, we exhibited computationally that a higher level of symmetry does not imply a larger number of partial automorphisms; further emphasising the importance of studying local symmetries. We have also applied probabilistic and computational methods to build more intuition in understanding Question 4.
For the implementation and testing of our algorithms
we used the mathematical software system - SageMath,
version 10.1 [
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.