Talks of the ITI Online Seminar

General information about the seminar and how to join the meetings (incl. passwords) can be found on the main page.

Approximation algorithms in classes with sublinear separators

by Zdeněk Dvořák (Computer Science Institute of Charles University, Prague)

8th October 2020, 11:00 CEST (join)

Abstract

Lipton and Tarjan proved that every n-vertex planar graph has a balanced separator of order O(sqrt(n)) and gave a number of algorithmic applications of this result. In particular, they showed that the maximum size of an independent set in graphs with this property can be approximated arbitrarily well in polynomial time. The idea of their algorithm applies to other problems, but only subject to somewhat limiting restrictions (the optimal solution must be of linear size and the problem must be defined by edge constraints).

In the last few years, several more sophisticated techniques for graphs with sublinear separators were developed; these techniques overcome the aforementioned restrictions and enable us to design approximation algorithms for much more general classes of problems. I will survey these developments and the outstanding challenges.


Toroidal grid minors and stretch in embedded graphs

by Petr Hliněný (Masaryk University, Brno)

15th October 2020, 11:00 CEST (join)

Abstract

We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar crossing number of G. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface‑embedded graph with bounded maximum degree.

slides


Limits of Latin squares

by Frederik Garbe (Institute of Mathematics, Czech Academy of Sciences)

22nd October 2020, 11:00 CEST (join)

Abstract

We develop a limit theory for Latin squares, paralleling the recent limit theories of dense graphs and permutations. We introduce a notion of density, an appropriate version of the cut distance, and a space of limit objects – so-called Latinons. Key results of our theory are the compactness of the limit space and the equivalence of the topologies induced by the cut distance and the left-convergence. Last, using Keevash's recent results on combinatorial designs, we prove that each Latinon can be approximated by a finite Latin square.

This is joint work with Robert Hancock, Jan Hladký and Maryam Sharifzadeh.


Six-cycles and perfect matchings of snarks

by Roman Nedela (University of West Bohemia, Pilsen)

29th October 2020, 11:00 CET (join)

Abstract

Every 3-edge-colourable cubic graph has a set of three perfect matchings that cover all of its edges. Conversely, if the edge set of a cubic graph can be covered with three perfect matchings, the matchings must be disjoint and the graph 3-edge-colourable. It follows that if a cubic graph is not 3-edge-colourable, then any collection of three perfect matchings, called a 3-packing, leaves some of its edges not covered. The minimum number of edges of a cubic graph G left uncovered by any set of three perfect matchings will be called the colour defect, or shortly, the defect of G and will be denoted by df(G). In this talk, by a snark I mean an uncolourable bridgeless cubic graph. Due to Petersen theorem the defect is well-defined for such graphs, with a trivial upper bound df(G) ≤ v(G), where v(G) denotes the number of vertices of G.

The concept of defect of a cubic graph was introduced by Steffen (2017). Among other things he proved that if a graph is not 3-edge-colourable, then its defect must be at least 3. Another notable result states that the defect of a snark is at least as large as one half of its girth. Since there exist snarks of arbitrarily large girth (Kochol 1996), there exist snarks of arbitrarily large defect. Hence, the defect of a snark G can be viewed as a measure of uncolourability of G.

An induced subgraph H of a snark G is called non-removable if G − H is colourable. Otherwise, H is called removable. Recall that a snark G is critical if every pair of distinct adjacent vertices in G is non-removable. Similarly, we shall say that G is cocritical if every pair of distinct nonadjacent vertices is non-removable. If G is both critical and cocritical then we say that G is bicritical. A snark G is irreducible if every induced subgraph H with at least two vertices is non-removable. It is known that a snark is irreducible if and only if it is bicritical. A snark G will be called strong if every pair of adjacent vertices is removable.

In my talk I will focus on snarks with defect 3, which is the minimum possible value of the defect of a snark. It can be easily seen that a snark of defect 3 has a 6-cycle. Our primary motivation to investigate the snarks of defect 3 is the following modified girth conjecture published in 1996.

Conjecture 1. (R. Nedela and M. Škoviera) The girth of irreducible snarks is at most 6.

