10 avril 2025: Daria Pchelina et François Pirot

par Daria Pchelina (CNRS, ENS Lyon), Francois Pirot (Université Paris Saclay)

jeudi 10 avr. 2025, 14:00 → 17:00 Europe/Paris

14h00 Daria Pchelina CNRS, ENS de Lyon

Optimal disc and sphere packings

How can we arrange an infinite number of spheres to maximize the proportion of space they occupy? Kepler conjectured that the "cannonball" packing is the optimal way to do it. This conjecture remained unproved for almost 400 years until Hales and Ferguson provided a 250-page proof accompanied by hundreds of thousands of lines of computer code. Given an infinite number of coins of three fixed radii, how can we place them on the plane to maximize the proportion of the covered surface? A disc packing is called triangulated if its contact graph is triangulated. We identified optimal packings for several triplets of disc sizes, all of which are triangulated. Conversely, we also showed that for certain other triplets, no triangulated packing is optimal. Building on our expertise in multi-size disc packings, we extend our research to two-sphere packings. Simplicial sphere packings are those whose contact graphs form pure simplicial 3-complexes. We consider the only ratio of sphere sizes that allows such packings which are conjectured to be optimal.

 

15h30 François Pirot Université Paris-Saclay

Fractional Domatic Number and Minimum Degree

Given a graph G, a dominating set of G is a set X⊆V(G) such that N[X]=V(G). Dominating sets are often used to model monitoring problems in networks. A classical problem in graph theory is to find the minimum size γ(G) of a dominating set of G, called the domination number of G. A possible approach to this problem is to study a stronger parameter, the domatic number of G, which is the maximum number of pairwise disjoint dominating sets of G. In this talk, I will present the fractional relaxation of this parameter, the fractional domatic number, and study its extremal value with respect to the minimum degree of G. I will present an asymptotically tight bound, and then focus on graphs G of minimum degree 2, showing that they all have fractional domatic number at least 5/2 unless at least one of 8 bad graphs appears as an isolated component in G. This is joint work with Quentin Chuet, Hugo Demaret, and Hoang La.