![]() |
![]() |
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 listsMetallurgy & Materials – Tech Entrepreneurship Seminar Series Applied Mathematics Seminar Series Centre for Systems Biology Coffee MorningsOther talksPerfect matchings in random sparsifications of Dirac hypergraphs Ultrafast, all-optical, and highly efficient imaging of molecular chirality Quantum simulations using ultra cold ytterbium Geometry of alternating projections in metric spaces with bounded curvature Modelling uncertainty in image analysis. Sensing and metrology activities at NPL, India |