Spring 2022 – schedule overview

21 FebruaryDiana Piguet (Czech Academy of Sciences)Perfect packing of degenerate graphs
28 FebruaryMykhaylo Tyomkyn (Charles University)Weak saturation in graphs and hypergraphs
21 MarchSamuel Mohr (Masaryk University)Inducibility of Cycles
28 MarchFilip Pokrývka (Masaryk University)First-Order Model Checking of Interval Graphs
04 AprilNathanael Arkor (Masaryk University)What is a proof?
11 AprilWalner Mendonça (IST Austria)Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
25 AprilTomas Juškevičius (Czech Academy of Sciences)Anticoncentration of sums of random vectors: on conjectures of Leader-Radcliffe and Lee Jones
02 MayZuzana Patáková (Charles University)On Radon and fractional Helly theorems
23 MayAlexandre Duret-Lutz (EPITA)Practical Applications of the Alternating Cycle Decomposition
13 JuneDavid Munhá Correia (ETH Zürich)Erdös's conjecture on the pancyclicity of Hamiltonian graphs
29 AugustFan Wei (Princeton University)Local max-cut in smoothed polynomial time

Diana Piguet (Czech Academy of Sciences): Perfect packing of degenerate graphs

Monday, 21 February, 14:00, room C417

A family of graphs packs into a host graph if there are edge-disjoint copies of every element of the family in the host graph. I shall talk about perfectly packing degenerate graphs of sublinear maximum degree into a complete graph. This work has been motivated by two beautiful tree-packing conjectures - one of Ringel from 1963 and one of Gyárfás from 1976. This is joint work with Peter Allen, Julia Böttcher, Dennis Clemens, Jan Hladký, and Anusch Taraz.

Mykhaylo Tyomkyn (Charles University): Weak saturation in graphs and hypergraphs

Monday, 28 February, 14:00, room C417

For two r-uniform hypergraphs G and H we say that G is weakly H-saturated if the missing edges in G can be filled one by one, creating a new copy of H at every step. The quantity wsat(n,H) measures the smallest size of a weakly H-saturated r-graph of order n. For r=2 a short argument due to Alon (1985) shows that for any graph H, wsat(n,H)/n tends to a limit as n increases. Tuza conjectured in 1992 that for arbitrary r the quantity wsat(n,H)/n^{r-1} similarly has a limit c(H). I will present a recent proof of Tuza's conjecture. Joint work with Asaf Shapira.

Samuel Mohr (Masaryk University): Inducibility of Cycles

Monday, 21 March, 14:00, room C417

Given positive integers k and n, we may ask for the maximum number of induced cycles of length k in an n-vertex graph. These type of questions of the inducibility of cycles including stability arose some decades ago and were also encouraged by conjectures of Erdős. In 1975, Pippenger and Golumbic conjectured the widely believed general answer of k!/(k^k-k). Recently, some specific exact results were achieved using Flag Algebra Methods. In this talk, I will give an overview about known results and approximations. The way Flag Algebra inequalities were plugged in to obtain exact results will be presented, too. My research was supported by DAAD.

Filip Pokrývka (Masaryk University): First-Order Model Checking of Interval Graphs

Monday, 28 March, 14:00, room C417

The class of interval graphs is a geometric graph class where edge relation is an intersection relation of intervals on the real axis. A geometric representation can be efficiently computed for a given interval graph, so geomteric properties might be used to solve hard problems. This talk focuses on first-order model checking problem (FO MC), as this metaproblem captures all problems expressible in first-order logic (e.g. k-CLIQUE, k-DOMINATING SET). The first results presented at ICALP'13 showed hardness of FO MC on interval graphs in general, and exhibited a natural subclass of interval graphs in which this problem is efficiently solvable. This was improved in a FOCS'15 paper, by providing another example of an efficiently solvable subclass. Our results give the complete answer to the question of when hereditary subclasses of interval graphs have efficient FO MC.
This is joint work with Petr Hliněný.

Nathanael Arkor (Masaryk University): What is a proof?

Monday, 04 April, 14:00, room C417

We are all intimately familiar with the idea of a proof, which is essential in mathematics. However, most likely we have rarely given thought to what exactly it is that constitutes a proof. For everyday mathematics, this question may seen unimportant, since the purpose of a proof is simply to convey understanding to other mathematicians. However, in recent years, it has become increasingly clear that there is a significant need for the computer-aided verification of mathematics: this necessitates a general, formal notion of proof.
Drawing on ideas from type theory, I shall present a general notion of deduction system that captures various formal systems of proof, and discuss how such a notion fits into a growing vision for the future of mathematics. I shall give examples from algebra, logic, and type theory to motivate the ideas.
No familiarity with type theory will be expected for the talk.

Walner Mendonça (IST Austria): Tiling edge-coloured graphs with few monochromatic bounded-degree graphs

Monday, 11 April, 14:00, room C417

