Summer Seminar on Symmetry, Computer Algebra, Algebraic Graph Theory and beyond ^*

Informal introduction to the first part of the background facts from AGT. The presentation will go around a handful or so of simple striking examples in a few different languages: permutations, graphs and their diagrams, matrices, relations.

The metric dimension of a graph is the smallest number of vertices, called a metric basis, that can uniquely identify every other vertex in the graph based on its distances to the metric basis. A unicyclic graph is a graph that contains exactly one cycle. In our talk, we focus on unicyclic graphs with metric dimension 2. We introduce the operation of knitting as a tool to characterize all such graphs.

An educational lecture, in which main concepts are introduced and discussed on a number of simple examples. Oriented on the audience on the level of Master students, and even strong Bachelor students, who are interested in combinatorics and symmetries of relational structures.

Motivated by the problems appearing in the theory of experimental designs, Bose and Mesner introduced a special class of matrix algebras, known nowadays as Bose-Mesner algebras of symmetric association schemes. In the same year Shah published the paper where he proposed a more general idea: to replace the standard matrix product with the Jordan product. So, in fact, he introduced the objects called later Jordan schemes by Cameron. While the ideas of Bose and Mesner led to a new direction in algebraic graph theory called later algebraic combinatorics by Bannai and Ito, Shah’s idea was not developed at all. Only in 2004 Shah’s approach was analyzed by Bailey. She proved several basic facts about Jordan schemes and observed that the symmetrization of any association scheme is a Jordan scheme, which led to the following question posed by Cameron in 2001: ”Are there any others?”. Here we give an affirmative answer to this question by providing several infinite series of proper Jordan schemes, i.e. those which do not appear via symmetrization of association schemes. In our talk we present basic facts about Jordan schemes and provide several constructions of Jordan Schemes.

The article deals with the problem of finding vertex-minimal graphs with a given automorphism group. We exhibit two undirected 16-vertex graphs having automorphism groups A₄ and A₅. It improves Babai’s bound for A₄ and the graphical regular representation bound for A₅. The graphs are constructed using projectivisation of the vertex-face graph of the icosahedron.

We discuss Hamming spaces, their connections with graphs, their isometry groups, and generalizations to the infinite case. These generalizations, known as periodic Hamming spaces, were first studied by P. J. Cameron and S. Tarzi in 2008. In particular, they represented periodic Hamming spaces as spaces of finite unions of half-open subintervals of the interval [0, 1). We propose an alternative representation, viewing them as spaces of clopen subsets of the boundaries of spherically homogeneous rooted trees. Using this approach, we describe the structure of the isometry group of the periodic Hamming space and its completion, thereby answering the question posed by P. J. Cameron and S. Tarzi regarding the description of these isometry groups.

Using a computer we constructed all coherent configurations of orders no more than 15 (up to isomorphism). One result of this enumeration is discovery of (the unique) non-Schurian coherent configuration of order 14 [2]. All coherent configurations of orders up to 13 are Schurian, so this is the smallest non-Schurian coherent configuration.

This is about an approach to design administrative divisions as solutions of vertex k-center problem (minimax facility location problem) using the road graph of a country or other territory.

Which 4-manifolds admit a flag-no-square triangulation? Just one family of examples, described by Przytycki and Swiatkowski, was known. We introduce two “gluing” operations which allow us to construct new examples of flag-no-square 4-manifolds. Furthermore, our construction technique may be of independent interest: we take copies of a single such 4-manifold (which we know very little about) and carefully apply our operations to obtain 4-manifolds with many different flag-no-square triangulations. The idea behind our construction technique is to realize geometrically the cycle structure of a permutation.

Based on joint work with Eran Nevo and Gangotryi Sorcar.

The problem of representing logical implications and proofs by mathematical objects is considered. The need to develop a theory for measuring value and complexity of mathematical implications and proofs is discussed including motivations, benefits and implementation problems. Examples of mathematical considerations are given. Arguments supporting such an advance and its applications in mathematical research guidance and publication standards are given.

We recall the problem of All-Pairs Shortest Path (APSP). A known conjecture states there exists no ε > 0 s.t. APSP can be computed in Õ(n^3−ε) runtime. To overcome this, the problem of All-Pairs Approximate Shortest Paths (APASP) has been studied for nearly three decades. Our main focus is APASP with an additive upper-bound and their comparison between weighted and unweighted graphs. Additionally, we will review APASP with a nearly-additive approximation and a multiplicative approximation.

Starting from a computer-generated example of a transitive Latin square graph over a proper loop we describe a computer-free interpretation of this specific strongly regular graph. Moreover, using this interpretation we generalize the result to an infinite series of similar examples.

A loop L of order n naturally defines a 3-net of order n, that is an incidence structure N(L), which consists of n² points and three parallel classes of lines, each class contains n lines of size n. The collineation group Σ(L) is the full group of collineations of the net N(L). The group Σ(L) has a normal subgroup T(L) of index at most 6, which maps each class of parallel lines into itself. A loop L is called a proper loop if T(L) contains a regular subgroup of degree n2, while the main class of L does not contain a group. We prove that for each odd prime p, there exists (up to isomorphism) exactly one main class of proper loops of order 2p. This is a joint project with M. Klin.

The analysis of common mistakes and stylistic issues in writing academic articles in mathematics. (The lecture is oriented on a very wide audience of mathematicians. Everybody from Math and CS departments is very welcome.)

Consideration of a cornerstone of modern numerical linear algebra. Attempt to discuss it through five lenses: axiomatic, variational, regularization and spectral perspectives, as well as combinatorial invariants at AGT.

Consideration of the generalization of Dynkin diagrams, that allows cycles of even length. Discussion of a few main theorems with the illustration on several examples of concrete linkage systems.