Umeå University's logo

umu.sePublications
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
The codegree threshold of K-4
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
Mathematics Institute and DIMAP, University of Warwick, Coventry, United Kingdom.
London, Citymapper, United Kingdom.
Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Czech Republic.
2023 (English)In: Journal of the London Mathematical Society, ISSN 0024-6107, E-ISSN 1469-7750, Vol. 107, no 5, p. 1660-1691Article in journal (Refereed) Published
Abstract [en]

The codegree threshold ex2 (n, F) of a 3-graph F is the minimum d = d(n) such that every 3-graph on n vertices in which every pair of vertices is contained in at least d + 1 edges contains a copy of F as a subgraph. We study ex2 (n, F) when F = K-4 , the 3-graph on 4 vertices with 3 edges. Using flag algebra techniques, we prove that if n is sufficiently large, then

ex2 (n, K-4)⩽ (n + 1)/4.

This settles in the affirmative a conjecture of Nagle [Congressus Numerantium, 1999, pp. 119-128]. In addition, we obtain a stability result: for every near-extremal configuration G, there is a quasirandom tournament T on the same vertex set such that G is o(n3)-close in the edit distance to the 3-graph C(T) whose edges are the cyclically oriented triangles from T. For infinitely many values of n, we are further able to determine ex2(n, K-4) exactly and to show that tournament-based constructions C(T) are extremal for those values of n.

Place, publisher, year, edition, pages
John Wiley & Sons, 2023. Vol. 107, no 5, p. 1660-1691
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-205362DOI: 10.1112/jlms.12722ISI: 000935215000001Scopus ID: 2-s2.0-85148342895OAI: oai:DiVA.org:umu-205362DiVA, id: diva2:1746758
Funder
EU, European Research Council, 101020255Swedish Research Council, 2016‐03488Swedish Research Council, 2021‐03687Available from: 2023-03-29 Created: 2023-03-29 Last updated: 2023-07-14Bibliographically approved

Open Access in DiVA

fulltext(784 kB)155 downloads
File information
File name FULLTEXT02.pdfFile size 784 kBChecksum SHA-512
36f6633d1477c507524e5bc9304ccd10c597ef3de591260d3593bb8c65f0a9b140bcd555e1fa7b3c97f86290275ebd8fd0c7eba10bc2e71b77a9695b9024517a
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Falgas-Ravry, Victor

Search in DiVA

By author/editor
Falgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of the London Mathematical Society
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 185 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 423 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