Midsummer Combinatorial Workshop XXIII

July 30 - August 3, 2018, Prague

Proceedings

List of lectures

All lectures takes place in room S5 at the building of Charles University, Malostranke namesti 25.
Monday
8:30-9:20 Registration
9:20-9:30 Welcome, brief information about program of the workshop
9:30-10:00 Martin LoeblPerfect matchings in double-torus grids
10:15-10:45 Coffee break
10:45-11:15 Zdenek Dvorak Baker game and approximation algorithms on proper minor-closed classes
11:15-11:45 Martin Balko Ramsey numbers and monotone colorings
11:45-12:15 Pierre Simon Towards a classification of geometric homogeneous structures
12:15-12:45 Dusan Knop Integer Programming in Parameterized Complexity: Three Miniatures
13:00 Lunch
Tuesday
9:00-9:30 Jan KynčlThe Z2-genus of Kuratowski minors
9:30-10:00 Andreas E. FeldmannThe Parameterized Hardness of the k-Center Problem in Transportation Networks
10:00-11:30 Pavel HubáčekOn Constant-Round Statistical Zero-Knowledge
10:30-11:00 Coffee break
11:00-11:30 Jan CorstenDiameter-Ramsey sets (slides)
11:30-12:00 Zaniar GhadernezhadAmenable automorphism groups and convex Ramsey matrices
12:00-12:30 Lluis VenaChromatic number of subgraphs of the kneser graph
13:00 Lunch
Wednesday
9:00-9:30 Václav Blažej Online Ramsey numbers
9:30-10:00 Josef CibulkaCovering Lattice points by subspaces (slides)
10:00-10:30 Endre CsókaLocal algorithms on random graphs
10:00 Group photo
10:30-11:00 Coffee break
11:00-11:30 Matěj KonečnýCompleting edge-labelled graphs (slides)
11:30-12:00 Günter RoteLattice Paths with States, and Counting Geometric Objects via Production Matrices
12:00-12:20 Jozsef SolymosiRigidity of graphs with given edge lengths
12:30 Lunch
13:50-16:00 First hike starts at the Masarykovo Nadrazi (Masaryk Train Station, reachable by tram 15). With Peter Korcsok
14:50-17:00 Second hike starts at the Masarykovo Nadrazi (Masaryk Train Station, reachable by tram 15). With Karel Kral
15:20-17:45 Third hike starts at the Masarykovo Nadrazi (Masaryk Train Station, reachable by tram 15). With Jan Hubicka
15:20 Fourth hike: you can leave at 16:20 from Masarykovo Nadrazi an walk at your own.
Taxi sharing: Contact Jan Hubicka or Karel Kral.
16:00-16:45 First brewery tour (Unětický Pivovar).
17:00-17:45 Second brewery tour (Unětický Pivovar).
17:45-18:30 Third brewery tour (Unětický Pivovar).
18:30-21:30 Conference dinner at the Unetice brewery (Unětický Pivovar)
21:30 Bus back, or use public transport (seach for "Únětice; okres Praha-západ", additional ticket approx 12kc can be purchased from bus driver)
Thursday
9:00-9:30 David HartmanEquality of MH and HH classes (slides)
9:30-10:00 Yelena YuditskyAlmost all string graphs are intersection graphs of plane convex sets
10:00-10:30 Robert ŠámalA rainbow version of Mantel's Theorem
10:30-11:00 Coffee break
11:00-11:30 José AlisteRooted U-polynomials
11:30-12:00 Dragan MašulovićFinite big Ramsey degrees in universal structures
12:00-12:30 Gábor KunGraphings not local-global approximable by finite graphs
13:00 Lunch
14:00-14:30 Zsolt TuzaFractional version of the domination game (slides)
14:30-15:00 Pavel ValtrThe exact chromatic number of the convex segment disjointness graph
15:00-15:30 Andrés Aranda HE and MB-homogeneous graphs
Friday
9:00-9:30 Hiep HanErdős-Rothschild type problems for graph cliques and Schur triples
9:30-10:00 Pavel VeselýOnline packet scheduling
10:00-10:30 Attila DankovicsHamiltonicity and low independence number imply pancyclicity
10:30-11:00 Coffee break
11:00-11:30 Jana SyrovátkováMaximizing points in prisoners dilemma tournaments
11:30-12:00 Demetres ChristofidesGraphs of high girth and high chromatic number - new proofs
11:00-12:30 Jan VolecFractional colorings vs. Hall ratio
12:30-13:00 Jan van den HeuvelUniversal orderings for generalised coloring numbers (slides)
13:00 Lunch

