论文标题
改进的定期分解为$ 3 $ - 均匀的超图的有限额度$ VC_2 $ -Dimension
An improved bound for regular decompositions of $3$-uniform hypergraphs of bounded $VC_2$-dimension
论文作者
论文摘要
定期分区$ \ MATHCAL {p} $，用于$ 3 $ - 均匀的超graph $ h =（v，e）$由一个分区组成$ v = v_1 \ cup \ ldots \ ldots \ cup v_t $，每个$ ij \ in {[t] \ ldots \ cup p_ {ij}^{\ ell} $，使某些quasirandomness属性保持。 $ \ Mathcal {p} $的复杂性是一对$（t，\ ell）$。在本文中，我们表明，如果$ 3 $均匀的hypergraph $ h $具有$ vc_2 $ - dimension，最多$ k $，那么有一个常规分区$ \ mathcal {p} $ for $ h $ of compladity $（t，\ ell）$，而$ \ ell $在$ \ ell $中受常规级别的多项式界定。这是由于这种规律性引理的证据所产生的巨大进步，其中$ \ ell $生成的界限是Wowzer型的。这可以看作是由于Alon-Fischer-Newman，Lovász-Szegedy和Fox-Pach-Suk而导致的图形和有限VC尺寸的图形和超图的有效规律性引理的较高的ARITH类似物。
A regular partition $\mathcal{P}$ for a $3$-uniform hypergraph $H=(V,E)$ consists of a partition $V=V_1\cup \ldots \cup V_t$ and for each $ij\in {[t]\choose 2}$, a partition $K_2[V_i,V_j]=P_{ij}^1\cup \ldots \cup P_{ij}^{\ell}$, such that certain quasirandomness properties hold. The complexity of $\mathcal{P}$ is the pair $(t,\ell)$. In this paper we show that if a $3$-uniform hypergraph $H$ has $VC_2$-dimension at most $k$, then there is a regular partition $\mathcal{P}$ for $H$ of complexity $(t,\ell)$, where $\ell$ is bounded by a polynomial in the degree of regularity. This is a vast improvement on the bound arising from the proof of this regularity lemma in general, in which the bound generated for $\ell$ is of Wowzer type. This can be seen as a higher arity analogue of the efficient regularity lemmas for graphs and hypergraphs of bounded VC-dimension due to Alon-Fischer-Newman, Lovász-Szegedy, and Fox-Pach-Suk.
