![]() |
![]() |
University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Antidirected subgraphs of oriented graphs
Antidirected subgraphs of oriented graphsAdd 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. This talk is included in these lists:Note that ex-directory lists are not shown. |
Other listsSchool of Mathematics events Type the title of a new list here Condensed Matter Physics SeminarsOther talksSylow branching coefficients for symmetric groups Quantifying the economic and environmental effects of the RCEP TBA Time crystals, time quasicrystals, and time crystal dynamics Title tbc TBA |