Announcement

The workshop continues the tradition of Prague Combinatorial Workshops held since 1993. Oriented on problems of all fields of graph theory, combinatorics and discrete geometry, it will continue in the spirit and informal working atmosphere of the previous meetings.

The workshop takes place at DIMATIA and the Department of Applied Mathematics of Charles University, Malostranske namesti 25, Prague 1, which is located in a historic building in the center of Old Prague. The workshop is also supported by Computer Science Institute of Charles University.

The workshop participation is by invitation only. Regardless, if you wish to participate, please email the organizers and we will respond to you shortly. In case you need an invitation letter (for example for your visa), please let us know and we will be happy to write one for you.

Coffee breaks and part of the meals are provided by the organizers. However, we will collect a modest fee of EUR 70 towards a fraction of the expenses.

As is the tradition, the program of the workshop is determined from day to day. The afternoons are reserved for discussions and other activities. If you intend to give a talk during the MCW, please let us know a few days in advance.

If you arrive later during the workshop, please register with the secretaries in the room 222 (at the 2nd floor).

On Wednesday afternoon, there will be an awesome social event.

Registered participants

Daniel Kral, Robert Woodrow, Robert Samal, Gena Hahn, Andrew Goodall, Martin Loebl, Pavel Valtr, Dusan Knop, Reza Naserasr, Lenka Zdeborova, Zdenek Dvorak, David Bradley-Williams, Dragan Masulovic, José Aliste, Diana Piguet, Karel Král, David Chodounsky, Manuel Bodirsky, Matej Konecny, Jan Hubicka, Jozsef Solymosi, Michael Kompatscher, Jan Corsten, Timothy Chan, Martin Balko, Peter Korcsok, Martin Hora, Václav Končický, Michael Skotnica, Ondřej Šplíchal, Aneta Šťastná, Jakub Tětek, Zsolt Tuza, Matej Stehlik, Parker Hund, Rahul Ilango, Ryan Rice, Michael Yang, Sherry Sarkar, Caitlin Guccione, Jan van den Heuvel, Florent Krzakala, Yelena Yuditsky, Csóka Endre, Casey Tompkins, Oscar Zamora, Edin Husic, Viola Mészáros, Günter Rote, Patel, Viresh, Demetres Christofides, Pierre Simon, Nate Ackerman, Ondra Suchý, Jan Kynčl, Antoine Mottet, Andrea Jiménez, Hiep Han, Gabor Kun, Goran Umicevic, Dragan Masulovic, Jan Volec, Pavel Veselý, Helena Nyklova, Jana Syrovatkova, Lluis Vena, Gregory L. Cherlin, Radek Hušek, Eng Keat Hng, Jiří Fiala, Attila Dankovics, Jozef Skokan, Andrés Aranda, Pavel Paták, Josef Cibulka, Tomáš Valla, Václav Blažej, Zuzka Patáková, Ida Kantor.

Facilities

Besides the workshop itself, you are free to use the following facilities of our departments:

If you need anything else, contact the organizers.

Travel info (public transport)

For the public transportation you can buy a 90-minute ticket for 32 CZK or 30-minute for 24 CZK in a newsstand or in a vending machine. The vending machines only accept coins (no credit cards, no paper money).

The ticket needs to be validated (in a magic yellow validating machine with a shining arrow). The validating machines are located inside buses and trams. In the Metro subway system, the machine is located at the entryway to the station.

If you need to find a tram connection, you can use the official website. The department building is located near the tram stop "Malostranske namesti". You can see it from the tram stop. It is this building.

Useful routes:

Airport -> Marianeum Hotel

Marianeum Hotel -> MCW

Airport -> Karolinum Hotel

Karolinum Hotel -> MCW

Contact

All e-mail correspondence concerning the workshop (e.g. registration, accommodation) should be directed to mcw@kam.mff.cuni.cz.

organizers: Jaroslav Nešetřil, Jan Hubicka, Karel Král

Abstracts

Martin Balko: Ramsey numbers and monotone colorings

