On an extremal problem for locally sparse multigraphs

DOI10.1016/J.EJC.2023.103887arXiv2101.03056OpenAlexW3119886057MaRDI QIDQ6201879FDOQ6201879

Authors: Victor Falgas-Ravry 

Publication date: 26 March 2024

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

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.

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

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

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)

Cites Work

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

Cited In (1)

• On extremal problems on multigraphs

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)