Schedule for: 18w5050 - Symmetry Breaking in Discrete Structures

Given a group $A$ acting on a set $X$, the distinguishing number, or asymmetric coloring number, denoted $D(A,X)$ or $ACN(A,X)$, is the smallest $k$ such that $X$ has a $k$-coloring where the only elements of $A$ preserving the coloring fix all elements of $X$, thus "breaking" the symmetry of $X$ under $A$. Albertson and Collins [1996] introduced and named $D(G)$ in the context of a graph $G$ with $A=Aut(G), X=V(G)$, but precedents include Babai's work [1977] on regular trees, Cameron et al.\ [1984] and Seress [1997] on regular orbits for a primitive permutation group acting on the set of subsets of $X$, and work of many authors on the graph isomorphism problem using colors to "individualize" vertices. This talk will survey various aspects of symmetry breaking: contexts other than graphs (such as maps), bounds relating $D(G)$ and the maximal degree of $G$, variations of $D(G)$ where the coloring is proper or where edges are colored instead of vertices. An underlying theme is the role of the elementary "Motion Lemma'' (Cameron et al. [1984] and Russel and Sundaram [1997]) that $D\leq 2$ when $m(A)>2\log_2(|A|)$, where $m(A)$ is the minimum number of elements of $X$ moved by any element of $A$ not acting as the identity on $X$.

A graph is said to have infinite motion, if every automorphism moves infinitely many vertices. Tucker's Infinite Motion Conjecture asserts that if a locally finite graph has infinite motion, then there is a 2-colouring of its vertex set which is only preserved by the identity automorphism. We show that this is true for graphs whose maximum degree is at most 5. In case the maximum degree is 3, we can even drop the assumption of infinite motion. Coauthors: M. Pilsniak, M. Stawiski

Apart from finitely many exceptions, connected vertex-transitive graphs of valency at most 3 have distinguishing number 2. Recently, Florian Lehner and I determined the distinguishing number of all vertex-transitive graphs of valency 4. In this case, there are infinitely many examples with distinguishing number 3. I will discuss this recent work, as well as some intriguing related questions.

The distinguishing index $D'(G)$ of a graph $G$ is the least number of colours in an edge colouring that breaks all nontrivial automorphisms of $G$. This invariant is defined only for graphs with at most one isolated vertex and without $K_2$ as a component (we call them admissible graphs). The general upper bound for connected admissible graphs is $D'(G)\leq \Delta(G)$ except for small cycles $C_3,C_4,C_5$. Moreover, it was proved by the second author that the equality holds only for cycles of length at least six, symmetric and bisymmetric trees and for two small graphs $K_4,K_{3,3}$. Recently, we proved with Imrich and Woźniak that $$D'(G)\leq \left\lceil\sqrt{\Delta(G)}\right \rceil+1$$ for every connected graph of order at least seven and without pendant edges. There are classes of graphs with the distinguishing index at most two (perhaps with few known exceptions). For instance, traceable graphs, claw-free graphs, Cartesian powers of connected graphs, and 3-connected planar graphs (the latter result was recently proved by Pilśniak and Tucker). A number of open problems will be formulated. Coauthor: Monika Pilśniak

If we want to distinguish all vertices of the graph by coloring its elements, then we have the following possibilities. We can use the concept of coloring that breaks non-trivial automorphisms, or coloring that induces different color palettes for each vertex. These approaches are not independent. Always distinguishing using automorphisms is stronger than using palettes. And, very often, the corresponding parameters are quite distant from each other. We will show several situations when the corresponding parameters are close to each other. The talk is based on the papers [1] and [2]. [1] R. Kalinowski, M. Pilśniak, J. Przybyło and M. Woźniak, How to personalize the vertices of a graph?, European Journal of Combinatorics 40 (2014), 116-123. [2] R. Kalinowski, M. Pilśniak, M. Woźniak, Distinguishing graphs by total colourings, Ars Mathematica Contemporanea 11 (2016), 79-89.