For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color.

For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ORS(n;2)=(n-1)^2+1 and ORS(n;3) = ((2n-4) choose (n-2))+1, respectively. It follows from a result of Eliáš and Matoušek that ORS(n;4) grows as o tower of height 2.

We show that ORS(n;r) grows at least as a tower of height r-2 for every r >= 3. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ORS(n;r) and two Ramsey-type problems that have been recently considered by several researchers. We also prove asymptotically tight estimate on the number of r- monotone colorings of on [N].

Martin Loebl:Perfect matchings in double-torus grids

Joint work with Andrea Jimenez and Marcos Kiwi

It is known that the number of the perfect matchings of each finite double-torus grid is a linear combination of 16 determinants. It is predicted by the Quantum field theory (Alvarez-Gaume, Vaffa) that exactly 6 of these determinants go to zero when the size of the grid grows. I will introduce the rich world around this claim.

Zdenek Dvorak: Baker game and approximation algorithms on proper minor-closed classes

Inspired by the Splitter game for nowhere-dense classes and Baker's approach to design of approximation algorithms, we propose a new game, show a strategy winning this game in a constant number of rounds on proper minor-closed classes of graphs (without using the structure theorem), and argue that the existence of such a strategy implies existence of polynomial-time approximation schemes for a number of optimization problems.

Dusan Knop: Integer Programming in Parameterized Complexity: Three Miniatures

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools.

Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Sum Coloring by modeling it as a convex program in fixed dimension, n-fold integer programs, and as ILP with bounded dual treewidth and graver complexity.

Pierre Simon: Towards a classification of geometric homogeneous structures

We call a homogeneous structure geometric (or NIP) if it has polynomially many types over finite sets, or equivalently at most exponential growth of the number of finite substructures. Such structures are usually order-like or tree-like. I will present the first step in the classification of the order-like case. As an example, the classification of primitive homogeneous multi-orders, as well as of their reducts, follows at once from it. I will end with a few open problems.

Jan Kynčl: The Z2-genus of Kuratowski minors (slides)

A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t\times t grid or one of the following so-called t-Kuratowski graphs: K3,t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the Z2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani--Tutte theorem on orientable surfaces. These results were obtained together with Radoslav Fulek.

Andreas E. Feldmann:The Parameterized Hardness of the k-Center Problem in Transportation Networks

We study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph $G=(V,E)$ and an integer $k$ are given and a center set $C\subseteq V$ needs to be chosen such that $|C|\leq k$. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers $k$, the highway dimension $h$, and even the treewidth $t$. Moreover, under the Exponential Time Hypothesis there is no $f(k,t,h)\cdot n^{o(t+\sqrt{k+h})}$ time algorithm for any computable function $f$. Thus it is unlikely that the optimum solution to k-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! (Joint work with Dániel Marx.)

Pavel Hubáček: On Constant-Round Statistical Zero-Knowledge

I will show how to overcome technical challenges when designing constant-round statistical zero-knowledge proofs. Specifically, I will describe an unconditional transformation from any honest-verifier statistical zero-knowledge protocol to a protocol where the statistical zero-knowledge property holds against arbitrary verifiers. Based on joint work with Alon Rosen and Margarita Vald.

Günter Rote: Lattice Paths with States, and Counting Geometric Objects via Production Matrices (slides)

