کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777623 1632969 2017 40 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
ترجمه فارسی عنوان
در ساختار نمودار گرا و هماهنگ با مسابقات ممنوعه یا چرخه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Motivated by his work on the classification of countable homogeneous oriented graphs, Cherlin asked about the typical structure of oriented graphs (i) without a transitive triangle, or (ii) without an oriented triangle. We give an answer to these questions (which is not quite the predicted one). Our approach is based on the recent 'hypergraph containers' method, developed independently by Saxton and Thomason as well as by Balogh, Morris and Samotij. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply to digraphs. Along the way we prove several stability results for extremal digraph problems, which we believe are of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 124, May 2017, Pages 88-127
نویسندگان
, , , ,