Change search
ReferencesLink to record
Permanent link

Direct link
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, 1504-1539 p.Article 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, 1504-1539 p.
Keyword [en]
codegree, Turan density, Turan function, 3-graphs
National Category
URN: urn:nbn:se:umu:diva-110602DOI: 10.1137/130926997ISI: 000362419600021OAI: diva2:865029
Available from: 2015-10-26 Created: 2015-10-23 Last updated: 2015-10-26Bibliographically approved

Open Access in DiVA

fulltext(1137 kB)52 downloads
File information
File name FULLTEXT01.pdfFile size 1137 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

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

Search outside of DiVA

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

Altmetric score

Total: 27 hits
ReferencesLink to record
Permanent link

Direct link