错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Extremal Problems on Multigraphs

  • Ran Gu,
  • Shuaichao Wang

摘要

An (nsq)-graph is an n-vertex multigraph in which every s-set of vertices spans at most q edges. Erdős initiated the study of maximum number of edges of (nsq)-graphs, and the extremal problem on multigraphs has been considered since the 1990s. The problem of determining the maximum product of the edge multiplicities in (nsq)-graphs was posed by Mubayi and Terry in 2019. Recently, Day, Falgas-Ravry and Treglown settled a conjecture of Mubayi and Terry on the case \((s,q)=(4, 6a + 3)\) ( s , q ) = ( 4 , 6 a + 3 ) of the problem (for \(a \ge 2\) a 2 ), and they gave a general lower bound construction for the extremal problem for many pairs (sq), which they conjectured is asymptotically best possible. Their conjecture was confirmed exactly or asymptotically for some specific cases. In this paper, we consider the case that \((s,q)=(5,\left( {\begin{array}{c}5\\ 2\end{array}}\right) a+4)\) ( s , q ) = ( 5 , 5 2 a + 4 ) and \(d=2\) d = 2 of their conjecture, partially solve an open problem raised by Day, Falgas-Ravry and Treglown. We also show that the conjecture fails for \(n=6\) n = 6 , which indicates for the case that \((s,q)=(5,\left( {\begin{array}{c}5\\ 2\end{array}}\right) a+4)\) ( s , q ) = ( 5 , 5 2 a + 4 ) and \(d=2\) d = 2 , n needs to be sufficiently large for the conjecture to hold.