کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649639 1342462 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complete rr-partite subgraphs of dense rr-graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Complete rr-partite subgraphs of dense rr-graphs
چکیده انگلیسی

Extending a classical result of Erdős, we derive the following concise statement:Let r≥3r≥3 and (lnn)−1/(r−1)≤α≤r−3(lnn)−1/(r−1)≤α≤r−3. Then every rr-uniform graph on nn vertices with at least αnr/r!αnr/r! edges contains a complete rr-partite subgraph with r−1r−1 classes of size ⌊α(lnn)1/(r−1)⌋⌊α(lnn)1/(r−1)⌋ and one class of size ⌈n1−αr−2⌉⌈n1−αr−2⌉.Our main result is a similar, but stronger statement about directed hypergraphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4326–4331
نویسندگان
,