Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Extremal problems for multigraphs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
University of Birmingham, Birmingham, United Kingdom.
2022 (Engelska)Ingår i: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 154, s. 1-48Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Academia Press, 2022. Vol. 154, s. 1-48
Nyckelord [en]
Multigraphs, Transcendental numbers, Turán-type problems
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
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
Forskningsfinansiär
Vetenskapsrådet, 2016-03488Tillgänglig från: 2022-01-05 Skapad: 2022-01-05 Senast uppdaterad: 2023-09-05Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopusFree full text in ArXiv

Person

Day, A. NicholasFalgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Day, A. NicholasFalgas-Ravry, Victor
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Journal of combinatorial theory. Series B (Print)
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 318 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf