کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651882 1632582 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the random greedy F-free hypergraph process
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the random greedy F-free hypergraph process
چکیده انگلیسی

Let F be a strictly k-balanced k-uniform hypergraph with e(F)≥|F|−k+1 and maximum co-degree at least two. The random greedy F-free process constructs a maximal F-free hypergraph as follows. Consider a random ordering of the hyper-edges of the complete k-uniform hypergraph on n vertices. Start with the empty hypergraph on n vertices. Successively consider the hyperedges e of in the given ordering and add e to the existing hypergraph provided that e does not create a copy of F. We show that asymptotically almost surely this process terminates at a hypergraph with hyperedges. This is best possible up to logarithmic factors.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 73-77