Gerencsér and Gyárfás proved in 1967 that for any 2-colouring of the edges of K_n, it is possible to partition V(K_n) into two monocromatic paths. This result, which has a straightforward proof, motivated many other challenging problems that have been extensively studied in the last years. For instance, an open conjecture of Erdős, Gyárfás and Pyber from 1991 states that for any r-colouring of the edges of K_n there are r monochromatic paths partitioning V(K_n). We can also find in the literature other versions of the problem where instead of partitioning into paths, we are interested in partitioning into trees, cycles, or even power of cycles.
Grinshpun and Sárkőzy studied a more general version of the problem where they were interested in partitioning V(K_n) into few monochromatic subgraphs which are copies of a given family of bounded degree graphs. They proved that for any family of graphs ℱ = {F_i : i ∈ N} such that |F_i| = i and Δ(F_i) ≤ D, the following holds: for any 2-colouring of edges of K_n, there is a partition of V(K_n) into at most 2^{O(D log D)} monochromatic subgraphs that are copies of graphs from ℱ. They conjectured that for any r-colouring of the edges of K_n, it is possible to partition V(K_n) into 2^{D^C} monochromatic subgraphs that are copies of graphs from ℱ, where C=C(r) is a constant that only depends on r. In this talk, we present the first progress towards Grinshpun-Sárkőzy's conjecture by establishing a super-exponential bound.

Tomas Juškevičius (Czech Academy of Sciences): Anticoncentration of sums of random vectors: on conjectures of Leader-Radcliffe and Lee Jones

Monday, 25 April, 14:00, room C417

In this talk we shall address anticoncentration inequalities for sums of random vectors. In particular, we shall asymptotically establish two conjectures: one by Lee Jones (1978) and another by Leader-Radcliffe (1994). Perhaps surprisingly, the main ingredient to establish the latter result is the Strong Perfect Graph Theorem by Chudnovsky, Robertson, Seymour and Thomas (2002).
The talk is based on recent joint work with V. Kurauskas (Vilnius University).

Zuzana Patáková (Charles University): On Radon and fractional Helly theorems

Monday, 2 May, 14:00, room C417

Radon theorem plays a basic role in many results of combinatorial convexity. It says that any set of d+2 points in R^d can be split into two parts so that their convex hulls intersect. It implies Helly theorem and as shown recently also its more robust version, so-called fractional Helly theorem. By standard techniques this consequently yields an existence of weak epsilon nets and a (p,q)-theorem.
We will show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. More precisely, given an intersection-closed family F of subsets of R^d, we will measure the complexity of F by the supremum of the first d/2 Betti numbers over all elements of F. We show that bounded complexity of F guarantees versions of all the results mentioned above. Partially based on joint work with Xavier Goaoc and Andreas Holmsen.
The talk is based on recent joint work with V. Kurauskas (Vilnius University).

Alexandre Duret-Lutz (EPITA): Practical Applications of the Alternating Cycle Decomposition

Monday, 23 May, 14:00, room C417

Joint work with Antonio Casares, Klara J. Meyer, Florian Renkin, and Salomon Sickert
In 2021, Casares, Colcombet, and Fijalkow introduced the Alternating Cycle Decomposition (ACD) to study properties and transformations of Muller automata. We present the first practical implementation of the ACD in two different tools, Owl and Spot, and adapt it to the framework of Emerson-Lei automata, i.e., ω-automata whose acceptance conditions are defined by Boolean formulas.
The ACD provides a transformation of Emerson-Lei automata into parity automata with strong optimality guarantees: the resulting parity automaton is minimal among those automata that can be obtained by duplication of states. Our empirical results show that this transformation is usable in practice. Further, we show how the ACD can generalize many other specialized constructions such as deciding typeness of automata and degeneralization of generalized Büchi automata, providing a framework of practical algorithms for ω-automata.

David Munhá Correia (ETH Zürich): Erdös's conjecture on the pancyclicity of Hamiltonian graphs

Monday, 13 June, 14:00, room C417

An n-vertex graph is Hamiltonian if it contains a cycle covering all its vertices and it is pancyclic if it contains cycles of all lengths from 3 up to n. A meta-problem that has been studied for at least fifty years is to understand how close these two notions are. Does every non-trivial condition implying Hamiltonicity also imply pancyclicity? And what conditions does one need to add to ensure that a Hamiltonian graph is also pancyclic?
In 1972, Erdös conjectured that there exists an absolute constant C such that every Hamiltonian graph G on at least n = C α(G)2 vertices is pancyclic, where α(G) denotes the size of the largest independent set in G. We prove this conjecture in a strong form by showing that (2+o(1))α(G)2 vertices are enough and this is tight up to the o(1) term.
This is joint work with Nemanja Draganić and Benny Sudakov.

Fan Wei (Princeton University): Local max-cut in smoothed polynomial time

Monday, 29 August, 14:00, room C417

In this talk, we show that in the smoothed analysis setting (where each parameter perturbed by an independent small error), local search algorithm for max-cut in a graph, which is also equivalent to the asynchronous Hopfield network, or a natural algorithm to find the Nash Equilibrium in the party affiliation game (an example of potential game), the complexity is polynomial. This is the first proved smoothed polynomial bound for these models; previously the best known bound is n^{O(log(n))}.
This is joint work with Omer Angel, Sebastien Bubeck, and Yuval Peres.