**August 06-19, 2018** - Novosibirsk, Russia

The scientific program of the G2R2-conference consists of 50-minutes invited talks and 25-minutes contributed talks with no parallel sessions.

All accepted abstracts are published in the book of abstracts

The topics of the G2R2-conference are widely presented by different branches of mathematics such as graph theory, group theory, geometry, topology, algebraic combinatorics, algebraic graph theory, coding theory and designs, representation theory of groups, computer science, discrete mathematics.

**Title:** Groebner-Shirshov bases for groups, semigroups, categories, and Lie algebras.

**Abstract:** What is now called Groebner and Groebner-Shirshov (GS) bases method was initiated independently
by A.I.Shirshov (1962), H.Hironaka (1964) and B.Buchberger (1965). We will emphasize on GS bases for Coxeter
and braid groups, plactic monoid, simplicial and cyclic categories, semisimple Lie algebras, Shirshov-Cartier-Cohn
counter examples. This is joint work with Yuqun Chen.

Sobolev Institute of Mathematics, Russia

**Groebner-Shirshov bases for groups, semigroups, categories, and Lie algebras**

**Title:** The smallest eigenvalues of Hamming, Johnson and other graphs.

**Abstract:** The smallest eigenvalue of graphs is closely related to other graph parameters such as
the independence number, the chromatic number or the max-cut. In this talk, I will describe the
well connections between the smallest eigenvalue and the max-cut of a graph that have
motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate
the smallest eigenvalue of Hamming and Johnson graphs. I will describe our proofs of a
conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs
and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and
mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and
Matt McGinnis.

University of Delaware, USA

**The smallest eigenvalues of Hamming, Johnson and other graphs**

**Title:** Cyclically *5*-edge connected graphs, Fullerenes and Pogorelov polytopes.

**Abstract:** In this talk, we discuss fruitful connections between classical and recent results of the
graph theory, the polytope theory, hyperbolic geometry and algebraic topology.

A *3*-valent planar *3*-connected graph is *cyclically 5-edge connected* (*c5-connected*) if
it has at least *5* vertices and no two circuits can be separated by cutting fewer than
*5* edges. A graph is *strongly cyclically 5-edge connected (c*5-connected)* if in addition
any separation of the graph by cutting *5* edges leaves one component that is a simple
circuit of *5* edges. These notions are well-known and play an important role in the graph
theory. By the result of G.D. Birkhoff (1913), the famous Four Colour Theorem for
planar graphs can be reduced to the class of *c*5*-connected graphs. In 1974 D. Barnette
and J.W. Butler shown independently that any *c5*-connected graph can be obtained from
the graph of dodecahedron by a simple set of operations. An analogous description for
*c*5*-connected graphs was found by D. Barnette in 1977. Later a part of this result was
rediscovered by T. Inoue (2008) in the context of hyperbolic geometry.

There is a remarkable geometric characterisation of *c5*-connected graphs due to
A.V. Pogorelov (1967) and E.M. Andreev (1970): a combinatorial *3*-polytope can be realised in
Lobachevsky space as a bounded polytope with right dihedral angles if and only if
its graph is *c5*-connected. We refer to such combinatorial polytopes as *Pogorelov polytopes*
(*𝒫-polytopes*). Generalising the classical construction of Löbell (1931), A.Yu. Vesnin in
1987 described a way to produce a hyperbolic *3*-manifold from any Pogorelov polytope by
endowing it with an additional structure related to the hyperbolic reflection group (this
structure consists of * ℤ/2*-vectors assigned to the facets of the polytope). An important
example of this additional structure arises from the Four Colour Theorem. A.Yu. Vesnin
also conjectured that hyperbolic manifolds arising from

According to T. Doslic (2003), the class of *𝒫*-polytopes contains fullerenes, i.e. simple
*3*-polytopes with only *5*- and *6*-gonal faces. V.M. Buchstaber and N.Yu. Erokhovets
(2017) obtained the results describing the class of *𝒫*-polytopes constructively:

(1) Any *𝒫*-polytope except for the *k*-barrels can be obtained from the *5*- or the *6*-barrel
by a sequence of two-edges-truncations and connected sums with *5*-barrels along *5*-gons.

