Graphes@Lyon is the graph theory seminar jointly organized by the MC2 team at LIP and the GOAL team at LIRIS.
Local organizers: Théo Pierron (LIRIS), Jean-Florent Raymond (MC2), and Rémi Watrigant (MC2). Contact us if you want to give a talk!
Upcoming talks
Alexander Crane: Probabilistic Network Design
- When: 26/09/2025 at 14:00
- Where: Amphi A1, ENS de Lyon
- Who: Alexander Crane (University of Utah)
- What: Probabilistic Network Design
Probabilistic graphs allow us to model randomized propagation
in graphs, for example communication in lossy networks or the spread of
information in a social network. In a realization of a probabilistic
graph G = (V, E, p), each edge in E is said to be “active”
independently with probability p. The proximity of a vertex pair u, v
is the probability with which there exists a uv-path consisting
entirely of active edges. The reach of G is the minimum proximity
across all vertex pairs.
In this talk, we will cover some recent approximation results on a
natural network design question in this setting: given a probabilistic
graph G and a budget k, how can we choose k edges to add to G such that
the reach of the resulting graph is maximized? The results rely on
connections to the k-center clustering problem, with an assist from
tools developed in percolation theory.
Past talks
Lifting maps between graphs to embeddings
- When: 19/06/2025 at 10:30
- Where: Room B1, ENS de Lyon
- Who: Alexey Gorelov (Institut Fourier)
- What: Lifting maps between graphs to embeddings
Let $f \colon G \to H$ be a graph homomorphism. In general, $f$ is not injective. The goal is to transform $f$ into an embedding by introducing a new dimension, that is, replacing $H$ by the space $|H| \times \mathbb{R}$, and perturbing $f$ along the new dimension. This task was originally motivated by similar problems in topology, which were in turn motivated by the classical embeddability question. Our problem can be reformulated in a purely combinatorial way. A \emph{combinatorial lifting} of $f \colon G \to H$ is a collection of linear orders $<_{v}$ on $f^{-1}(v)$ for all $v \in V(H)$ such that no crossings occur. A crossing is a pair of edges $x_1 y_1, x_2 y_2 \in E(G)$ with $f(x_1) = f(x_2) = v$, $f(y_1) = f(y_2) = w$, and $x_1 >_v x_2$ while $y_1 <_w y_2$. We study the computational complexity of deciding whether such a lifting exists. In a former work, we showed that this problem is NP-complete in general. However, for the special case of maps from trees to path graphs, we proved a complete criterion that can be checked in polynomial time. Our approach relies on combining and transforming liftings, a technique that may be of independent interest.
Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets & Variants of Maker-Breaker games on complete and random graphs
- When: 22/05/2025 at 14:00
- Where: LIRIS
- Who (1st speaker): Malory Marin (LIP)
- What: Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
Given a graph G, the hard-core model defines a probability distribution over its independent sets, assigning to each set of size k a probability of λ^k/Z, where λ>0 is a parameter known as the fugacity and Z is a normalization constant. The Glauber dynamics is a simple Markov chain that converges to this distribution and enables efficient sampling. Its mixing time–the number of steps needed to approach the stationary distribution–has been widely studied across various graph classes, with most previous work emphasizing the dichotomy between polynomial and exponential mixing times, with a particular focus on sparse classes of graphs.
We investigate subexponential mixing times of the Glauber dynamics on geometric intersection graphs, such as disk graphs. We also study parameterized mixing times by focusing on two structural parameters that can remain small even in dense graphs: the tree independence number and the path independence number. We show that Glauber dynamics mixes in polynomial time on graphs with bounded path independence number and in quasi-polynomial time when the tree independence number is bounded. Moreover, we prove both bounds are tight, revealing a clear separation between the two parameters.
- Who (2nd speaker): Yannick Mogge (LIRIS)
- What: Variants of Maker-Breaker games on complete and random graphs
In this talk we discuss two variants of Maker-Breaker games: fast strategies in Waiter-Client games, as well as a result for Connector-Breaker and Walker-Breaker games.
Waiter-Client games are played on some hypergraph $(X, \mathcal{F})$, where $\mathcal{F}$ denotes the family of winning sets. During each round of the game, Waiter offers two elements of $X$ to Client, from which she claims one for himself and the other element goes to Waiter. Waiter wins the game, if he can force Client to claim all the elements of a winning set from $\mathcal{F}$.
We will discuss fast strategies for the Waiter-Client Hamiltonicity game on the edges of the complete graph $K_n$, and we will show that Waiter can force Client to claim a Hamilton cycle within $n+1$ rounds.
Connector-Breaker and Walker-Breaker games are defined similarly to Waiter-Client games on graphs, but in each round both players claim some predefined number of edges for themselves, with the additional restriction that Connector (or Walker) has to play in such a way that her graph stays connected throughout the game (or according to a walk). We will discuss the $(2:2)$-biased version of those games (where both players claim two edges of the graph in each turn) on a random graph $G \sim G_{n,p}$ and we will show that the threshold probabilities for Connector/Walker to claim a Hamilton cycle are of order $n^{-2/3 + o(1)}$.
See the archives.