14:00
18:00

This thesis explores local structures in combinatorics, focusing on understanding how local configurations influence the global properties and structures of combinatorial objects. This thesis is divided into four parts, each investigating different problems related to local structures: distance reconstruction, poset saturation, spread embedding, and universal structures.
In the chapter related to distance reconstruction, we seek to reconstruct an unknown graph using local information. We only have access to an oracle providing the shortest path distances between pairs of vertices.
We study this problem for different classes of graphs, improving both the best-known lower bounds and upper bounds in various cases. In particular, we provide an optimal algorithm for reconstructing trees and a near-optimal algorithm for reconstructing graphs without long induced cycles.
Then, we study poset saturation, introduced by Katona and Tarjan in 1981. This concept extends Turán’s seminal work in extremal graph theory. A P -saturated family is a maximal family that avoids any substructure locally isomorphic to P (i.e., avoids P as an induced subposet). We study the saturation number of a poset P , defined as the minimum size of a P -saturated family included in the hypercube of dimension n. Despite substantial work on this problem in recent years, the saturation number is only known exactly for small posets, and its possible behaviors are still largely unknown. In this thesis, we will show that an extension of a lemma from Lehman and Ron allows us to compute exactly the saturation number of the antichain of size k. We also prove the first general upper bound on the possible behavior of the saturation number for any poset P.
In the chapter on spreadness, we study the distribution of spanning trees in dense graphs. It might seem, at first, far from local, as a “spanning” structure is by definition global, but the key technique we developed to construct these global spanning structures goes through the subdivision into multiple local substructures. Via this novel method, we are able to give a simpler and more flexible proof of the existence of spread embeddings for bounded-degree trees. In particular, our approach does not use Szemerédi’s Regularity Lemma.
Finally, we study universal structures. Given a family F of combinatorial objects and an integer n, another object U is said to be universal if it contains every element of F of size n as a local substructure. We call such a structure "faithful" when U is also part of F. In this chapter, we study the minimum size of faithful universal graphs for minor-closed classes of graphs as well as the size of universal posets for the family of all posets.


 

Amphi LaBRI