Proper vertex coloring with odd occurrence - Probabilistic approach
summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints. A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors. For a graph G, the chromatic number χ(G) is ...
Some results on directed coloring
summary: Proper coloring of undirected graphs lies among the most studied
problems in graph theory. It asks to color vertices while giving
different colors to adjacent ones.
In 1982, Neumann-Lara introduced a generalization of this problem to
directed graphs. When walking in an undirected graph, an undirected edge
between two ...
Associaèdres cycliques et degrés intrinsèques des arborescences non-croisées
Le polytope de pivot d'un polytope P est une généralisation de son polytope des chemins monotones qui vise a capturer le comportement de la "shadow vertex rule" (une règle de pivot importante en optimisation linéaire et dans le domaine des polytopes de fibre). Il a récemment été montré que ...
Walking On A Line: finding S-adic walks in an ω-automaton
summary: At the heart of symbolic dynamics lies the study of languages, infinite words and the dynamical structures associated. We focus on two classical methods to generate such structures. The first one relies on substitutions, which are morphisms on words, by iterating one on an initial letter, and considering the ...
Séminaire ouvert
Lors d'un séminaire ouvert, le thème n'est pas décidé à l'avance. Tous les membres du séminaires sont invités à participer et peuvent proposer le jour même des interventions plus ou moins longues, des démos ou des questions ouvertes au reste de l'équipe.
Realizing Geometrically s-Permutahedra via Flow Polytopes
summary: In 2020, Ceballos and Pons defined s-decreasing trees with s being a weak composition. They described an order on these objects called the s-weak order which gives them the order structure of a lattice. They further conjectured that this structure could be realized geometrically as the 1-skeleton of a ...
Density of sphere packings: from coins to oranges
summary: How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the "cannonball" packing is an optimal way to do it. This conjecture took almost 400 years to prove and the proof of Hales and Ferguson consists of 6 papers and ...
A realization of poset associahedra as sections of graph associahedra
Poset associahedra are a family of convex polytopes introduced by Pavel Galashin in 2021, each one associated to a partially ordered set, that generalize the classical associahedron. Galashin describes the combinatorial structure of poset associahedra, and he realizes them as convex polytopes. However, his construction is not completely satisfactory. In ...
(q,t)-symmetry in triangular partitions
We study the \((q,t)\) enumeration of the Triangular Dyck paths, i.e. the sub-partitions of the so-called triangular partitions discussed by Bergeron and Mazin. This is a generalization of the general \((q,t)\) enumeration of Catalan objects. We present new combinatorial notions such as the triangular tableau and the ...
An introduction to twin-width in graphs via the study of highly inapproximable problems
summary: The goal of this seminar is to introduce the graph parameter "twin-width", defined by Bonnet et al. in 2020. The collection of graphs with bounded twin-width generalizes many well-known families of graphs : planar, bounded treewidth and cliquewidth, unit interval,... The first motivation behind this parameter was that FO-expressible NP-hard ...