Raziskovalni matematični seminar - Arhiv

A group G is called an m-(D)CI-group if whenever two Cayley (di)graphs of G, with (out-)valencies at most m, are isomorphic, there exists an automorphism of G, mapping one connection set to the other. In this talk, we classify cyclic m-DCI-groups and m-CI-groups.

This is a joint work with István Kovács.

The  sphere dimension of a graph G is the smallest integer d≥2 so that G is an intersection graph of metric spheres in ℝ^d.

This talk considers the class C^d  of graphs with sphere dimension d.
We present the results that for each integer t, the class of all graphs in C^d that exclude K_t,t as a subgraph has strongly sublinear separators and that C^d has asymptotic dimension at most 2d+2.
 

The presented work is joined with James Davies, Agelos Georgakopoulos and Rose McCarty.

The sphere dimension of a graph G is the smallest integer d ≥ 2 so that G is an intersection graph of metric spheres in ℝ^d.

The well-known Moore graphs (including odd-length cycles, the complete graphs, the Petersen graph and the Hoffman-Singleton graph) are regular graphs of maximum conceivable order with given degree and diameter, or equivalently, regular graphs of minimum conceivable order with given degree and girth (sometimes called cages), according to the well-known Moore bound.  

More generally, the task of finding the largest regular graph with given degree and diameter is called the degree-diameter problem, and the corresponding one for given degree and girth is called the cage problem. Various people in the combinatorial community have contributed answers or partial answers to these problems.

At a BIRS workshop at Banff in May 2023, some investigations were made into the stronger notion of a degree-diameter-girth problem, namely finding the largest regular graph with given degree, diameter and girth.  I will report on some of what was discovered, after reviewing some of the background to the degree-diameter and cage problems.

A prototypical problem in extremal graph theory is determining which graphs are minimizers or maximizers of the density of a fixed graph H, possibly with some additional constraints. For example, considered among most important conjectures in extremal combinatorics, the famous conjecture by Sidorenko and Erdős-Simonovits claims that the density of every bipartite graph H is asymptotically minimized by quasirandom graphs among all graphs with the same edge density.

In this talk we will focus on directed graphs with the property that their homomorphism density is maximized by transitive tournaments. We prove that for any bipartite graph H whose edges are oriented in the same direction between both parts (that is, a directed graph that admits a homomorphism to a directed edge ), the n-vertex transitive tournament maximizes the number of homomorphisms from H among all oriented n-vertex graphs.

Joint work with Igor Balla, Bartlomiej Kielak, Daniel Král’, and Filip Kučerák.

ZOOM link: https://upr-si.zoom.us/j/94947596338?pwd=Ala2JolIlOnXb1jINtebXmk7ZlHjb9.1

Arising from applications in machine learning such as the problem of approximate sampling from a given probability distribution or optimization, special types of stochastic processes such as McKean-Vlasov SDEs became highly attractive in recent years. The theory about them is quite interesting as it shows that in many ways they exhibit different characteristics than classical diffusion processes. In this talk, I will discuss the behaviour of interacting particle systems and their gradient flows. In particular, the focus will be on WassersteinFisher-Rao and Fisher-Rao gradient flows and deriving conditions which result in the convergence to the target measures. I will consider various approaches to the problem as well as numerical methods that can be used for simulations.