Spanning trees in pseudorandom graphs via sorting networks

Add to your list(s) Download to your calendar using vCal

• Alp Muyesser (UCL)
• Thursday 16 November 2023, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

How pseudorandom does a graph need to be before it contains a certain spanning subgraph? This problem is not very well understood, especially in comparison to its purely random analogue. For example, the best possible condition that forces an (n,d,\lambda)-graph to contain a Hamilton 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 value) of the adjacency matrix is bounded above by \lambda. The smaller \lambda is, the more control we have over the edge distribution, and the easier it becomes to embed spanning subgraphs. Alon, Krivelevich, and Sudakov asked in 2007 if the mild condition ”\lambda=o(d)” is sufficient to guarantee that an (n,d,\lambda)-graph contains all bounded degree spanning trees. Improving significantly on previous results, we show that the condition ”\lambda 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 existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance, which might be of independent interest.

Joint work with Joseph Hyde, Natasha Morrison, and Matías Pavez-Signé.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.