论文标题
多编码的极端问题
Extremal problems for multigraphs
论文作者
论文摘要
a $（n，s，q）$ - 图是$ n $ vertex多编码，其中每个$ s $ set的顶点跨度最多$ q $ edges。自1990年代以来，已经研究了有关此类多编码中边缘多重性总和的最大值的Turán型问题。最近，Mubayi和Terry [具有先验解决方案，组合概率和计算2019的一个极端问题]提出了确定$（n，s，q）$图中边缘多重性产物的最大产品的问题。对于许多对$（S，Q）$，我们为此问题提供了一般的下限结构，我们认为这是渐进的。我们证明了我们的猜想的各种一般案例，尤其是我们在$（s，q）=（4,6a+3）$案例上解决了穆巴伊和特里的猜想（对于$ a \ geq2 $）；反过来，这回答了阿隆的问题。我们还确定了“稀疏”多编码的问题的渐近行为（即$ q \ leq 2 \ binom {s} {2} $）。最后，我们介绍了一些工具，这些工具可能对攻击问题很有用。
An $(n,s,q)$-graph is an $n$-vertex multigraph in which every $s$-set of vertices spans at most $q$ edges. Turán-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry [An extremal problem with a transcendental solution, Combinatorics Probability and Computing 2019] posed the problem of determining the maximum of the product of the edge multiplicities in $(n,s,q)$-graphs. We give a general lower bound construction for this problem for many pairs $(s,q)$, which we conjecture is asymptotically best possible. We prove various general cases of our conjecture, and in particular we settle a conjecture of Mubayi and Terry on the $(s,q)=(4,6a+3)$ case of the problem (for $a\geq2$); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for `sparse' multigraphs (i.e. when $q\leq 2\binom{s}{2}$). Finally we introduce some tools that are likely to be useful for attacking the problem in general.