A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphism of $G$ preserves it. The distinguishing number of $G$, denoted by $D(G)$, is the smallest number of colors required for such a coloring. We are intent to count number of different distinguishing colorings with a set of $k$ colors for some certain kinds of graphs. To do this, we first introduce a parameter, namely $\Phi_k (G)$, as the number of different distinguishing colorings of a graph $G$ with at most $k$ definite colors. We then introduce another similar parameter, namely $\varphi_k (G)$, as the number of different distinguishing colorings of a graph $G$ with exactly $k$ definite colors. Showing that it might be hard to calculate $\Phi_k (G)$ and $\varphi_k (G)$ even for small graphs, we use the \emph{distinguishing threshold of $G$}, $\theta(G)$, which is the minimum number $t$ such that for any $k\geq t$, any arbitrary coloring of $G$ with $k$ colors is distinguishing. When $k\geq \theta (G)$, calculating $\Phi_k (G)$ and $\varphi_k (G)$ showed to be much easier. Finally, we introduce the \emph{distinguishing polynomial} for a graph $G$ to be $$P_D (G)=\sum_{k=D(G)}^{n} \varphi_k (G) x^k .$$ An application to distinguishing lexicographic products of graphs is also presented. Coauthors: Bahman Ahmadi, Fatemeh Alinaghipour

