Raziskovalni matematični seminar - Arhiv

A bipartite biregular (n,m;g)-graph G is a bipartite graph of even girth g having the degree set {n,m} and satisfying the additional property that the vertices in the same partite set have the same degree.
An  (n,m;g)-bipartite biregular cage is a bipartite biregular (n,m;g)-graph of minimum order. In our talk, we present lower bounds on the orders of bipartite biregular (n,m;g)-graphs, and call the graphs that attain these bounds bipartite biregular Moore cages.

In parallel with the well-known classical results relating the existence of k-regular Moore graphs of even girths g = 6,8 and 12 to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of S(2,k,v)-Steiner systems  yields the existence of  bipartite biregular (k,\frac{v-1}{k-1};6)-Moore cages. Moreover, in the special case of Steiner triple systems (i.e., in the case k=3), we completely solve the problem of the existence of (3,m;6)-bipartite biregular cages for all integers m greater or equal than 4. Considering girths higher than 6 and prime powers s, we relate the existence of generalized polygons (quadrangles, hexagons and octagons) with the existence of (n+1,n^2+1;8), (n+1,n^3+1;12), and (n+1,n^2+1;16)-bipartite
biregular Moore cages, respectively. Using this connection, we derive improved upper bounds for the orders of bipartite biregular cages of girths 8, 12 and 14.

This is joint work with Alejandra Ramos Rivera, Slobodan Filipovski and Gabriela Araujo Pardo.

Given a graph G, a minimal separator in G is a subset of vertices that separates some non-adjacent vertex pair a, b and is inclusion-minimal with respect to this property (separation of a and b). Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators. Graph classes having polynomially bounded number of minimal separators are called tame. Several well-known graph classes are tame, including chordal graphs, permutation graphs, circular-arc graphs, and circle graphs. We perform a systematic study of the question which classes of graphs defined by small forbidden induced subgraphs are tame. We focus on sets of forbidden induced subgraphs with at most four vertices and obtain a complete dichotomy.

Joint work with Martin Milanič.

It is known that a Cayley digraph Cay(A, S) of an abelian group A is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup B≤A such that S\B is a union of cosets of B in A. We generalize this result to Cayley graphs Cay(G, S) of nonabelian groups G by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup H≤G such that S\H is a union of double cosets of H in G. This result is proven in the more general situation of a coset digraph. We will also discuss implications of this result to coset digraphs. This is joint work with Rachel Barber of Mississippi State University.

11:15 – 12:00: FAMNIT-VP1

Lecturer: Martin R Bridson FRS, 8ECM Prize Committee Chair (University of Oxford)

Title: Hyperbolic geometry: where battered gems retain their full beauty

Abstract: Hyperbolic geometry provides a rich setting in which many rigidity phenomena emerge. In this talk for a general audience, I shall present several different types of rigidity phenomena, from Mostow’s classical rigidity theorem to generalizations involving the large-scale geometry of groups and spaces. I shall also explain why hyperbolicity is so ubiquitous. I shall end by sketching how a newly discovered rigidity phenomenon in hyperbolic geometry can be used to settle an old question concerning the difficulty of identifying an infinite group by studying its actions on finite objects.

12:00 – 12:45: FAMNIT-VP1

Lecturer: Maria J. Esteban, 8ECM Scientific Committee Chair (CEREMADE (CNRS UMR n° 7534), PSL Research University, Université Paris-Dauphine)

Title: Best constants for functional inequalities and spectral estimates for Schrödinger operators

12:45 – 13.30: Lunch Break (Catering)

13:30 – 14.15: FAMNIT-VP1

Lecturer: Volker Mehrmann, President, European Mathematical Society (TU Berlin)

Title: The distance to stability and the distance to instability of dynamical systems

Abstract: The analysis of the stability of a dynamical system is an essential question of mathematics. An important class of control systems is that of dissipative Hamiltonian systems that arise in all areas of science and engineering. When the system is linearized around a stationary solution one gets a linear dissipative Hamiltonian system. Despite the fact that the system looks very unstructured at first sight, it has remarkable properties. Stability and passivity are automatic, Jordan structures for purely imaginary eigenvalues, eigenvalues at infinity, and even singular blocks in the Kronecker canonical form are very restricted and furthermore the structure leads to fast and efficient iterative solution methods for associated linear systems. We discuss the distance to instability under structure preserving perturbations and also the smallest distance to the nearest stable system. An even harder problem is the distance to the nearest singular or ill-posed problem. While this in general open, for the class of dissipative Hamiltonian systems we present a simple classification. This is joint work with Christian Mehl and Michal Wojtylak.