# Midsummer Combinatorial Workshop XXIV

July 29 - August 2, 2019, Prague

August 5: Gena and Robert Day celebrating the 70th birthday of Robert Woodrow and Gena Hahn

## Programme

All lectures take place in room S5 at the building of Charles University, Malostranske namesti 25.
Monday
8:30-9:20 Registration
9:20-9:30 Welcome, brief information about program of the workshop
9:30-9:55 Stanislav JendrolFacial total colorings of plane graphs
10:00-10:25 Peter ZemanAutomorphism groups of maps in linear time
10:30-11:00 Coffee break
11:00-11:25 Tomas MasarikDiversity in Combinatorial Optimization
11:30-11:55 Natasha DobrinenSome Ramsey theory on infinite graphs
12:00-12:25 Pierre SimonA conjecture on linearly ordered structures
12:30-12:55 Marcin SabokMeasurable Hall's theorem for actions of abelian groups
Tuesday
9:00-9:25 Robert SamalThe binary paint shop problem (slides)
9:30-9:55 Bojana PanticTowards the classification of polymorphism-homogeneous metric spaces (slides)
10:00-10:25 Manuel BodirskyA universal-algebraic approach to the feder-vardi-kun-bulatov-zhuk dichotomy for mmsnp
10:30-11:00 Coffee break
11:00-11:25 Dragan MasulovicCountable ordinals and big Ramsey degrees
11:30-11:55 Yibei LiAutomorphism groups of some homogeneous directed graphs
12:00-12:25 Rehana PatelOn recent work of Rebecca Coulson: Twist and shout
Wednesday
9:00-9:25 Adam KabelaForbidden pairs and perfect graphs
9:30-9:55 Yiting JiangMultiple list colouring of triangle free planar graphs
10:00-10:25 Johanna WieheThe NL-Coflow Polynomial (slides)
10:30-11:00 Coffee break
11:00-11:25 Hossein TeimooriAlebraic and topological tools in subgraph counting polynomials
11:30-11:55 Lluis VenaA characterization of extremal families of sets of fixed size minimizing their lower shadow
14:15Departure to Brevnov monastery: Details to be announced
15:00-16:15Brevnov monastery tour
18:00-WORKSHOP DINNER: At Vila Kajetanka
Thursday
9:30-9:55 Davis IssacParameterized complexity of biclique cover and partition
10:00-10:25 Hoi Ping LukTilings of the Sphere by Almost Equilateral Pentagons
10:30-11:00 Coffee break
11:00-11:25 Dusan KnopStructural Parameterizations of Stable Roommates with Ties
11:30-11:55 Rongxing XuHomomorphism of $K_4$-minor free graphs
12:00-12:25 Andres ArandaIB-homogeneous graphs
Friday
9:00-9:25 Manfred ScheucherUsing SAT Solvers in Combinatorics and Geometry (slides)
9:30-9:55 Huajing LuThe Alon-Tarsi number of planar graphs without cycles of length 4 and l
10:00-10:25 Helena BergoldTopological Drawings meet Classical Theorems of Convex Geometry (slides)
10:30-11:00 Coffee break
11:00-11:25 Jozsef SolymosiOn the Erdos-Szemeredi sum-product conjecture elong edges of graphs
Monday, Aug 5 (Gena and Robert Day)
9:30-9:55 Jozef SiranLarge Cayley graphs of given degree and diameter
10:00-10:30 Andres ArandaFraisse theorems galore
10:30-11:00 Coffee break
11:00-11:30 Jan KratochvilRobber chasing
11:40-12:20 Reza NaserasrHomomorphisms of signed graphs
Lunch (provided)
14:00-14:30 Erin MegerThe Iterated Local Model for Social Networks
14:40-14:55 Jaroslav NesetrilJust a few mathematical memories
Gena + Robert
Reminiscences
18:00-Dinner at Nebozizek restaurant

## 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.

### Facilities

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

• Two open lounges with tables, chairs and a whiteboard opposite the Lecture Room S5. You can take the lounges on a first come, first serve basis. Great for working on open problems in the afternoon!
• Two open lounges with tables, chairs and a whiteboard on the third floor, directly above the lounges on the second floor. Same rules apply.
• Water coolers in the hall with the open lounges -- both on second and third floor.

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

• Take bus number 119 to Nadrazi Veleslavin station (last stop).
• Transfer to Metro subway A (green line) and take it to the station Namesti Miru.
• Take the tram 22 (direction: Kubanske namesti) for one stop to the tram stop Jana Masaryka (location here), and walk to the hotel (hotel location here) from that stop.
• Alternately: for a faster but slightly longer walk, you can walk from the station Namesti Miru as follows: Take the Americka street and when you reach the intersection with Machova street, your hotel is nearby (hotel location here).

Marianeum Hotel -> MCW

• Walk to the tram stop Jana Masaryka (location here)
• Take the tram 22 (direction: Kralovka) to the stop Malostranske namesti.

Airport -> Karolinum Hotel

• From airport to Karolinum take bus number 119 to Nádrazi Veleslavín station (last stop).
• Transfer to Metro subway A (green line) and take it to the station Staromestska.
• Exit the subway and continue on foot:
• Take the Kaprova street to the Old Town Square.
• From the Old Town Square go through the Celetna street to your hotel.

Karolinum Hotel -> MCW

• Walk to the Subway station Staromestska.
• Take the Metro subway line A (direction: Nemocnice Motol) to Malostranska.
• Exit the subway at Malostranska and take one stop with any of the following trams: 12, 20 or 22 to Malostranske namesti.

## Contact

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

organizers: Jaroslav Nesetril, Jan Hubicka, Matej Konecny

## Abstracts

### Andres Aranda: Fraisse theorems galore

I will present a new Fraisse-type theorem for IB-homogeneous relational structures and how the conceptual framework that it suggests can be used to produce Fraisse theorems in the 18 homomorphism-homogeneity classes defined by Lockett and Truss.

### Davis Issac: Parameterized complexity of biclique cover and partition

A biclique of a graph is a complete bipartite subgraph of it.We look at the problems of covering and partitioning the edges of a bipartite graph with bicliques. These problems are called biclique cover and biclique partition respectively. The problems are equivalent to computing binary factorization of binary matrices over boolean arithmetic and standard integer arithmetic respectively. Both the problems have many applications in a variety of fields such as display optimization and data compression and mining. We study the problems from the point of view of parameterized complexity, where the parameter is taken to be the size of the cover or partition. It was known that both problems are fixed parameter tractable but the algorithms had running times that had a doubly exponential dependence on the parameter $k$. We show an algorithm for biclique partition that has only $\mathcal{2^{k^2}}$ dependence on $k$. For biclique cover, we show that no improvement over the doubly exponential dependence is possible, by giving a reduction from $3$-SAT on $n$ variables to an instance of biclique cover with the parameter $k=\log n$. We also give kernel lower bounds for biclique cover. I will point out some interesting open problems related to the above problems.

### Yiting Jiang: Multiple list colouring of triangle-free planar graphs

Colouring of triangle free planar graphs has been studied extensively in the literature. It was proved by Gr\"{o}tzsch that every triangle free planar graph is $3$-colourable. On the other hand, Voigt showed that there are triangle free planar graphs that are not $3$-choosable. What we are interested in is multiple list colouring of triangle free planar graphs. We prove that for each positive integer $m$, there is a triangle free planar graph $G$ which is not $(3m+ \lceil \frac m{17} \rceil -1, m)$-choosable.

### Yibei Li: Automorphism groups of some homogeneous directed graphs

We will introduce the notion of a stationary weak independence relation on a homogeneous structure. Then we will generalise a theorem by Tent and Ziegler to the stationary weak independence relation and apply the theorem to some directed graphs proposed by Cherlin.

### Huajing Lu: The Alon-Tarsi number of planar graphs without cycles of length 4 and l

