Schedule for: 18w5050 - Symmetry Breaking in Discrete Structures

Arriving in Oaxaca, Mexico on Sunday, September 16 and departing Friday September 21, 2018
Sunday, September 16
14:00 - 23:59 Check-in begins (Front desk at your assigned hotel)
19:30 - 22:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
20:30 - 22:30 Informal gathering (Hotel Hacienda Los Laureles)
Monday, September 17
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:15 - 09:30 Introduction and Welcome (Conference Room San Felipe)
09:30 - 10:30 Thomas Tucker: Symmetry Breaking
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$.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:50 Florian Lehner: Distinguishing numbers of infinite graphs with bounded degrees
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
(Conference Room San Felipe)
12:00 - 12:50 Gabriel Verret: Distinguishing number of vertex-transitive graphs of valency 4
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.
(Conference Room San Felipe)
12:50 - 13:00 Group Photo (Hotel Hacienda Los Laureles)
13:00 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:10 Rafal Kalinowski: Bounds for the distinguishing index of finite graphs
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
(Conference Room San Felipe)
15:15 - 15:55 Mariusz Wozniak: Distinguishing vertices of a graph: automorphisms and palettes
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.
(Conference Room San Felipe)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:00 Mohammad Hadi Shekarriz: The number of different distinguishing colorings of a graph
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
(Conference Room San Felipe)
17:05 - 17:35 Saeid Alikhani: Symmetry breaking in maximal outerplanar, regular and Cayley graphs
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
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Tuesday, September 18
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 10:00 Laszlo Babai: My view on symmetry breaking, part 1 (Conference Room San Felipe)
10:00 - 10:30 Coffee Break (Conference Room San Felipe)
10:30 - 11:20 Laszlo Babai: Symmetry breaking - my view, part 2 (Conference Room San Felipe)
11:30 - 12:20 Laszlo Babai: Efficient symmetry breaking for graphs via coherent configurations: the emergence of the Johnson graphs (Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:20 Bohdan Kivva: Minimal degree of the automorphism group of primitive coherent configurations
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.
(Conference Room San Felipe)
15:30 - 16:00 Coffee Break (Conference Room San Felipe)
16:00 - 16:50 Bohdan Kivva: The Sun--Wilmes classification of primitive coherent configurations with many automorphisms
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.
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Wednesday, September 19
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:40 Claude Laflamme: Symmetry Breaking of Countable Homogeneous Structures
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.
(Conference Room San Felipe)
09:45 - 10:25 Thomas Lachmann: The costs of symmetry breaking vertex-transitive cubic graphs
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.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:40 Svenja Hüning: On the distinguishing number of locally finite trees
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.
(Conference Room San Felipe)
11:45 - 12:10 Sara Sabrina Zemljič: Distinguishing Sierpiński products of graphs
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.
(Conference Room San Felipe)
12:15 - 13:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
13:30 - 19:00 Excursion (Monte Alban)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Thursday, September 20
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:50 Joy Morris: Using the natural edge colouring to limit symmetry in Cayley graphs
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.
(Conference Room San Felipe)
10:00 - 10:30 Coffee Break (Conference Room San Felipe)
10:30 - 11:20 Luke Morgan: Bounds and invariants of semiprimitive groups
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.
(Conference Room San Felipe)
11:30 - 12:20 Scott Harper: The distinguishing number of semiprimitive 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.
(Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:10 Marston Conder: Fixicity of 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.
(Conference Room San Felipe)
15:15 - 15:55 Mark Ellingham: Distinguishing partitions and asymmetric uniform hypergraphs
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.
(Conference Room San Felipe)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:00 Ann Trenk: The Distinguishing Number and Posets, Part I
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
(Conference Room San Felipe)
17:05 - 17:35 Karen Collins: The Distinguishing Number and Posets, Part II
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.
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
20:30 - 22:00 Problem Session (Conference Room San Felipe)
Friday, September 21
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:50 Marston Conder: Restricting symmetry (rather than breaking it)
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.
(Conference Room San Felipe)
10:00 - 10:30 Wilfried Imrich: A view of uncountable graphs
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.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
12:00 - 14:00 Lunch (Restaurant Hotel Hacienda Los Laureles)