论文标题
无三角超图
Triangle-free Subgraphs of Hypergraphs
论文作者
论文摘要
在本文中，我们考虑了统一超图的图形无三角形子图的良好极端问题的类似物。一个松散的三角形是由三个边缘$ e，f $和$ g $组成的超图$ t $，因此$ | e \ cap f | = | f \ cap g | = | g \ cap e | = 1 $和$ e \ cap f \ cap g = \ emptyset $。我们证明，如果$ h $是$ n $ vertex $ r $ r $均匀的超图，带有最高度$ \ triangle $，则为$ \ triangle \ rightarrow \ rightarrow \ infty $，在密度$ t $ t $ t $ t $ free $ hyhypergraph的边缘数量至少为\ [至少为\ [ \ frac {e（h）} {\ triangle^{\ frac {r-2} {r-1} + o（1）}}。我们还表明，如果$ h $是一个随机的$ n $ vertex三重系统，带有边缘概率$ p $，以至于$ pn^3 \ rightarrow \ rightarrow \ ins in h \ rightarrow \ rightarrow \ infty $，则具有很高的可能性，然后是$ n \ rightarrow \ rightarrow \ rightarrow \ rightarrow \ infty \ infty \ infty \ infty $ infty $ infty $ the of the of the of the of infty $ the Effty $ - \ min \ bigl \ {（1-o（1））p {n \ select3}，p^{\ frac {1} {3}} n^} n^{2-o（1）} \ bigr \}。 Szemerédi。
In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$. We prove that if $H$ is an $n$-vertex $r$-uniform hypergraph with maximum degree $\triangle$, then as $\triangle \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph of $H$ is at least \[ \frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.\] For $r = 3$, this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$-vertex triple system with edge-probability $p$ such that $pn^3\rightarrow\infty$ as $n\rightarrow\infty$, then with high probability as $n \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph is \[ \min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.\] We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.
