DIMEA Days 2022 - Abstracts of the talks

Stefan Felsner: Contact representations of planar graphs - combinatorial structure and algorithm X

The main player in this talk is algorithm X. In its various disguises this algorithm can be used to compute contact representations of planar graphs with squares, homothetic triangles, pentagons and other shapes. To this end the algorithm exploits combinatorial structures such as transversal structures, Schnyder woods, and five-color forests. We survey what is known about algorithm X and what remains mysterious.

Tomáš Kaiser: Critical subgraphs of Schrijver graphs

Soon after Lovász' breakthrough result that determined the chromatic number of Kneser graphs, Schrijver described a related family of graphs now called Schrijver graphs. For each Kneser graph G, the corresponding Schrijver graph is a vertex-critical subgraph of G with the same chromatic number. Since Schrijver graphs are not edge-critical (the deletion of an edge may not decrease the chromatic number), it is natural to ask if one can make a step further and describe an edge-critical subgraph of a Schrijver graph with the same chromatic number. Such a description was recently obtained by Matěj Stehlík and the speaker as one of the main results of a long-term project focused on quadrangulations of projective spaces. In this talk, I will describe this construction and discuss its geometric and combinatorial aspects.

Joint work with Matěj Stehlík.

Edita Máčajová: Geometric approach to Berge's conjecture

A fascinating conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. Since three perfect matchings suffice only when the graph is 3-edge-colourable, the remaining cubic graphs fall into two classes: those that can be covered with four perfect matchings, and those that need at least five. Understanding the cubic graphs that require more than four perfect matchings to cover their edges is therefore fundamental for any potential approach that might lead to proving or disproving Berge's conjecture. A significant obstacle for this has been the fact that examples of cubic graphs that cannot be covered with four perfect matchings are extremely rare and difficult to find. In the talk we outline a theory that describes coverings with four perfect matchings as flows whose flow values represent points and outflow patterns represent lines of a configuration six lines spanned by four points of the 3-dimensional projective space over the 2-element field in general position. This theory provides a powerful tool for investigating the graphs that do not admit such a cover and leads to a number of new results. Among them are, for instance, unification all known examples and constructions into a single family, offering a great variety of new constructions, or disproving conjectures that attribute certain properties to cubic graphs that cannot be covered with four perfect matchings.

The talk is based on several recently published papers co-authored by Martin Škoviera.

Hans Raj Tiwary: Extension Complexity: how (not) to modify your polytope

Extension complexity of a polytope P is a measure of the number inequalities needed to define any polytope whose shadow along suitably chosen directions is P. With perfect matching polytope being essentially the only known exception, known polytopes with exponential extension complexity correspond to various NP-hard problems. These lower bounds typically follow a reduction based approach similar to NP-hardness proofs with the CUT polytope serving as the basis of hardness. Both for obtaining lower and upper bounds on the extension complexity of polytopes related to various combinatorial optimization problems, one may wish to understand how a 0/1-polytope can be modified so that the extension complexity does not drastically change. In this talk I will discuss how essentially every non-local transformation (depending on more than a single coordinate) can change the extension complexity of some 0/1-polytope too much. I will also discuss some special cases in which the change is not drastic.

Szymon Toruńczyk: On monadically stable and monadically NIP classes of graphs

Sparsity theory, initiated by Ossona de Mendez and Nešetřil, identifies those classes of sparse graphs that are tractable in various ways (e. g. from the perspective of the model checking problem for first order logic) as exactly the nowhere dense classes. There is an ongoing effort aimed at generalizing sparsity theory to classes of graphs that are not necessarily sparse. It is conjectured that the relevant notion characterizing dense graph classes that are tractable, generalizing nowhere denseness, is the notion of monadically NIP classes, introduced by Shelah in model theory. I will survey some recent progress in the understanding of those classes, and of the related monadically stable classes. In particular, monadically NIP classes are a common generalization of the notions of nowhere denseness and of twin-width, introduced recently by Bonnet, Thomassé, and coauthors.

Géza Tóth: Coloring disjointness graphs of segments and polygonal chains

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph of any system of segments in the plane is chi-bounded, that is, its chromatic number is upper bounded by a function of its clique number. We generalize this statement for segments in (high dimensional) space. We also show that the statement does not remain true for systems of polygonal chains of length 2, even in the plane.For polygonal chains of length 3 the disjointness graphs can have arbitrarily large girth and chromatic number.

Joint work with János Pach and Gábor Tardos.