Talks of the ITI Online Seminar

Approximation algorithms in classes with sublinear separators

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

8^th 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)

15^th 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)

22^nd 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.

↪slides

Six-cycles and perfect matchings of snarks

by Roman Nedela (University of West Bohemia, Pilsen)

29^th 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 {M₁, M₂, M₃, M₄, M₅} 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)

5^th 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 arXiv.

Littlewood-Offord theory for arbitrary distributions

by Tomas Juskevicius (Institute of Mathematics, Czech Academy of Sciences)

12^th November 2020, 11:00 CET (join)

Abstract

The classical Littlewood-Offord problem asks for the maximum probability that a weighted sum of independent random signs hits a point or a ball of a given radius. A sharp result when dealing with real weights was famously provided by Erdős who used Sperner's Theorem. This was later generalized to high dimensions by Kleitman. In this talk we shall consider the same problem for arbitrary distributions. It turns out that, perhaps surprisingly, there is a unique choice of optimal weights, regardless of the distribution under consideration. Our result applied to Bernoulli distributions answers a recent question of Fox, Kwan and Sauermann. An important feature of our approach is that we do not use Harmonic Analysis or Extremal Combinatorics, which are the prevailing tools in the area. Finally, I will discuss the applications of the methods developed to other problems.

The talk is based on joint work with Valentas Kurauskas (Vilnius University) and a preprint of our paper can be found at arXiv.

Isomorphism Problem for S_d-graphs

by Deniz Agaoglu (Masaryk University, Brno)

19^th November 2020, 11:00 CET (join)

Abstract

An H-graph is the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró, Hujter and Tuza (1992). We focus on S_d-graphs as a special case generalizing interval graphs. A graph G is an S_d-graph if and only if it is the intersection graph of connected subgraphs of a subdivision of a star S_d with d rays. We give an FPT algorithm to solve the isomorphism problem for S_d-graphs with the parameter d. This solves an open problem of Chaplick, Töpfer, Voborník and Zeman (2016). In the course of our proof, we also show that the isomorphism problem of S_d-graphs is computationally at least as hard as the isomorphism problem of posets of bounded width.

Even maps, the Colin de Verdière number and representations of graphs

by Martin Tancer (Department of Applied Mathematics of Charles University, Prague)

26^th November 2020, 11:00 CET (join)

Abstract

Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of σ is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G)≤σ(G)+2 and conjectured μ(G)≤σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on μ(G) which is, in general, tight. Equality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G)≤18 and σ(G)≥20. We show that the gap appears on much smaller values, namely, we exhibit a graph H for which μ(H)≤7 and σ(H)≥8. We also prove that, in general, the gap can be large: The incidence graphs H_q of finite projective planes of order q satisfy μ(H_q) is of order q^(3/2) while σ(H_q) is quadratic in q. During the talk, I plan to explain the results and sketch the main ideas of the proofs.

This is a joint work with Vojtěch Kaluža.

Extension complexity upper bounds via orienting cycles: Three unified results

by Hans Raj Tiwary (Faculty of Mathematics and Physics of Charles University, Prague)

3^rd December 2020, 11:00 CET (join)

Abstract

In proving that a given (large) polytope can be obtained as a projection of a small polytope, one often uses specialized arguments that are specific to the problem at hand. In this talk I will present simple proofs of three known results showing polynomial extension complexity for Subtour Elimination inequalities for TSP, vertex figure of Matching polytope, and Odd-cycle inequalities for Independent set. Our proofs use the (little-exploited) connection between extension complexity and existence of certain two party protocols computing the slack matrix of a polytope. The talk will contain an overview of this connection as well.

Cycles of a given length in tournaments

by Jan Volec (Czech Technical University, Prague)

10^th December 2020, 11:00 CET (join)

Abstract

We study the asymptotic behavior of the maximum number of directed cycles of a given length k in large tournaments. It is well-known that in the triangle case the maximum is attained by a regular tournament, and in the case of 4-cycles the maximum is attained by the so-called carousel tournament – a vertex-transitive tournament on the vertex-set {0,1,2,…,2k} with arcs from a vertex i to the vertices i+1,i+2,…,i+k (mod 2k+1).

In this talk, we show that for every l that is not a multiple of 4 the number of l-cycles is asymptotically maximized by a random tournament. Moreover, for any positive integer z, we prove that a large tournament T maximizes the number of (4z+2)-cycles and (2z+1)-cycles if and only if T is quasi-random and regular, respectively. For the cylce-lengths that are divisible by 4, we show that the carousel tournament asymptotically maximizes the number of 8-cycles, and find an approximate solution for sufficiently long cycles.

This is a joint work with Andrzej Grzesik, Dan Kráľ and Laszlo M. Lovász.

Ramsey upper density of infinite graphs

by Ander Lamaison (Masaryk University, Brno)

17^th 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.