14:00
15:00

/Exposé /Talk/

A seminal result of Komlos, Sarkozy and Szemeredi proves that for any \Delta and \alpha, any graph G with minimum degree (1/2+\alpha)n and large enough n contains all n-vertex trees of maximum degree \Delta. Given two graphs H and G, recent advances on the Kahn-Kalai conjecture connect the existence of /spread measures/ on the space of embeddings of H in G, with the probabilistic threshold above which a random subgraph of G, obtained by sampling the edges at a fixed rate, still contains H with good probability. Spread distributions also give a lower bound on the number of embeddings of H in G. In 2023, Pham, Sah, Sawhney and Simkin designed a spread measure on the embeddings of bounded degree trees in graphs of minimum degree (1/2+\alpha)n, by following the proof of Komlos /et al/.

We give a regularity free proof of this result. As a result, we obtain much better constants, with a more flexible framework and unlike the proof of Pham /et al./, our construction generalises to hypergraphs and digraphs painlessly.

This is joint work with Paul Bastide and Alp Müyesser.

[Clément Legrand-Duchesne] (Université de Bordeaux, LaBRI )
https://www.labri.fr/perso/clemlegrand/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178