On an extremal problem for locally sparse multigraphs

DOI10.1016/J.EJC.2023.103887MaRDI QIDQ6201879zbMATH OpenOpenAlexFDO

Authors Victor Falgas-Ravry

Publication date 26 March 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph isomorphismsasymptotic extremal combinatoricsdensities of substructuresformal algebras

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: A multigraph $G$ is an $(s,q)$-graph if every $s$-set of vertices in $G$ supports at most $q$ edges of $G$, counting multiplicities. Mubayi and Terry posed the problem of determining the maximum of the product of the edge-multiplicities in an $(s,q)$-graph on $n$ vertices. We give an asymptotic solution to this problem for the family $$ with $r,ainmathbb{Z}_{geq2}$. This greatly generalises previous results on the problem due to Mubayi and Terry and to Day, Treglown and the author, who between them had resolved the special case $r=2$. Our result asymptotically confirms an infinite family of cases in (and overcomes a major obstacle to a resolution of) a conjecture of Day, Treglown and the author.

Recommendations

• Extremal problems for multigraphs
• Extremal theory of locally sparse multigraphs
• On extremal problems on multigraphs
• scientific article; zbMATH DE number 3641461
• Boundedness of optimal matrices in extremal multigraph and digraph problems

Cites work

• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• A weighted generalization of Tur�n's theorem
• An Extremal Graph Problem with a Transcendental Solution
• Extremal problems for multigraphs
• Extremal theory of locally sparse multigraphs
• Hypergraph containers
• Independent sets in hypergraphs
• Multicolor containers, extremal entropy, and counting
• Structure and enumeration theorems for hereditary properties in finite relational languages
• The method of hypergraph containers
• Turán problems for integer-weighted graphs

Cited in

(3)

• Extremal graph theoretic questions for q-ary vectors
• On extremal problems on multigraphs
• Results on extremal graph theoretic questions for q-ary vectors

This page was built for publication: On an extremal problem for locally sparse multigraphs

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