The distinguishing number (index) $D(G)$ ($D'(G)$) of a graph $G$ is the least integer $d$ such that $G$ has a vertex (edge) labeling with $d$ labels that is preserved only by a trivial automorphism. In this talk we consider the maximal outerplanar graphs (MOP graphs) and show that MOP graphs, except $K_3$, can be distinguished by at most two vertex (edge) labels. We also consider the distinguishing number and distinguishing index of regular and Cayley graphs. In particular, we present a family of Cayley graphs, graphical regular representations of a group, for which the distinguishing number and the distinguishing index is two. Coauthor: Samaneh Soltani

The minimal degree of a permutation group $G$ is the minimum number of points not fixed by non-identity elements of $G$. Lower bounds on the minimal degree have strong structural consequences on $G$. In 2014 Babai proved that the automorphism group of a strongly regular graph with n vertices has minimal degree at least $cn$, with known exceptions. Strongly regular graphs correspond to primitive coherent configurations of rank 3. We extend Babai's result to primitive coherent configurations of rank 4. We also show that the result extends to non-geometric primitive distance-regular graphs of bounded diameter. The proofs combine structural and spectral methods. The results have consequences to primitive permutation groups that were previsouly known using the classification of finite simple groups (Cameron, Liebeck). The paper is available at arXiv:1802.06959.

This talk is based on the paper by Xiaorui Sun and John Wilmes, "Structure and automorphisms of primitive coherent configurations", arXiv:1510.02195 (2015). Coherent configurations (CCs) are edge-colorings of the complete directed graph satisfying certain regularity conditions, modeling the orbitals (orbits on ordered pairs) of permutation groups. Introduced by Schur in 1934 for the study of permutation groups, CCs also include strongly regular graphs and association schemes, structures that do not necessarily arise from groups. Primitive CCs (PCCs) are a combinatorial model of primitive permutation groups. A base of a permutation group is a subset of the permutation domain of which the pointwise stabilizer is the identity. A base of a structure (such as a graph or a CC) is a base of its automorphism group. The minimum size of a base is a measure of the cost of destroying all symmetry. 37 years ago Babai gave a nearly tight $O(\sqrt{n}\log n)$ upper bound on the minimum base size of PCCs with the trivial exception of the clique (Annals of Math, 1981). As a corollary, this result solved the then century-old problem of bounding the order of primitive permutation groups in an unexpected, purely combinatorial way. In a major recent development, Sun and Wilmes reduced the upper bound to $O(n^{1/3}(\log n)^{4/3})$, with known exceptions. As a corollary, they classify the largest primitive permutation groups, a result previously only known through the classification of finite simple groups (CFSG) (Cameron 1981). At the same time, the scope of their result goes significantly beyond primitive permutation groups, into a combinatorial domain where the CFSG has little relevance. To prove their result, Sun and Wilmes develop a combinatorial structure theory of PCCs. A crucial element of their theory is the discovery of "asymptotically uniform clique geometries" in PCCs with parameters in a certain range. Like Babai's, the Sun-Wilmes result is algorithmic: the proof is an analysis of the individualization/refinement method.

Homogenous structures exhibit a high degree of symmetry. In particular their automorphism group is transitive, and any partial isomorphism between two finite substructures extends to an automorphism of the entire structure. It is thus natural to better understand these symmetries, and one approach is by trying to break them. The distinguishing number provides an interesting tool to do so and at the same time providing structural information. Two such well known homogeneous structures are the rationals and the Rado graph. The first one is easily seen to have unbreakable symmetry in this setting, its distinguishing number is infinite. On the other hand Imrich et al. showed that the Rado graph has distinguishing number 2. We will present an overview of the distinguishing number of the homogeneous simple and directed graphs through their classification, and discuss recent results for the countable Urysohn homogenous metric spaces of given spectrum.

All but four finite vertex-transitive cubic graphs are $2$-distinguishable. We discuss the corresponding amount, resp. density, of points needed to break all the symmetries for the latter ones. This will be done by splitting the problem into three cases depending on the number of edge orbits the graph has. In the cases of one or three edge orbits the number needed is always finite. The talk will be focused on the case of two edge orbits which will prove to be a bit more diverse.

The distinguishing number $D(G)$ of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ such that the only color-preserving automorphism on $G$ is the identity. We are interested in the distinguishing number of locally finite trees. Our work is motivated by the "Infinite Motion Conjecture" given by Tucker in 2011. It says that $D(G) = 2$ if every non-identity automorphism of a given connected, locally finite, infinite graph $G$ moves infinitely many vertices. In this talk, we study the question how many vertices of a tree with bounded valence $k$ can be fixed with $c$ colors. We show that all vertices whose distance to the next leaf is at least $\lceil log_c k \rceil$ can be fixed. This is joint work with W. Imrich, J. Kloas, H. Schreiber and T. Tucker.

The Sierpiński product of graphs was introduced as a generalization of Sierpiński graphs, which is a fractal-like family of graphs. The main building blocks of Sierpiński graphs are complete graphs and each next iteration is built in the fractal-like manner of a complete graph. This idea was recently generalized to a graph product, where instead of initially taking just one graph, we build a fractal-like structure with two arbitrary graphs, say $G$ and $H$. Intuitively this is done in such a way that the product $G\otimes H$ has $|G|$ copies of graph $H$ which are connected among themselves according to the edges in $G$. So we get a graph with local structure of $H$, but global structure of $G$ (i.e., if we contract all copies of $H$ to a vertex, we get a copy of graph $G$). This construction is interesting because it may yield graphs with distinguishing number greater than 2. In the talk I will describe the Sierpiński products and list some of their basic properties, which may be useful to answer the open question(s) about the distinguishing number of Sierpiński products.

For a group $G$ and an inverse-closed subset $S$ of $G$, the Cayley graph $\mathrm{Cay}(G;S)$ is defined to have the elements of $G$ as its vertices, with vertices $g$ and $gs$ adjacent whenever $s \in S$. Note that $s$ and $s^{-1}$ lead to the same collection of edges under this definition. Thus, the natural edge-colouring arises by assigning to each pair $\{s,s^{-1}\}$ a distinct colour, and associating this colour with all edges that arise from $\{s, s^{-1}\}$ (that is, this colour is assigned to the edges between $g$ and $gs$ for every $g \in G$). By its definition, any Cayley graph admits a regular group of automorphisms isomorphic to $G$, since left-multiplying every element of $G$ by any fixed $g \in G$ is a permutation of the vertices that preserves the adjacency relation. Furthermore, this regular group also preserves the natural edge colouring described above. However, it can be the case that a Cayley graph has no other automorphisms that preserve the natural edge colouring, or that the only other automorphisms that preserve the natural edge colouring are group automorphisms. I will discuss this situation and some of the work that has been done on it.

A permutation group is semiprimitive if each normal subgroup is transitive or semiregular. This class of groups generalises the classes of primitive and quasi primitive groups, and has attracted most interest due to problems in algebraic graph theory. In this talk, I will survey some recent joint work with Kyle Rosa and Cheryl Praeger where we explored the question of whether certain bounds (in terms of degree) that hold for primitive groups could be adapted to the class of semiprimitive groups. Motivated by ``useful'' results for the class of primitive groups, we investigated bounds on order, base size and fixity. In general, we found that similar bounds hold, or, one can establish even stronger bounds if we exclude certain families of primitive groups.

The distinguishing number of a permutation group $G \leq \Sym(X)$ is the smallest number of colours required to colour the points of $X$ such that only the identity of $G$ preserves the colouring. The distinguishing number of a graph, in the traditional sense, is simply the distinguishing number of its automorphism group. Seress proved that every primitive group of degree $n$ other than $\Alt(n)$ and $\Sym(n)$ has distinguishing number 2, except for a short list of known examples (with distinguishing number 3 or 4). In this talk, I will overview previous work on the distinguishing number of groups, before discussing recent joint work with Alice Devillers and Luke Morgan on the distinguishing number of semiprimitive groups. I will highlight the application of our result to graphs.

This talk is being given on behalf of Primož Potočnik (Ljubljana), at the request of Wilfried Imrich. Much of it is joint work between Primož Potočnik and Florian Lehner, Pablo Spiga and Gabriel Verret. The fixicity of a a graph $\Gamma$ is defined as the largest number of fixed vertices of a non-trivial automorphism of $\Gamma$. I will explain this notion (with many examples), and explain how some interesting bounds on the fixicity have been obtained for the classes of vertex-transitive and arc-transitive 3-valent graphs.

In 2011 Ellingham and Schroeder introduced the idea of a "distinguishing partition" for an action of a group $\Gamma$ on a set $X$, namely a partition of $X$ that is preserved by no nontrivial element of $\Gamma$. As a special case, a distinguishing partition of a graph is a partition of the vertex set that is preserved by no nontrivial automorphism. Distinguishing partitions are weaker at breaking symmetry than distinguishing colourings, and not every graph has a distinguishing partition. We discuss our work with Schroeder which linked distinguishing partitions of complete equipartite graphs with asymmetric uniform hypergraphs. We find a function $f(n)$ such that a distinguishing partition for $K_{m(n)}=K_{n,n,\ldots,n}$, or equivalently for the wreath product action $S_n \wr S_m$, exists if and only if $m\geq f(n)$. We also discuss some other work on distinguishing partitions of complete multipartite graphs by Michael Goff.

We introduce the distinguishing numbers of partially ordered sets. This study has given us the opportunity to apply classic results in poset theory to obtain results about this parameter. We present both an elementary proof of the distinguishing number of divisibility lattices and a more general result that employs Birkoff's Fundamental Theorem of Distributive Lattices. In other distinguishing bounds, we use a fundamental result about straight line embeddings of ranked planar posets with a minimum element and a maximum element to find bounds on planar posets. Coauthor: Karen L. Collins

We introduce two distinguishing chromatic numbers of partially ordered sets, one based on incomparability and the other on comparability. This study has given us the opportunity to apply classic results in poset theory to obtain results about these parameters. We use Dilworth's Theorem to obtain a bound for the parameter based on incomparability. In distinguishing chromatic bounds based on comparability, we use the proof of Birkoff's Fundamental Theorem of Distributive Lattices. In contrast, we provide a bound for the Boolean lattice, $B_n$, based on its high degree of symmetry.

The symmetry of a discrete structure can easily be altered (or in the case of maps, destroyed) by changing just a small part of it. But there are other contexts where a large degree of symmetry is desirable without achieving the maximum possible symmetry, for example with maps and polytopes that are maximally symmetric by orientation-preserving automorphisms but are chiral (admitting no refections). In a similar vein, sometimes restricting the symmetry can help achieve things that are either impossible or difficult when full symmetry is assumed. I will outline a few recent discoveries that explain and illustrate these phenomena.

Many results on distinguishing finite and locally finite graphs have easy extensions to graphs without degree restrictions or to uncountable graphs. Some other results are very difficult to generalize, and many hopelessly difficult. The talk presents a selection of results and problems for graphs without degree restrictions or uncountable graphs, and how they relate to the locally finite case. It concludes with challenging, interesting problems.