In Strasbourg, CIARUS Center
The people coming.
In November 2017, 5th to 8th
Informal atmosphere with free time to work & cooperate. See the programme. Here is the outcome of the Problem Session
bla
bla
10h | Patrice Ossona de Mendez |
---|---|
11h-11h20 | Cofee Break |
11h30 | Tobias Muller |
13h00 | Lunch |
14h00 | Open Problem Session |
15h | Tomas Kaiser |
16h00 | Coffee Break |
10h | Andrew Goodall |
---|---|
11h | Coffee Break |
11h30 | François Pirot |
12h45 | Lunch |
14h00 | Frédéric Havet |
15h00 | Zdeněk Dvořák |
16h30 | Matěj Konečký |
10h | Alfredo Hubard |
---|---|
11h | Coffee Break |
11h30 | Rémi de Joannis de Verclos |
12h45 | Lunch |
We follow Tutte’s footsteps in how he created his “dichromate” (the Tutte polynomial) as a simultaneous generalization of the chromatic polynomial and flow polynomial, counting colour- ings and flows of graphs. Only this time we shall count the analogues of colourings and flows for maps (graphs 2-cell embedded in surfaces). We end up with a multivariate polynomial – a “dichromate for maps” – that, like the Tutte polynomial of a graph, contains combinatorially significant specializations other than the colourings and flows it was defined to capture at the outset. We wonder what other combinatorial and topological juices can be extracted from it. This talk will be a broad-brush sketch of some recent work with Guus Regts, Lluis Vena, Thomas Krajewski and Bart Litjens.
We follow Tutte’s footsteps in how he created his “dichromate” (the Tutte polynomial) as a simultaneous generalization of the chromatic polynomial and flow polynomial, counting colour- ings and flows of graphs. Only this time we shall count the analogues of colourings and flows for maps (graphs 2-cell embedded in surfaces). We end up with a multivariate polynomial – a “dichromate for maps” – that, like the Tutte polynomial of a graph, contains combinatorially significant specializations other than the colourings and flows it was defined to capture at the outset. We wonder what other combinatorial and topological juices can be extracted from it. This talk will be a broad-brush sketch of some recent work with Guus Regts, Lluis Vena, Thomas Krajewski and Bart Litjens.
Mader proved that every graph with sufficiently large minimum degree (resp. chromatic number) contains a subdivision of the complete graph on k vertices. This result does not generalize to digraph since there are acyclic (i.e. with no subdivision of the complete digraph on 2 vertices) digraphs with arbitrarily large out-degree and arbitraly large chromatic number. Hence a natural question is which digraphs are δ+-maderian (resp χ-maderian) that is such that every digraph with large minimum out-degree (resp. chromatic number) contains a subdivision of D. In this talk, we will survey the results around this problem
We say that a graph property is expressible in the “first order language of graphs” if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes of the graph, the usual connectives AND, OR, NOT, parentheses and the relations = and ∼, where x ∼ y means that x and y share an edge. For example, the property that G contains a triangle can be written as ∃x,y,z : (x∼y) AND (x∼z) AND (y∼z). A classical result of Glebskii et al. 1969 and independently Fagin 1976 states that if one samples a graph on n vertices uniformly at random from all such graphs then every first order expressible graph property holds with probability tending to either zero or one (as n tends to infinity). Since then, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdős-Rényi model. A number of very attractive and surprising results have been obtained, and by now we have a fairly full description of the behaviour of first order expressible properties on this model. After describing some of these results, time permitting, I will discuss some recent and ongoing work where we try to see what happens both in other models of random graphs (such as random planar graphs, random perfect graphs, random geometric graphs, . . . ) and when one considers other (i.e. “higher order”) logics. (Based on joint works with S. Haber, P. Heinig, T. Luczak, M. Noy, A. Taraz)
Hoffmann-Ostenhof conjectured in 2011 that every connected cubic graph G admits an edge- decomposition into a spanning tree of G, a 2-regular subgraph and a matching. We outline a proof of the planar case of this conjecture and discuss some related problems. Joint work with Arthur Hoffmann-Ostenhof and Kenta Ozeki.
Order types are combinatorial invariants of finite point sets that appear in a number of contexts in combinatorial and computational geometry, for instance in the classification of polytopes, the computation of rectilinear crossing numbers of graphs, enumeration of triangulations, estimates on the k-set problem among may other problems. Limits of combinatorial objects appeared in the last decade as a tool to coursely translate extremal combinatorial problems into algebraic and analytic ones. In this talk I will consider order types from the point of view of limits of combinatorial objects. Concretely, I will first describe how using the flag algebra-semidefinite programming framework one can obtain new concrete results to old geometry problems. Then, guided by analogies with the theory of graphons, I will explain some connections between limits of order types and measure theory. This talk will be based on joint work with Xavier Goaoc, Rémi de Joannis de Verclos Jean- Sébastien Sereni, and Jan Volec.
We review some recent progress in the study of structural properties of sparse graphs and sketch recent exciting developments on “structural sparsity”, allowing to generalize tools used for sparse graphs to dense low complexity graphs
The iterated partite construction, the by far strongest hammer for proving the Ramsey property of various classes, essentially reduces the problem to finding and studying a way to fill the gaps in incomplete structures. Recently, the Ramsey expansions were found for all metric spaces from Cherlin’s large catalogue of metrically homogeneous graphs. Surprisingly, the completion procedures are described by an ordered semigroup on the set of distances. In this talk we shall introduce this result and discuss its connections to generalised metric spaces (over some ordered semigroups) and semigroup completions.
It is well known that you can colour a graph G of maximum degree D greedily with D+1 colors. Moreover, this bound is tight, since it is reached for example by the cliques. Johansson proved with a pseudo-random colouring scheme that you can colour triangle-free graphs of maximum degree D with no more than O(D/ log D) colours. This is tight up to a multiplicative constant, since you can pseudo-randomly construct a family of graphs of maximum degree D, arbitrarily large girth, and chromatic number bigger than cD/ log D, for some constant c. When you introduce the distance-t chromatic number of a graph G of maximum degree D, which is simply the chromatic number of Gt, you can be interested in finding similar bounds, and proving that they are tight. It is straightforward that Dt is an upper bound for the distance-t chromatic number, but determining how tight this bound is is far from being an easy problem. You may also wonder what happens to the bound of the distance-t chromatic number when you forbid some fixed lengths of cycles in your graph. The goal of my talk will be to give some answers to these natural questions.