9086

8431

كارشناسي ارشد

رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1392

هفت،55ص.:نمودار

ص.ع.به فارسي و انگليسي

رياضي

ID8431

Erdos Conjecture on Matchings in Hypergraphs Ali Nasresfahani a nasresfahani@math iut ac ir 2014 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Gholam Reza Omidi romidi@cc iut ac ir Advisor Dr Reza Rezaeian 2010 MSC 05C35 05C65 Keywords Hypergraphs Matching Erd s AbstractA k uniform hypergraph G V E is a set of vertices V N together with a family E of k elementsubsets of V which are called edges In this note by G V and e G E we denote the numberof vertices and edges of G V E respectively By a matching we mean any family of disjoint edgesof G and we denote by G the size of the largest matching contained in E Moreover by k n s wemean the largest possible number of edges in a k uniform hypergraph G with G n and G s and by Mk n s we denote the family of the extremal hypergraphs for this problem i e H Mk n s if H n H s and e H k n s In 1965 Erd s conjectured that unless n 2k and s 1 all graphs from Mk n s are eithercliques or belong to the family Covk n s of hypergraphs on n vertices in which the set of edgesconsists of all k subsets which intersect a given subset S V with S s This conjecture which is anatural generalization of Erd s Gallai result for graphs has been veri ed only for k 3 For generalk there have been series of results which state that Mk n s Covk n s f or n g k s where g k is some function of k The existence of such g k was shown by Erd s then Bollobas Daykin and Erd s proved that this equation holds whenever g k 2k 3 Frankl and F redi showedthat the equation is true for g k 100k 2 and recently Huang Loh and Sudakov veri ed its truness

غلامرضا اميدي

رضا رضاييان

بهناز عمومي، محمدرضا عبودي