University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Antidirected subgraphs of oriented graphs

Antidirected subgraphs of oriented graphs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.