Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Extremal problems for multigraphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
University of Birmingham, Birmingham, United Kingdom.
2022 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 154, p. 1-48Article in journal (Refereed) Published
Abstract [en]

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 (2019) [13] 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≥2); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for ‘sparse’ multigraphs (i.e. when q≤2(s2)). Finally we introduce some tools that are likely to be useful for attacking the problem in general.

Place, publisher, year, edition, pages
Academia Press, 2022. Vol. 154, p. 1-48
Keywords [en]
Multigraphs, Transcendental numbers, Turán-type problems
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-190943DOI: 10.1016/j.jctb.2021.12.003ISI: 000751659000001Scopus ID: 2-s2.0-85121584522OAI: oai:DiVA.org:umu-190943DiVA, id: diva2:1624884
Funder
Swedish Research Council, 2016-03488Available from: 2022-01-05 Created: 2022-01-05 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopusFree full text in ArXiv

Authority records

Day, A. NicholasFalgas-Ravry, Victor

Search in DiVA

By author/editor
Day, A. NicholasFalgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of combinatorial theory. Series B (Print)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 493 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf