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.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.
.jpg#/media/File:Profesní_dům_(Malá_Strana).jpg){kind=link}
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: IB-homogeneous graphs
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.
Helena Bergold: Topological Drawings meet Classical Theorems of Convex Geometry
Manuel Bodirsky: A universal-algebraic approach to the feder-vardi-kun-bulatov-zhuk dichotomy for mmsnp
Natasha Dobrinen: Some Ramsey theory on infinite graphs
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.
Stanislav Jendrol: Facial total colorings of plane graphs
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.
Adam Kabela: Forbidden pairs and perfect graphs
Dusan Knop: Structural Parameterizations of Stable Roommates with Ties
Jan Kratochvil: Robber chasing
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.
Hoi Ping Luk: Tilings of the Sphere by Almost Equilateral Pentagons
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?
Jaroslav Nesetril: Just a few mathematical memories
Bojana Pantic: Towards the classification of polymorphism-homogeneous metric spaces
Rehana Patel: On recent work of Rebecca Coulson: Twist and shout
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
Manfred Scheucher: Using SAT Solvers in Combinatorics and Geometry
Pierre Simon: A conjecture on linearly ordered structures
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
Hossein Teimoori: Alebraic and topological tools in subgraph counting polynomials
Lluis Vena: A characterization of extremal families of sets of fixed size minimizing their lower shadow
Johanna Wiehe: The NL-Coflow Polynomial
Rongxing Xu: Homomorphism of $K_4$-minor free graphs
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
- Midsummer Workshop XXIII - July 30 - August 3, 2018, Proceedings
- Midsummer Workshop XXII - July 31 - August 3, 2017
- Midsummer Workshop XXI - July 27 - July 31, 2015
- Midsummer Workshop XX - July 28 - August 1, 2014
- Midsummer Workshop XIX - July 29 - August 2, 2013
- Midsummer Workshop XVIII - July 30 - August 3, 2012
- Midsummer Workshop XVII - July 25 - July 29, 2011
- Midsummer Workshop XVI - July 26 - July 30, 2010
- Midsummer Workshop XV - July 27 - July 31, 2009
- Midsummer Workshop XIV - July 28 - August 1, 2008
- Midsummer Workshop XIII - July 30 - August 3, 2007
- Midsummer Workshop XII - July 25 - 29, 2005
- Midsummer Workshop XI - July 26 - 30, 2004
- Midsummer Workshop X - July 28 - August 1, 2003
- Midsummer Workshop IX - July 29 - August 2, 2002
- Midsummer Workshop VIII - July 30 - August 3, 2001
- Midsummer Workshop VII - August 7 - 11, 2000
- Midsummer Workshop VI - July 26 - 30, 1999
- Midsummer Workshop V - July 26 - August 2, 1997
- Midsummer Workshop IV - July 28 - August 2, 1996
- Midsummer Workshop III - August 24-20, 1995
- Midsummer Workshop II - July 24-30, 1994
- Midsummer Workshop I - July 25-30, 1993
Webmaster: kamweb@kam.mff.cuni.cz Modified: 09. 03. 2020