(2) Any fullerene except for the 5-barrel and the *(5, 0)*-nanotubes can be obtained
from the *6*-barrel by a sequence of *(2, 6; 5, 5)*-, *(2, 6; 5, 6)*-, *(2, 7; 5, 6)*-, *(2, 7; 5, 5)*-
truncations such that all intermediate polytopes are either fullerenes or *𝒫*-polytopes with
facets *5*-, *6*- and at most one additional *7*-gon adjacent to a *5*-gon.

Steklov Mathematical Institute, Moscow State University, Russia

**Cyclically 5-edge connected graphs, Fullerenes and Pogorelov polytopes**

** Title:** Applications of semidefinite programming, symmetry, and algebra to graph
partitioning problems.

**Abstract:** We will present semidefinite programming (SDP) and eigenvalue bounds for several graph partitioning
problems.

The graph partition problem (GPP) is about partitioning the vertex set of a graph into a given number
of sets of given sizes such that the total weight of edges joining different sets - the cut - is optimized.
We show how to simplify known SDP relaxations for the GPP for graphs with symmetry so that they
can be solved fast, using coherent algebras.

We then consider several SDP relaxations for the max-*k*-cut problem, which is about partitioning the
vertex set into *k* sets (of arbitrary sizes) such that the cut is maximized. For the solution of the weakest
SDP relaxation, we use an algebra built from the Laplacian eigenvalue decomposition - the Laplacian
algebra - to obtain a closed form expression that includes the largest Laplacian eigenvalue of the graph.
This bound is exploited to derive an eigenvalue bound for the chromatic number of a graph. For regular
graphs, the new bound on the chromatic number is the same as the well-known Hoffman bound. We
demonstrate the quality of the presented bounds for several families of graphs, such as walk-regular
graphs, strongly regular graphs, and graphs from the Hamming association scheme.

If time permits, we will also consider the bandwidth problem for graphs. Using symmetry, SDP, and
by relating it to the min-cut problem, we obtain best known bounds for the bandwidth of Hamming,
Johnson, and Kneser graphs up to 216 vertices.

Tilburg University, The Netherlands

**Applications of semidefinite programming, symmetry, and algebra to graph
partitioning problems**

**Title:** On mixed Moore-Cayley graphs.

**Abstract:** A graph is said to be mixed if it contains both undirected edges
and directed arcs. In this talk, we give a brief survey on the topic and
describe an algebraic approach based on the socalled Higman's method in
the theory of association schemes, which enables us to rule out the
existence
of mixed Moore-Cayley graphs of certain orders.

** Title:** Several results on cliques in strongly regular graphs.

**Abstract:** In this talk we discuss recent results related to cliques and equitable partitions into cliques in strongly regular graphs. The talk is based on joint work with Rosemary Bailey, Peter Cameron, Rhys Evans, Alexander Gavrilyuk, Vladislav Kabanov, Dmitry Panasenko, Leonid Shalaginov, Alexander Valuzhenich.

Shanghai Jiao Tong University, China, Krasovskii Institute of Mathematics and Mechanics, Russia

**Several results on cliques in strongly regular graphs**

**Title:** *PC*-polynomial on graph and its largest root.

**Abstract:** Given a graph *G*, we are interested on the properties of *β(G)*, the largest root of *PC*-polynomial, a polynomial with integer coefficients depending on the numbers of cliques in *G*.
The number *β(G)* is deeply related to partially commutative algebras, Lovász local lemma and
matrices. We find a graph on which *β(G)* reaches the largest value if the numbers *n = |V|* and *k =
|E|* are fixed. We find the upper bound on *β(G): β(G) < n - (0.941k)/n* for *n>>1*. We obtain new
versions of Lovász local lemma. We investigate the analogues of Nordhaus-Gaddum
inequalities for *β(G)*. Applying random graphs, we prove that the average value of *β(G)* on
graphs with *n* vertices asymptotically equals *≈ 0.672n*.

University of Vienna, Austria, Sobolev Institute of Mathematics, Russia

*PC*-polynomial on graph and its largest root

**Title:** On directed strongly regular graphs.

