ディラックの定理と線形ハイパーグラフ

ディラックの定理は、偶数整数 n を満たす任意の n 頂点グラフ G が (G) n/2 を満たす場合、完全マッチングを含むことを述べています。これを k-一様線形ハイパーグラフに一般化し、以下を証明します。最小次数が少なくとも nk + (1) である任意の n 頂点 k-一様線形ハイパーグラフ H には、少なくとも (1-o (1)) n 頂点をカバーするマッチングが含まれます。この最小次数条件は漸近的に厳密であり、任意の次数条件で完全マッチングを得ることは不可能です。さらに、もし (H) (1k+o (1)) n ならば、H にはほぼスパンの線形サイクル、o (n) 葉を持つほぼスパンのハイパーツリー、および任意の o (n) 頂点グラフの「長い細分」が含まれることを示します。