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 September||Tomas Kaiser (University of West Bohemia)||Independent transversals in graphs|
|4 October||Filip Pokrývka (Masaryk University)||Twin-width of circle graphs|
|11 October||Thekla Hamm (TU Vienna)||A unifying framework for characterizing and computing width measures|
|18 October||Pedro Campos Araújo (The Czech Academy of Sciences)||Hamilton cycles in uniformly dense hypergraphs|
|1 November||Jan Hladký (The Czech Academy of Sciences)||Graph norms and the regularity lemma|
|8 November||Ander Lamaison (Masaryk University)||TBA|
|15 November||Cornelius Brand (TU Vienna)||TBA|
|22 November||Jan Volec (CTU Prague)||TBA|
|29 November||Vít Musil (Masaryk University)||TBA|
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.
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ý.
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.
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.
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.
Spring 2021: Special Seminar – part 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 Seminar – a one-semester online venue for presenting current research in discrete mathematics and theoretical computer science in the Czech Republic.