**Abstract:** A directed strongly regular graph (DSRG) with parameters (*n,k,t,λ,μ*) is a regular directed
graph on *n* vertices with valency *k* such that every vertex is incident with *t* undirected edges; the
number of directed paths of length *2* directed from a vertex *x* to another vertex *y* is *λ*, if there is an
arc from *x* to *y* and *μ* otherwise. In the talk we present a few constructions of DSRGs.

**Title:** Combinatorial curvature for infinite planar graphs.

**Abstract:** For any planar graph, its ambient space *S ^{2}* or

**Title:** The Terwilliger algebra of a tree.

**Abstract:** Let *Γ* be a finite connected simple graph. Let *X* denote the vertex set of *Γ*
and *V = ⊕ _{x∈X}ℂx* the standard module, i.e., the vector space for which

In this talk, we discuss the Terwilliger algebra of a tree. Precisely speaking, we assume

This talk is based on joint work with Shuang-Dong Li, Jing Xu, Masoud Karimi and Yizheng Fan. We acknowledge that Jack Koolen conjectured: For almost all finite connected simple graphs,

**Title:** Locally Projective Graphs of *GF*(2)-type.

**Abstract:** Consider a connected graph Γ with a family 𝓛 of complete subgraphs (called lines), and possessing a
vertex-transitive automorphism group *G* preserving 𝓛. It is assumed that for every vertex *x* of Γ there
is a *G*(*x*)-bijection *π*(*x*) between the set 𝓛(*x*) of lines containing *x* and the point-set of a projective
*GF*(2)-space. There is a number of important examples of such *locally projective graphs of GF*(2)*-type*
where both classical and sporadic simple groups appear among the automorphism groups. The ultimate
goal is to classify these graphs up to their local isomorphisms. This was achieved by V.I. Trofimov,
S.V. Shpectorov and the present author for the case where the lines are of size *2*. An approach of
extending the classification to the case where the lines are of size *3* will be discussed in the lecture.

**Title:** Recent progress on graphs with fixed smallest eigenvalue.

**Abstract:** In the 1970's Cameron et al. showed that connected graphs with smallest eigenvalue at
least *-2* are generalized line graphs, if the number of vertices is at least *36*. In this talk I will
discuss recent progress on graphs with fixed smallest eigenvalue.

University of Science and Technology of China (USTC)

**Recent progress on graphs with fixed smallest eigenvalue**

**Title:** Counting Colorings of Cubic Graphs via a Generalized Penrose Bracket

**Abstract:** A *proper edge coloring* of a cubic graph is a coloring of the edges of the
graph using three colors so that three distinct colors appear at each node of the graph.
It is well-known that the four-color theorem is equivalent to the statement that every
isthmus-free planar cubic graph has at least one proper edge coloring. Roger Penrose
gave a graphical recursion formula, *the Penrose Bracket*, that can be seen to count the number
of proper edge colorings of a planar cubic graph. The Penrose Bracket does not count the number
of colorings of non-planar cubic graphs. For example, the original Penrose Bracket vanishes on
the graph *K _{3,3}* while this graph has

University of Illinois, USA

**Counting Colorings of Cubic Graphs via a Generalized Penrose Bracket**

**Title:** Skew-morphisms and regular Cayley maps for dihedral groups.

**Abstract:** Let *G* be a finite group having a factorisation *G = AB* into subgroups *A* and
*B* with *B* cyclic and *A ∩ B = 1*, and let *b* be a generator of *B*. The associated
skew-morphism is the bijective mapping *f : A → A* well defined by the equality
*baB = f(a)B* where *a ∈ A*. The motivation of studying skew-morphisms comes
from topological graph theory. A Cayley map for the group *A* is an embedding
of a Cayley graph of *A* into an orientable surface such that a chosen global
orientation induces at each vertex the same cyclic permutation of generators. If
the group of map automorphisms is regular on arcs, the map is called regular. It
is well-known that regular Cayley maps for *A* arise from those skew-morphisms
of *A* that admit a generating orbit which is closed under taking inverses. Regular
Cayley maps for cyclic groups were classified by Conder and Tucker (2014). In
this talk, we discuss regular Cayley maps for dihedral groups. This is joint work with Young Soo Kwon.

University of Primorska, Slovenia

**Skew-morphisms and regular Cayley maps for dihedral groups**

