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
The Codegree Threshold for 3-Graphs with Independent Neighborhoods
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik. Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA.ORCID-id: 0000-0001-8631-4745
2015 (Engelska)Ingår i: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 29, nr 3, s. 1504-1539Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Given a family of 3-graphs F, we define its codegree threshold coex(n, F) to be the largest number d = d(n) such that there exists an n-vertex 3-graph in which every pair of vertices is contained in at least d 3-edges but which contains no member of F as a subgraph. Let F-3,F-2 be the 3-graph on {a, b, c, d, e} with 3-edges abc, abd, abe, and cde. In this paper, we give two proofs that coex(n, {F-3,F-2}) = - (1/3 + o(1))n, the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large n: coex(n, {F-3,F-2}) = [n/3] - 1 if n is congruent to 1 modulo 3, and [n/3] otherwise. In addition we determine the set of codegree-extremal configurations for all sufficiently large n.

Ort, förlag, år, upplaga, sidor
2015. Vol. 29, nr 3, s. 1504-1539
Nyckelord [en]
codegree, Turan density, Turan function, 3-graphs
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-110602DOI: 10.1137/130926997ISI: 000362419600021Scopus ID: 2-s2.0-84943192453OAI: oai:DiVA.org:umu-110602DiVA, id: diva2:865029
Tillgänglig från: 2015-10-26 Skapad: 2015-10-23 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

fulltext(1137 kB)368 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1137 kBChecksumma SHA-512
7e7ad37dcec4e1d7725a951aedbb347ebd2aa0f4915eb8952177d669a5915738083de07ebf3a076dcdedc8558296d3de74525ded52e93ff89a92c3f9514244a3
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Falgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Falgas-Ravry, Victor
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
SIAM Journal on Discrete Mathematics
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 368 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 517 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