In Paris, IRIF, Room 11 of Batiment Sophie Germain
The people coming.
In May 2019, 15th to 17th
Informal atmosphere with free time to work & cooperate. See the programme.
bla
bla
10h | Patrice Ossona de Mendez |
---|---|
11h-11h20 | Cofee Break |
11h30 | Edita Mačajová |
13h00 | Lunch |
14h00 | Open Problem Session |
15h | Ross J. Kang |
16h00 | Coffee Break | 17h00 | Gwen Joret |
9h15 | Tomas Kaiser |
---|---|
10h | Frédéric Havet |
11h | Coffee Break |
11h30 | Alex Scott |
12h45 | Lunch |
14h00 | Pierre Charbit's habilitation defence |
10h | Sebastian Siebertz |
---|---|
11h | Coffee Break |
11h30 | Tobias Müller |
12h45 | Lunch |
14h00 | Discussion time |
A natural way to try to weaken list colouring is by forcing that neighbouring lists not share too many colours. Of course, constraining such pairs of lists to have no colours in common makes the list colouring problem trivial! However even allowing at most one common colour per pair the problem retains qualitative similarities to classical list colouring, but rescaled somehow. We discuss this in two concrete settings. One is in terms of extending, or rather attempting to extend, Alon's "degrees and choice number" theorem. This has led to a surprising and natural question on triangle-free graphs, which has since attracted a lot of attention. The other is in terms of a "correspondence" variant of the problem, where we could make some progress for graphs on surfaces. It turns out that this variant is closely related to finding independent transversals under the assumption that the partition graph has bounded maximum average degree. This talk discusses joint work with Esperet and Thomassé, with Dvorak, Esperet and Ozeki, and with Kelly. Slides
The starting point of this talk is the following recent result: Every planar graph is a subgraph of the strong product of some graph of bounded treewidth and a path. After sketching its (simple) proof, I will present two applications of this result, namely that planar graphs have bounded queue-number and bounded nonrepetitive chromatic number. This talk is based on joint works with Dujmović, Esperet, Micek, Morin, Ueckerdt, Walczak, and Wood. Slides
Permutation graphs are cubic graphs that admit a 2-factor consisting of two chordless cycles. Despite the simple structure, edge-colouring problems regarding permutation graphs are nontrivial (infinitely many permutation graphs are snarks), but at least in some cases they are more tractable than for cubic graphs in general. In this talk, we will discuss known results and some open problems regarding (list) edge colouring of permutation graphs. Slides
A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is (n+k-1)-unavoidable. We then prove that every oriented tree of order n≥2 with k leaves is (³⁄₂·n+³⁄₂·k -2)-unavoidable and (⁹⁄₂·n -⁵⁄₂·k -⁹⁄₂)-unavoidable, and thus (²¹⁄₈·n- ⁴⁷⁄₁₆)-unavoidable. Finally, we prove that every oriented tree of order n with k leaves is (n+ 144k² - 280k + 124)-unavoidable. This is joint work with François Dross. Slides
In my talk, I will describe some recent and ongoing work on random geometric graphs and Poisson-Voronoi percolation in the hyperbolic plane. Random geometric graphs are obtained by taking a random set of points in the plane (usually either generated by a Poisson process or sampled i.i.d. uniformly from a large disk or square), and then joining any pair of points by an edge whose distance is less than some parameter r > 0. In the Poisson-Voronoi percolation model, we take a constant intensity Poisson process and assign to each point its Voronoi-cell, that is the set of all points closer to it than to any other Poisson point, and then we flip a coin for each cell to determine whether it will br coloured black or white. We say that percolation occurs if the set of black cells contains an unbounded component. For both these models it turns out that the hyperbolic versions display behaviour that is spectacularly different from their Euclidean counterparts. (Based on recent and ongoing works with M. Bode, E. Broman, N. Fountoulakis, B. Hansen, P. van der Hoorn, D. Mitsche, J. Tykesson, M. Schepers.) Slides
It is well known that a graph on n vertices need not have complete subgraphs or independent sets of size more than about log n. But what if we consider graphs which do not contain some specific induced subgraph? Erdos and Hajnal conjectured in the 1980s that for every graph H there is a constant c such that every graph on n vertices without an induced copy of H contains a clique or stable set of size nc. The Erdos-Hajnal conjecture is still very much open, but we will discuss some recent progress and related results. Joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.
The Fulkerson conjecture belongs to one of the most prominent open problems in Graph theory. It suggests that the edges of any bridgeless cubic graph can be covered with six perfect matchings in such a way that each edge belongs to exactly two of them. Despite the fact that Berge and Fulkerson made this conjecture almost half a century ago, it has been verified only for several explicitly defined families of graphs. During the talk we will present the current state of this conjecture as well as its connections to other important conjectures in graph theory. As the main result we show that Fulkerson's conjecture can be reduced to cyclically 5-edge-connected cubic graphs. This is a joint work with Giuseppe Mazzuoccolo. Slides
We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications: like the existence of low shrub-depth decompositions for tranductions of bounded expansion classes and the characterization of transductions of classes with bounded pathwidth. Slides