Joint DIMEA and FORMELA seminar

Fall 2021 – schedule overview

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.

Ander Lamaison (Masaryk University): Hypergraphs with minimum positive uniform Turán density

Monday, 8 November, 15:00

Change: This talk will be online and is merged with the EPC webinar

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. This is based on joint work with Frederik Garbe and Daniel Král’.

Cornelius Brand (TU Vienna): Algebraic methods in parameterized graph algorithms

Monday, 15 November, 14:00, room C417

In this talk, I will present an overview over recent advances in parameterized graph algorithms using algebraic methods. More concretely, we consider (special cases of) the subgraph isomorphism problem, asking whether a given pattern graph appears as a subgraph in a given host graph, where we parameterize by the size of the pattern graph. We will mainly restrict our attention to the important special case when the pattern is a path. As it turns out, this problem admits an elegant formulation in terms of multivariate polynomials. This formulation can then in turn be tackled by using a host of algebraic objects, such as exterior algebras (B., Dell, Husfeldt, STOC'18 and B., ESA'19) or algebras of differential operators (Pratt, FOCS'19, B. and Pratt, ICALP'21). We will give a gentle introduction to the necessary mathematical notions of the latter approach, point out its applications to other problems and sketch how it connects to other techniques in the area, in particular representative families (see e.g. Fomin et al., JACM, 2016).

Jan Volec (CTU Prague): A colorful version of Mantel's theorem

Monday, 22 November, 14:00, room C417

A classical result of Mantel states that every graph of density larger than 1/2 must contain a triangle, and the constant 1/2 is best possible. Recently, DeVos, McDonald and Montejano proved the following Mantel-inspired statement: every 2-edge-colored n-vertex graph with both color classes having their size more than n²/6 contains a non-monchromatic triangle, and again the bound is best possible. Given number of colors k≥2, they conjectured that a natural generalization of their 2-colored extremal graph is going to provide extremal graphs also for the general setting. Specifically, the conjecture states that if G is k-edge-colored graph with each of the color classes having size more than n²/(4k-2), then G contains a non-monochromatic triangle. In this talk, we present a flag-algebra approach for the general k-colored question of DeVos, McDonald and Montejano, which seems to allow us to confirm their conjecture for any fixed value of k we have considered (in particular, we have verified the conjecture for all 10^6 > k). More precisely, given an integer k, we desribe a linear relaxation of the original extremal problem for k colors whose dimension does not depend on k at all. This is a joint work with Sergey Norin.

Vit Musil (Masaryk University): Combinatorial expressivity of neural networks

Monday, 29 November, 14:00, room C417

The toolbox of popular methods in computer science sees a split into two major components. On the one hand, there are classical algorithmic techniques from discrete optimization – graph algorithms, SAT-solvers, integer programming solvers – often with heavily optimized implementations and theoretical guarantees on runtime and performance. On the other hand, there is the realm of deep learning allowing data-driven feature extraction as well as the flexible design of end-to-end architectures. Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. We present a universal, easy-to-implement, fast and theoretically sound method enabling the incorporation of solvers into neural networks. We show that our method achieves the state of the art performance on various computer vision benchmarks.

Anselm Paulus (MPI Tübingen): Combinatorial expressivity of neural networks

Thursday, 16 December, 14:00, room C417

Over the recent years, deep learning has achieved astonishing successes in many fields such as computer vision and natural language processing. But while excelling at extracting information from raw data, neural networks notoriously struggle at tasks involving algorithmic reasoning. Such tasks can often be solved efficiently by combinatorial solvers, which can build on a long history of development. However, these solvers usually require a clean abstract formulation of the problem instead of raw data. How can we bridge the gap between these two worlds? This talk discusses two recently developed methods, Blackbox Backpropagation and CombOptNet, that allow the seamless integration of combinatorial solvers into end-to-end trainable deep learning architectures.