We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state q, there is a finite set S(q) of allowable "steps" ((i,j),q'). This means that from any point (x,y) in state q, we can move to (x+i,y+i) in state q'. We want to count the number of paths that go from (0,0) in some starting state q0 to the point (n,0) without going below the x-axis. Under some natural technical conditions, I conjecture that the number of such paths is asymptotic to C^n/sqrt(n^3), and I will show how to compute C.

I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices.

This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

Robert Šámal: A rainbow version of Mantel's Theorem (slides)

Mantel's Theorem asserts that a simple $n$ vertex graph with more than~$\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$. We provide an example to show this bound is best possible.

Yelena Yuditsky: Almost all string graphs are intersection graphs of plane convex sets

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on $n$ vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on $n$ vertices are intersection graphs of plane convex sets.

This is a joint work with János Pach and Bruce Reed.

Dragan Mašulović: Finite big Ramsey degrees in universal structures (slides)

Let F be a countable ultrahomogeneous relational structure. A positive integer n is a big Ramsey degree of a finite structure A in Age(F) if n is the least integer such that for every k > 1 and every coloring of copies of A in F with k colors there is a copy F' of F sitting inside F such that at most n colors are used to color the copies of A that fall within F'. If such an integer exists we say that A has finite big Ramsey degree in F.

For example, Devlin proved in 1979 that finite chains have finite big Ramsey degrees in Q, Sauer proved in 2006 that finite graphs have finite big Ramsey degrees in the Rado graph, and Dobrinen has just recently proved that finite triangle-free graphs have finite big Ramsey degrees in the Henson graph H_3.

In this talk we consider the context where F is a countable structure universal for a class of finite structures, but not necessarily a Fraisse limit. For each of the following classes of structures: acyclic digraphs, finite permutations, a special class of finite posets with a linear order extending the poset relation, and a special class of metric spaces we show that there exists a countably infinite universal structure S such that every finite structure from the class has finite big Ramsey degree in S.

José Aliste: Rooted U-polynomials

The U polynomial was introduced by Noble and Welsh in 1999 and it generalizes the chromatic symmetric function of Stanley. It is an open question whether there exist non-isomorphic trees with the same U-polynomial. In this talk, we truncate the U-polynomial and for each k, we find pairs of non-isomorphic trees with the same truncation of the U-polynomial. To construct these trees we introduce and study the rooted U-polynomial for rooted trees and prove several algebraic formulas that allow for simple computations of rooted polynomials, which can later be used to deduce properties of the non-rooted versions U-polynomials of the trees involved.

Andres Aranda: HE and MB-homogeneous graphs

HE-homogeneous structures satisfy that any homomorphism between finite induced substructures extends to a surjective endomorphism. In MB-homogeneous structures, any monomorphism between finite induced substructures extends to a bijective endomorphism. In this talk, I will show that all MB-homogeneous graphs are HE-homogeneous and all "interesting" (i.e., not a union of cliques) HE-homogeneous graphs are MB-homogeneous.

Jan Volec: Fractional colorings vs. Hall ratio

If G is an n-vertex graph with the chromatic number k and the independence number a, then k >= n/a . However, for many graphs G this bound can get very bad, and it is easy to show there is in no function g which would upper-bound the chromatic number by g(n/a).

In this talk, we study a relation between the fractional chromatic number, which can be viewed as a relaxation of the chromatic number, and a hereditary variant of the ratio between the number of vertices and the independence number, called the Hall ratio. By averaging, the Hall ratio is always a lower bound on the fractional chromatic number. In 2009, Johnson asked if the fractional chromatic number can be also upper-bounded by a linear function of the Hall ratio, and in 2016, Harris conjectured that this should be the case. We disprove Harris conjecture, and discuss further problems concerned with the relation between these two parameters.

This talk is based on joint works with J. Balogh, A. Kostochka, S. Norin and A. Blumenthal, B. Lidicky, R. Martin, Y. Pehova, F. Pfender.

Pavel Veselý: Online packet scheduling

In the online bounded-delay packet scheduling problem (PacketScheduling),the goal is to schedule transmissions of packets that arrive over time in a network switch to be sent across a link. Each packet has a deadline, representing its urgency, and a weight, representing its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to maximize the total weight of transmitted packets. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm.

We solve this open problem by presenting a $\phi$-competitive online algorithm for PacketScheduling (where $\phi\approx 1.618$ is the golden ratio), matching the previously established lower bound.

Joint work with Marek Chrobak, Łukasz Jeż, and Jiří Sgall

Pavel Valtr: The exact chromatic number of the convex segment disjointness graph

Let P be a set of n points in strictly convex position in the plane. Let D_n be the graph whose vertex set is the set of all line segments with endpoints in P, where disjoint segments are adjacent. The chromatic number of this graph was first studied by Araujo, Dumitrescu, Hurtado, Noy, and Urrutia [2005] and then by Dujmovic and Wood [2007]. Improving on their estimates, we prove the following exact formula for the chromatic graph of D_n: \chi(D_n)=n-[\sqrt{n+1/4}-1/2]. Joint work with Ruy Fabila-Monroy, Jakob Jonsson, and David Wood.

Previous Workshops

Webmaster: kamweb@kam.mff.cuni.cz         Modified: 26. 07. 2019