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
The Codegree Threshold for 3-Graphs with Independent Neighborhoods
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA.ORCID iD: 0000-0001-8631-4745
2015 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 29, no 3, p. 1504-1539Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
2015. Vol. 29, no 3, p. 1504-1539
Keywords [en]
codegree, Turan density, Turan function, 3-graphs
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-110602DOI: 10.1137/130926997ISI: 000362419600021Scopus ID: 2-s2.0-84943192453OAI: oai:DiVA.org:umu-110602DiVA, id: diva2:865029
Available from: 2015-10-26 Created: 2015-10-23 Last updated: 2023-03-23Bibliographically approved

Open Access in DiVA

fulltext(1137 kB)433 downloads
File information
File name FULLTEXT01.pdfFile size 1137 kBChecksum SHA-512
7e7ad37dcec4e1d7725a951aedbb347ebd2aa0f4915eb8952177d669a5915738083de07ebf3a076dcdedc8558296d3de74525ded52e93ff89a92c3f9514244a3
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
SIAM Journal on Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 434 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: 700 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