Monday 11.12.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Gaurav Kucheriya (Charles University): Characterization of edge-ordered graphs with linear extremal functions
Abstract: The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is $\Omega(n \log n)$. This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs. We also extend the study of extremal function of short edge-ordered paths by Gerbner et al. to some longer paths. Joint work with Gábor Tardos.
Monday 4.12.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Valentas Kurauskas (Vilnius University): Estimating Global Subgraph Counts by Sampling
Abstract: I will talk about a short joint paper with Svante Janson on estimating small (constant-sized) subgraph counts in very sparse graphs (bounded average degree) by, for example, repeatedly sampling a uniformly random vertex and then counting the number of rooted copies around that vertex.
Monday 20.11.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Anna Limbach (ICS CAS): Clique Dynamics of Finite or Infinite Locally Cyclic Graphs with δ≥6
Abstract:
We prove that the clique graph operator k is divergent on a (not necessarily finite) locally cyclic graph G with minimum degree δ ≥ 6 if and only if the universal triangular cover of G contains arbitrarily large triangular-shaped subgraphs. For finite G, this is equivalent to G being 6-regular.
A graph is called locally cyclic if the open neighbourhood N_G(v) of each vertex v induces a cycle. The clique graph kG of a graph G has the maximal complete subgraphs of G as its vertices and its edges are those pairs with non-empty intersection. The (n+1)-st iterated clique graph is recursively defined as the clique graph of the n-th iterated clique graph. If all iterated clique graphs of G are non-isomorphic, the graph G is called k-divergent; otherwise, it is k-convergent.
While it has been shown for finite locally cyclic graphs that those with minimum degree δ ≥ 7 are k-convergent while the 6-regular ones are k-divergent, we obtain a full characterisation of k-convergent locally cyclic graphs with minimum degree δ ≥ 6.
We start by showing that a k-convergent connected graph has a k-convergent universal triangular cover. Conversely, we give a sufficient condition under which the clique convergence of the universal triangular cover of a graph implies the clique convergence of the graph itself.
Locally cyclic graphs with minimum degree δ ≥ 6 which are triangularly simply connected are their own universal covers. On this class, clique convergence is characterised using an explicit construction of the iterated clique graphs and a finite yet divergent parameter for the k-divergent case. Furthermore, it is shown that locally cyclic graphs with minimum degree δ ≥ 6 are k-convergent if and only if their universal covers are k-convergent. This way, the characterisation is completed.
This is joint work with Markus Baumeister and Martin Winter.
Friday 3.11.2023 at 14:00 ICS, room 419 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Michal Opler (Czech Technical University in Prague): The hierarchy of hereditary sorting operators
Abstract:
We consider the following general model of a sorting procedure: we fix a hereditary permutation
class $C$, which corresponds to the operations that the procedure is allowed to perform in a
single step. The input of sorting is a permutation $\pi$ and in every step, the sorting procedure
composes $\pi$ with some permutation $\sigma$ from $C$. The goal is to transform the input
$\pi$ into the sorted sequence $1,2,\dotsc,n$ in as few steps as possible.
This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble
sort, but also sorting by series of devices, like stacks or parallel queues, as well as sorting by
block operations commonly considered, e.g., in the context of genome rearrangement.
We classify the possible asymptotic behavior of the worst-case sorting time of hereditary permutation
classes and relate it to their structural properties.
Joint work with Vít Jelínek and Jakub Pekárek.
Friday 27.10.2023 at 14:00 ICS, room 419 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Ander Lamaison (Masaryk University): Hypergraphs with minimum positive uniform Turán density
|
Abstract: Reiher, Rödl and Schacht showed that the uniform Turán density of every 3-uniform hypergraph is either 0 or at least 1/27, and asked whether there exist 3-uniform hypergraphs with uniform Turán density equal or arbitrarily close to 1/27. We construct 3-uniform hypergraphs with uniform Turán density equal to 1/27. Joint work with Frederik Garbe and Dan Král'. |
Friday 6.10.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Niklas Latz (Institute of Information Theory and Automation of the Czech Academy of Sciences): Pathwise Duality of Interacting Particle Systems
Abstract: While the term "pathwise duality" was coined in a survey paper by Jansen and Kurt in 2014, the underlying concept of constructing an interacting particle system via its "graphical representation" was already developed by Harris in the 1970s. In this talk, I will first introduce the general idea of how to construct a pathwise duality for an interacting particle system, and then present recent advances in the field that are due to joint work with Jan Swart.
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ń.