Joint DIMEA and FORMELA seminar

This research seminar provides a venue for presenting research results concerning algorithms, discrete structures, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA and FORMELA. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

Time and place

The seminar takes place on Monday at 2PM term time in Room C417 in the building of the Faculty of Informatics on a (roughly) biweekly schedule.

Fall 2021 – schedule overview

20 SeptemberTomas Kaiser (University of West Bohemia)Independent transversals in graphs
4 OctoberFilip Pokrývka (Masaryk University)Twin-width of circle graphs
11 OctoberThekla Hamm (TU Vienna)A unifying framework for characterizing and computing width measures
18 OctoberPedro Campos Araújo (The Czech Academy of Sciences)Hamilton cycles in uniformly dense hypergraphs
1 NovemberJan Hladký (The Czech Academy of Sciences)Graph norms and the regularity lemma
8 NovemberAnder Lamaison (Masaryk University)TBA
15 NovemberCornelius Brand (TU Vienna)TBA
22 NovemberJan Volec (CTU Prague)TBA
29 November Vít Musil (Masaryk University)TBA

Tomas Kaiser (University of West Bohemia): Independent transversals in graphs

Monday, 20 September, 14:00, room C417

Let G be a graph with a partition P of its vertex set. An independent transversal in G (with respect to P) is an independent set of G intersecting each class of P. Independent transversals have natural connections to a variety of problems, and since 1970s, conditions for their existence have been widely studied. We will discuss topological and probabilistic arguments used to establish such conditions, as well as recent developments related to the entropy compression method. Includes joint work with Carla Groenland, Matt Wales and Oscar Treffers.

Filip Pokrývka (Masaryk University): Twin-width of circle graphs

Monday, 4 October, 14:00, room C417

In 2020 Bonet et al. introduced parameter of graphs called twin-width. The series of results followed, showing that graph classes of bounded twin-width have tractable first-order model checking and then followed by examples of classes of bounded twinwidth. One of the most interesting graph class result is that any hereditary proper subclass of permutation graphs has bounded twin-width, while class of all permutatation graphs does not. We studied superclass of permutation graphs called circle graphs (intersection graph of chords of a circle), and we concluded that a hereditary subclass of circle graphs has bounded twin-width if and only if it forbids some permutation graph as induced subgraph. This is joint work with Petr Hliněný.

Thekla Hamm (TU Vienna): A Unifying Framework for Characterizing and Computing Width Measures

Monday, 11 October, 14:00, room C417

Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify 𝓕-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of 𝓕-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can compute every possible 𝓕-branchwidth, providing a unifying framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions. Based on joint work with Eduard Eiben, Robert Ganian, Lars Jaffke and O-joung Kwon.

Pedro Campos Araújo (The Czech Academy of Sciences): Hamilton cycles in uniformly dense hypergraphs

Monday, 18 October, 14:00, room C417

We study sufficient conditions for the existence of Hamilton cycles in uniformly dense 3-uniform hypergraphs. We show that if an n-vertex 3-uniform hypergraph H=(V,E) has the property that for any set of vertices X and for any collection P of pairs of vertices, the number of hyperedges composed by a pair belonging to P and one vertex from X is at least (1/4+o(1))|X||P| - o(|V|³) and H has minimum vertex degree at least Ω(|V|²), then H contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context. We also discuss possible extensions to higher uniformities.

Jan Hladký (The Czech Academy of Sciences): Graph norms and the regularity lemma

Monday, 1 November, 14:00, room C417

Graph norms are a fairly recent concept that emerged with the theory of graphons. This concept has been particularly useful for progress related to the notorious conjecture of Sidorenko. I will explain this connection, and also explain how this relates to the index pumping operation, which is in the heart of proofs of various regularity lemmas. The talk is based on arXiv:1809.03797.

Past terms

Spring 2021: Special Seminarpart of Round the World Relay in Combinatorics, where a number of seminars and groups around the world were getting together. Each site hosted a talk, and everyone was welcome.

Fall 2020: ITI Online Seminara one-semester online venue for presenting current research in discrete mathematics and theoretical computer science in the Czech Republic.

Spring 2020

Fall 2019

Spring 2019