BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Spanning trees in pseudorandom graphs via sorting networks - Alp M
 uyesser (UCL)
DTSTART:20231116T143000Z
DTEND:20231116T153000Z
UID:TALK208378@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION: How pseudorandom does a graph need to be before it contains a
  certain spanning subgraph? This problem is not very well understood\, esp
 ecially in comparison to its purely random analogue. For example\, the bes
 t possible condition that forces an (n\,d\,\\lambda)-graph to contain a Ha
 milton cycle is not known\, where an (n\,d\,\\lambda)-graph is an n-vertex
 \, d-regular graph such that the second largest eigenvalue (in absolute va
 lue) of the adjacency matrix is bounded above by \\lambda. The smaller \\l
 ambda is\, the more control we have over the edge distribution\, and the e
 asier it becomes to embed spanning subgraphs. Alon\, Krivelevich\, and Sud
 akov asked in 2007 if the mild condition "\\lambda=o(d)" is sufficient to 
 guarantee that an (n\,d\,\\lambda)-graph contains all bounded degree spann
 ing trees. Improving significantly on previous results\, we show that the 
 condition "\\lambda<d/log^3(n)" is sufficient. Up to logarithmic factors\,
  this matches the best known condition that guarantees a Hamilton path.\n\
 n\n Contrary to other results in the area\, our proof does not rely on any
  absorption technique. Instead\, we take a new approach based on the exist
 ence of sorting networks of logarithmic depth\, as given by a celebrated c
 onstruction of Ajtai\, Komlós and Szemerédi. Using this construction\, w
 e show that the classical vertex-disjoint paths problem can be solved for 
 a set of vertices fixed in advance\, which might be of independent interes
 t.\n\n\nJoint work with Joseph Hyde\, Natasha Morrison\, and Matías Pavez
 -Signé.
LOCATION:MR12
END:VEVENT
END:VCALENDAR