Small cores in 3-uniform hypergraphs

详细信息    查看全文

• 作者：David Solymosi^a ; ^{solymosi@cs.toronto.edu} ; Jozsef Solymosi^b ; ^{solymosi@math.ubc.ca}
• 关键词：Cores in hypergraphs ; Brown&ndash ; Erdős&ndash ; Só ; s conjecture ; Hypergraph regularity
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：897-910
• 全文大小：671 K
• 卷排序：122

文摘

The main result of this paper is that for any c>0c>0 and for large enough n   if the number of edges in a 3-uniform hypergraph is at least cn2cn2 then there is a core (subgraph with minimum degree at least 2) on at most 15 vertices. We conjecture that our result is not sharp and 15 can be replaced by 9. Such an improvement seems to be out of reach, since it would imply the following case of a long-standing conjecture by Brown, Erdős, and Sós; if there is no set of 9 vertices that span at least 6 edges of a 3-uniform hypergraph then it is sparse.