Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• 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.
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
##### Keyword [en]
codegree, Turan density, Turan function, 3-graphs
Mathematics
##### Identifiers
ISI: 000362419600021OAI: oai:DiVA.org:umu-110602DiVA, id: diva2:865029
Available from: 2015-10-26 Created: 2015-10-23 Last updated: 2018-06-07Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 1137 kBChecksum SHA-512
Type fulltextMimetype application/pdf

#### 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

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: 87 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• 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
v. 2.33.0
|