**Title:** Delta-matroids and Vassiliev invariants.

**Abstract:** Vassiliev (finite type) invariants of knots can be
described in terms of weight systems. These are functions on chord diagrams
satisfying so-called 4-term relations. There is also a natural way to define
4-term relations for abstract graphs, and graph invariants satisfying these
relations produce weight systems: to each chord diagram its intersection graph
is associated. The notion of weight system can be extended from chord diagrams,
which are orientable embedded graphs with a single vertex, to embedded graphs
with arbitrary number of vertices that can well be nonorientable. These embedded graphs
are a tool to describe finite order invariants of links: the vertices of a graph
are in one-to-one correspondence with the link components. We are going to describe
two approaches to constructing analogues of intersection graphs for embedded graphs
with arbitrary number of vertices. One approach, due to V. Kleptsyn and E. Smirnov,
assigns to an embedded graph a Lagrangian subspace in the relative first homology
of a 2-dimensional surface associated to this graph. Another approach, due to S.
Lando and V. Zhukov, replaces the embedded graph with the corresponding delta-matroid,
as suggested by A. Bouchet in 1980's. In both cases, 4-term relations are written out,
and Hopf algebras are constructed. Vyacheslav Zhukov proved recently that the two
approaches coincide.

National Research University Higher School of Economics, Skolkovo Institute of Science and Technology, Russia

**Delta-matroids and Vassiliev invariants**

**Title:** Recent developments in Majorana representations of the symmetric groups.

**Abstract:** We will present some recent developments in Majorana representations of the
symmetric groups obtained jointly with Clara Franchi and Alexander Ivanov.

University of Udine, Italy

**Recent developments in Majorana representations of the symmetric groups**

**Title:** Around symmetries of vertex operator algebras.

**Abstact:** A vertex operator algebra (VOA) is a vector space equipped with a countably many binary operations subject to some axioms,
and interesting groups such as the Monster simple group appear as automorphism groups of VOAs. In this talk, I will survey various
results related to the automorphism groups of VOAs focusing on those which arose from my own activities from late 90's to 00's. The
topics include Matsuo-Norton trace formula, conformal design, and Matsuo algebra.

**Title:** Symmetries and Combinatorics of Finite Antilattices.

**Abstract:** Antilattices, known also as rectangular quasilattices,
form one of the simplest varieties of non-commutative lattices. In this talk we will
explore the combinatorics of finite antilattices via their generating matrices.
We will also investigate their substructures, congruences, symmetries, and in particular,
their connection with orthogonal latin squares. The inspiration comes from a paper by
Jonathan Leech (2005) on magic squares and simple quasilattices. This is work in progress with Karin Cvetko Vah.

University of Ljubljana, University of Primorska, Slovenia

**Symmetries and Combinatorics of Finite Antilattices**

**Title:** Cliques and colourings in GRAPE.

**Abstract:** Many problems in discrete mathematics and finite geometry boil down to the problem
of finding or classifying cliques of a given size in some graph, which often has a large group of
automorphisms. The GRAPE package for GAP provides extensive facilities to exploit graph
symmetries for clique finding and classification. Recently, I have used these facilities to develop
programs (for inclusion in GRAPE) which exploit graph symmetry for the proper vertex-
colouring of a graph and the determination of its chromatic number. I will talk about this recent
development, and give concrete examples and applications of the clique and colouring
machinery in GRAPE, so that you can apply this machinery to your own research problems.

**Title:** On 2-closures of primitive solvable permutation groups.

**Abstract: **Denote by *Ω* the set *{1, . . . , n}*, by *Sym _{n}* the symmetric group of degree

Sobolev Institute of Mathematics, Russia

**On 2-closures of primitive solvable permutation groups**

**Title:** Combinatorial Games on Graphs, Coxeter-Dynkin diagrams, and the geometry of root systems.

**Abstract:** The Coxeter-Dynkin graphs, particularly the ADE graphs and their affine variants,
feature prominently in dozens of topics in group theory, Lie algebras, combinatorics and many other areas.
Explaining this ubiquity is a tantalising problem. In this talk we consider the graphs as central,
and explore two remarkable games, the Numbers game and the Mutation game, that generate quite a lot of associated
mathematics around ADE diagrams. Rich lattices and posets will figure, the geometry of root systems and connections
with representation theory will appear, and we will also present an intriguing challenge.

