论文标题
反向图恩数
Inverse Turán numbers
论文作者
论文摘要
对于给定的图形$ g $和$ f $，Turán数字$ ex（g，f）$被定义为$ f $ f $ f $ f $ g $的最大边数。 Foucaud，Krivelevich和Perarnau以及后来独立的Briggs和Cox引入了此问题的双重版本，其中，对于给定的数字$ K $，一个人最大化了主机图$ G $中的边缘数量，$ g $ ex（g，h）<k $。 在解决Briggs和Cox的问题时，我们确定了长度为$ 4 $和5美元的逆图路的渐近值，并为所有长度的所有路径提供了改进的下限。此外，在$ C_4 $的情况下，我们获得了Turán数量偶数偶数偶数偶数的界限。最后，我们给出了有关$ c_4 $和$ p _ {\ ell} $的渐近值的多个猜想，这表明在后一种问题中，渐近行为在很大程度上取决于$ \ ell $的奇偶校验。
For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turán number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turán number of $C_4$ and $P_{\ell}$, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $\ell$.
