Monday 27.11.2023 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Jan Volec (Czech Technical University in Prague): TBA
|
Abstract: TBA |
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): TBA
|
Abstract: TBA |
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): Sorting time of permutation classes
|
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 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ń.