Wildberger

University of New South Wales, Australia

**Combinatorial Games on Graphs, Coxeter-Dynkin diagrams, and the geometry of root systems**

**Title:** Character degree graphs of finite groups.

**Abstract:** Character degree graphs of finite groups have been investigated intensively in recent
years. We will report some new developments.

**Abrosimov Nikolay**, Sobolev Institute of Mathematics, Novosibirsk State University, Russia

**Aljohani Mohammed**, Taibah University, Saudi Arabia

**Avgustinovich Sergey**, Sobolev Institute of Mathematics, Russia

**Baykalov Anton**, The University of Auckland, New Zealand

**Berikkyzy Zhanar**, University of California, USA

**Bernard Matthew**, University of California, USA

**van Bevern Rene**, Novosibirsk State University, Sobolev Institute of Mathematics, Russia

**Bokut Leonid**, Sobolev Institute of Mathematics, Russia

**Brodhead Katie**, Florida A&M University, USA

**Buchstaber Victor**, Steklov Mathematical Institute, Moscow State University, Russia

**Buturlakin Alexander**, Sobolev Institute of Mathematics, Russia

**Chanchieva Marina**, Gorno-Altaisk State University, Russia

**Chen Sheng**, Harbin Institute of Technology, China

**Chen Huye**, China Three Gorges University, China

**Cho Eun-Kyung**, Pusan National University, South Korea

**Churikov Dmitry**, Novosibirsk State University, Russia

**Cioabă Sebastian M. **, University of Delaware, USA

**Dai Yi**, Harbin Institute of Technology, China

**van Dam Edwin**, Tilburg University, The Netherlands

**Dedok Vasily**, Sobolev Institute of Mathematics, Russia

**Dobrynin Andrey**, Sobolev Institute of Mathematics, Russia

**Dogra Riya**, Shiv Nadar University, India

**Drozdov Dmitry**, Gorno-Altaisk State University, Russia

**Dudkin Fedor**, Novosibirsk State University, Sobolev Institute of Mathematics

**El Habouz Youssef**, University ibn Zohr, Morocco

**Erokhovets Nikolai**, Lomonosov Moscow State University, Steklov Mathematical Institute, Russia

**Evans Rhys**, Queen Mary University of London, UK

**Fadeev Stepan**, Novosibirsk State University, Russia

**Fu Zhuohui**, Northwestern Polytechnical University, China

**Fuladi Niloufar**, Sharif University of Technology, Iran

**Galt Alexey**, Novosibirsk State University, Sobolev Institute of Mathematics, Russia

**Gavrilyuk Alexander**, Pusan National University, South Korea

**Glebov Aleksey**, Sobolev Institute of Mathematics, Novosibirsk State University, Russia

**Golmohammadi Hamid Reza**, University of Tafresh, Iran

**Goncharov Maxim**, Novosibirsk State University, Russia

**Gonzalez Yero Ismael**, Universidad de Cadiz - Escuela Politecnica Superior, Spain

**Gorshkov Ilya**, Sobolev Institute of Mathematics, Novosibirsk, Russia

**Goryainov Sergey**, Shanghai Jiao Tong University, China, Krasovskii Institute of Mathematics and Mechanics, Russia

**Grechkoseeva Maria**, Novosibirsk State University, Sobolev Institute of Mathematics

**Gubarev Vsevolod**, University of Vienna, Austria, Sobolev Institute of Mathematics, Russia

**Gyürki Štefan**, Matej Bel University, Slovakia

**He Yunfan**, University of Wisconsin-Madison, USA

**Hua Bobo**, Fudan University, China

**Ilyenko Christina**, Ural Federal University, Russia

**Ito Keiji**, Tohoku University, Japan

**Ito Tatsuro**, Anhui University, China

**Ivanov Alexander A.**, Imperial College London, UK

**Jin Wanxia**, Northwestern Polytechnical University, China

**Jing Naihuan**, North Carolina State University, USA

**, University of Southampton, UK
**

© website design by Rogalskaya Kristina