Extremal theory of locally sparse multigraphs

DOI10.1137/19M1237612MaRDI QIDQ5128516zbMATH OpenFDO

Authors Dhruv Mubayi, Caroline A. Terry

Publication date 27 October 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08948

zbMATH Keywords

enumerationextremalmultigraph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: An $(n,s,q)$-graph is an $n$-vertex multigraph where every set of $s$ vertices spans at most $q$ edges. In this paper, we determine the maximum product of the edge multiplicities in $(n,s,q)$-graphs if the congruence class of $q$ modulo $schoose2$ is in a certain interval of length about $3s/2$. The smallest case that falls outside this range is $(s,q)=(4,15)$, and here the answer is $a^{n^2+o(n^2)}$ where $a$ is transcendental assuming Schanuel's conjecture. This could indicate the difficulty of solving the problem in full generality. Many of our results can be seen as extending work by Bondy-Tuza and F"uredi-K"undgen about sums of edge multiplicities to the product setting. We also prove a variety of other extremal results for $(n,s,q)$-graphs, including product-stability theorems. These results are of additional interest because they can be used to enumerate and to prove logical 0-1 laws for $(n,s,q)$-graphs. Our work therefore extends many classical enumerative results in extremal graph theory beginning with the ErdH{o}s-Kleitman-Rothschild theorem to multigraphs.

Recommendations

• Extremal problems for multigraphs
• scientific article; zbMATH DE number 3641461
• An Extremal Graph Problem with a Transcendental Solution
• Boundedness of optimal matrices in extremal multigraph and digraph problems
• Jumps and nonjumps in multigraphs

Cites work

• A weighted generalization of Tur�n's theorem
• An Extremal Graph Problem with a Transcendental Solution
• Extensions of Turán's theorem on graphs
• Extremal graphs without three‐cycles or four‐cycles
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3298603 (Why is no real title available?)
• Multicolor containers, extremal entropy, and counting
• On the number of graphs without 4-cycles
• Turán problems for integer-weighted graphs

Cited in

(7)

• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Extremal problems for multigraphs
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• On an extremal problem for locally sparse multigraphs
• Extremal graph theoretic questions for q-ary vectors
• Results on extremal graph theoretic questions for q-ary vectors
• On extremal problems on multigraphs

This page was built for publication: Extremal theory of locally sparse multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128516)