In this talk we discuss the Alon-Tarsi number of some subgraphs of planar graphs. We prove that if $G$ is a planar graph without 4-cycles and $l$-cycles for some $l\in\{5, 6, 7\}$, then there exists a matching $M$ such that $AT(G-M)\leq 3$. This implies that every planar graph without 4-cycles and $l$-cycles for some $l\in\{5, 6, 7\}$ is 1-defective 3-paintable.

### Tomas Masarik: Diversity in Combinatorial Optimization

Joint work with J. Baste, M.R. Fellows, L. Jaffke, M. de Oliveira Oliveira, G. Philip, F.A. Rosamond

### Dragan Masulovic: Countable ordinals and big Ramsey degrees

In this talk we consider big Ramsey degrees of finite chains in certain countable ordinals. The first result in this direction is, of course, the infinite version of Ramsey's theorem which claims that finite chains all have the big Ramsey degree 1 in $\omega$. Another important step in this direction was Laver's result on divisibility of scattered chains which claims that the one-element chain has finite big Ramsey degree in any countable scattered chain. Scattered countable chains are of particular interest since the situation with non-scattered chains can be resolved fairly easily: non-scattered countable chains have the same finite big Ramsey degrees as the chain of rationals, where the big Ramsey degrees were explicitly computed by Devlin. Along the way we prove a result that we see as an infinite analogue of the Finite Product Ramsey Theorem.

### Erin Meger: The Iterated Local Model for Social Networks

On-line social networks such as Facebook and Twitter are often studied through friendships between users. Adversarial relationships also play an important role in the structure of these social networks. We define the Iterated Local Model (ILM) utilizing the transitive and anti-transitive generative mechanisms within social networks. These mechanisms provide a precise analogy to the adages "the enemy of my enemy is my friend," and "friends of friends are friends." Complex networks exhibit four key properties: large scale, evolution over time, power law degree distribution, and the small world property. Densification is also observed in complex networks, where the average degree of the network increases over time. Each of these properties will be discussed for the ILM. Structural properties of the graphs generated by ILM, including the hamiltonicity and the chromatic number, will also be explored.

### Reza Naserasr: Homomorphisms of signed graphs

I will introduce an extension of notion of homomorphism from graphs to signed graphs. After presenting some basic no-homomorphism lemmas we will have a look at the following question: when and for which families of signed graphs do these necessary conditions (provided by the no-homomorphism lemmas) become sufficient?

### Marcin Sabok: Measurable Hall's theorem for actions of abelian groups

I will discuss a measurable version of the Hall marriage theorem for actions of abelian groups. In particular, it implies that for free measure-preserving actions of such groups, if two equidistributed measurable sets are equidecomposable, then they are equidecomposable using measurable pieces. The latter generalizes a recent result of Grabowski, Máthé and Pikhurko on the measurable circle squaring and confirms a special case of a conjecture of Gardner. This is joint work with Tomasz Ciesla.

### Robert Samal: The binary paint shop problem

Joint work with J. Hancl, A. Kabela, M. Opler, J. Sosnovec, P. Valtr

### Jozef Siran: Large Cayley graphs of given degree and diameter

In the early 90's we made an observation with Gena Hahn that every sharply $2$-transitive group $G$ admits a Cayley (di)graph $C(G,S)$ of diameter $2$ and degree $|S| \sim \sqrt{|G|}$. In the talk we will survey the progress made in this direction over time.

### Jozsef Solymosi: On the Erdos-Szemeredi sum-product conjecture elong edges of graphs

In their seminal paper Erdos and Szemeredi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this talk we show that this strong form of the Erdos-Szemeredi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets and ratio sets along the edges of graphs. Joint work with Noga Alon and Imre Ruzsa

### Peter Zeman: Automorphism groups of maps in linear time

By a map we mean a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, then every automorphism of a map determines an angle-preserving homeomorphism of the surface. We present a linear-time algorithm computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. We reconstruct the automorphism group of the original map from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. This is a joint work with Ken-ichi Kawarabayashi, Bojan Mohar, and Roman Nedela.

## Previous Workshops

Webmaster: kamweb@kam.mff.cuni.cz         Modified: 09. 03. 2020