Combinatorial group

** Friday 12.5.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10),
Eng Keat Hng (ICS CAS): Characterising flip process rules with the same trajectories**

__Abstract__:Garbe, Hladký, Šileikis and Skerman recently introduced a class of discrete-time random graph processes called flip processes. A flip process starts with a given n-vertex graph, and each step of a flip process involves randomly selecting a k-tuple of distinct vertices and modifying the induced subgraph according to a predetermined rule. It was proved by Garbe, Hladký, Šileikis and Skerman that the typical behaviour of flip processes correspond to certain continuous-time deterministic graphon trajectories.

In this talk we discuss recent work towards characterising flip process rules with the same trajectories.

** Friday 5.5.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10),
Jan Hladky (ICS CAS): Invitation to graphons**

__Abstract__: The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory, so-called graphons, are suitable measurable counterparts to graphs.

In the talk, I will outline the syllabus of a hypothetical first course in graphon theory, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal, Hu, Máthé, Piguet, Rocha.

** Friday 28.4.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Diana Piguet (ICS CAS): Degree conditions for tree-embedding and implication for the Erdős–Sós Conjecture**

__Abstract__: We shall present an approximate solution of a conjecture of Klimošová, Piguet, and Rozhoň in dense graphs concerning tree embedding. We'll also show how the result implies the approximate version of the Erdős–Sós Conjecture in the context of dense graphs.

This is a joint work with Akbar Davoodi, Hanka Řada, and Nicolás Sanhueza.

** Friday 21.4.2023 at 10:00 ICS, room 419 (and on ZOOM),
Tomas Juškevičius (ICS CAS): The "power of few" phenomenon: majority dynamics on G(n,p) **

__Abstract__: The "majority dynamics" process on a social network begins with an initial phase, where the individuals are split into two competing parties, Red and Blue. Step by step everyone updates their affiliation to match the majority among those of their friends. While studying this process on Erdos-Renyi G(n, p) random graph (with constant density), Van Vu and Linh Tran discovered the "Power of Few" phenomenon, showing that a very small advantage to one side already guarantees that everybody will unanimously join that side after just a few days with overwhelming probability. For example, when p = 1/2, then 10 extra members guarantee this unanimity with a 90% chance, regardless of the value of n. We shall present some of these results and formulate a couple of open problems.

The talk is based on recent papers of Van Vu and Linh Tran.

** Friday 14.4.2023 at 10:00 ICS, room 318 (and on ZOOM), Matas Šileikis (ICS CAS): Maximum local tree counts in G(n,p) **

__Abstract__:
We consider a generalization of the maximum degree. Given a rooted tree T, let X_v be the number of copies (injective homomorphisms) of T rooted at v in the random graph G(n,p). We ask the question where the maximum of X_v over all vertices is concentrated. For p tending to zero not too fast, the maximum is asymptotically attained by the vertex of maximum degree. That is, if the maximum degree is concentrated at D = D(n,p), then maximum T-count is concentrated at D^d(pn)^{e(T) - d}, where d is the degree of the root. However, for smaller p, the maximum is of higher order and the answer crucially depends on the structure of T.

** Wednesday 11.1.2023 at 09:30 ICS, room 318 (and on ZOOM), Małgorzata Sulkowska (Wrocław University of Science and Technology): Modularity of minor-free graphs **

__Abstract__:
Modularity is a well-established parameter measuring the presence of community structure in the graph. It was introduced by Newman and Girvan in 2004. Nowadays it is widely used as a quality function for community detection algorithms. The popular heuristic clustering algorithms (e.g., Louvain algorithm or Leiden algorithm) find a partition using modularity-based approach. We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, for every eps>0, the modularity of any graph in the class with sufficiently many edges is at least 1-eps.
This completes the classification of maximally modular classes among all commonly considered subclasses of nowhere dense graphs with maximum degree sublinear in the number of edges.

Joint work with Michał Lasoń.