<p>For every positive integer t we construct a finite family of triple systems <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({\cal M}_{t}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mi mathvariant="script">M</mi> </mrow> <mrow> <mi>t</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, determine its Turán number, and show that there are <i>t</i> extremal <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\cal M}_{t}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mi mathvariant="script">M</mi> </mrow> <mrow> <mi>t</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({\cal M}_{t}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mi mathvariant="script">M</mi> </mrow> <mrow> <mi>t</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-free triple system whose size is close to the maximum size is a subgraph of one of these <i>t</i> extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turán tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({\cal M}_{t}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mrow> <mi mathvariant="script">M</mi> </mrow> <mrow> <mi>t</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> has exactly <i>t</i> global maxima.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hypergraphs with many extremal configurations

  • Xizhi Liu,
  • Dhruv Mubayi,
  • Christian Reiher

摘要

For every positive integer t we construct a finite family of triple systems \({\cal M}_{t}\) M t , determine its Turán number, and show that there are t extremal \({\cal M}_{t}\) M t -free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every \({\cal M}_{t}\) M t -free triple system whose size is close to the maximum size is a subgraph of one of these t extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turán tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of \({\cal M}_{t}\) M t has exactly t global maxima.