Having in mind that snarks of defect 3 contain 6-cycles we aimed to prove

Conjecture 2. The defect of irreducible of snarks is 3.

Although, this goal was not fully achieved, a partial solution was obtained. As a consequence, we proved that a permutation snark is of defect 3 if and only if it admits a 6-cycle. Note that no permutation snark without a 6-cycle is known (another nice problem to discuss). On the other hand side, strong snarks and snarks of girth > 6 have defect > 3. Computer-aided experiments show that between 25286953 cyclically 4-connected snarks of girth ≥ 5 and of order ≤ 34 only 178 have defect > 3. This suggests that it may be that almost all snarks have defect 3.

Futhermore, we investigated the relation of the defect to other invariants of snarks. We shall see that several important invariants of snarks take their minimum values on snarks in this family: namely oddness, resistence, compactness, perfect-matching index, and others. In order to attract the listeners, we announce the following result.

Theorem. Every bridgeless cubic graph with defect 3 has a Berge cover.

Recall that a Berge cover of a cubic graph G is a set {M1, M2, M3, M4, M5} of five perfect matchings, not necessarily distinct, that together cover all the edges of G. A long term open Berge conjecture states that every bridgeless cubic graph admits a Berge cover.

This is joint work with J. Karabáš, E. Máčajová, and M. Škoviera.

Bibliography:

1. G. Brinkmann, J. Goedgebeur, J. Hgglund, K. Markstrm, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013), 468–488.

2. P. J. Cameron, A. G. Chetwynd and J. J. Watkins, Decomposition of snarks, J. Graph Theory 11 (1987), 13–19.

3. G. Fan and A. Raspaud, Fulkerson’s Conjecture and circuit covers, J. Combin. Theory Ser. B 61 (1994), 133–138.

4. M. A. Fiol, G. Mazzuoccolo, E. Steffen, Measures of edge-uncolorability of cubic graphs, Elec- tron. J. Combin. 25 (2018), #P4.54.

5. L. Jin, E. Steffen, Petersen cores and the oddness of cubic graphs, J. Graph Theory 84 (2017), 109–120.

6. L. Jin, E. Steffen, and G. Mazzuoccolo Cores, joins and the Fano-flow conjectures, Discuss. Math. Graph Theory 38, 165–175.

7. J. Karabáš, E. Máčajová, R. Nedela, 6-decomposition of snarks, European J. Combin. 34 (2013), 111–122.

8. M. Kochol, Snarks without small cycles, J. Combin. Theory Ser. B 61 (1996), 34–47.

9. R. Lukot’ka, E. Máčajová, J. Mazák, M. Škoviera, Small snarks with large oddness, Electron. J. Com- bin. 22 (2015), #P1.51.

10. E. Máčajová, A. Raspaud, On the strong circular 5-flow conjecture, J. Grap Theory 52 (2006), 307–316.

11. E. Máčajová, M. Škoviera, Fano colourings and the Fulkerson Conjecture, Theoret. Comput. Sci. 349 (2005), 112–120.

12. E. Máčajová, M. Škoviera, Sparsely intersecting perfect matchings in cubic graphs, Combinatorica 34 (2014), 61–94.

13. R. Nedela and M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253–279.

14. E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998), 183–203.

15. E. Steffen, 1-Factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015), 195–206.

16. E. Steffen, Intersecting 1-factors and nowhere-zero 5-flows, Combinatorica 35 (2015), 633–640.


Polynomial time approximation schemes for clustering in low highway dimension graphs

by Andreas Feldmann (Faculty of Mathematics and Physics of Charles University, Prague)

5th November 2020, 11:00 CET (join)

Abstract

We study clustering problems such as k-Median, k-Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) [Feldmann et al. SICOMP 2018] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) [Becker et al. ESA 2018, Braverman et al. 2020]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. This is joint work with David Saulpic. The arxiv version can be found at https://arxiv.org/pdf/2006.12897.pdf.


Ramsey upper density of infinite graphs

by Ander Lamaison (Masaryk University, Brno)

17th December 2020, 11:00 CET (join)

Abstract

Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for wide classes of bipartite graphs and infinite factors.


Last change: 2020-10-22T15:56:42 CEST