Antidirected subgraphs of oriented graphs

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

• Camila Zarate Gueren, Birmingham
• Thursday 02 February 2023, 15:00-16:00
• LRC.

If you have a question about this talk, please contact Dr Richard Mycroft.

For simple connected graphs, minimum degree at least k/2 guarantees having the k-path as a subgraph, if the graph has at least k+1 vertices. For oriented graphs, Stein conjectured that minimum semidegree greater than k/2 should be enough to have every oriented path of length k. We prove that this is asymptotically true for large antidirected paths in large graphs. Even more, the result is true for large antidirected trees that are balanced and of bounded maximum degree under the same condition on the minimum semidegree. We also prove a similar result for antisubdivisions of a sufficiently small complete graph, which implies having the k-edge antidirected cycle.

Lastly, we address a conjecture by Addario-Berry, Havet, Linhares Sales, Reed and Thomassé about edge density on digraphs and antidirected trees. We show that this conjecture is asymptotically true for oriented graphs with n vertices and all balanced antidirected trees of bounded maximum degree and of size linear in n.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• LRC
• School of Mathematics events

Note that ex-directory lists are not shown.