The Library
The codegree threshold for 3-graphs with independent neighborhoods
Tools
Falgas-Ravry, Victor, Marchant, Edward, Pikhurko, Oleg and Vaughan, Emil R. (2015) The codegree threshold for 3-graphs with independent neighborhoods. SIAM Journal on Discrete Mathematics, 29 (3). pp. 1504-1539. doi:10.1137/130926997 ISSN 0895-4801.
|
PDF
WRAP_130926997.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (579Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/130926997
Abstract
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 F3,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, {F3,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, {F3,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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||
ISSN: | 0895-4801 | ||||||||
Official Date: | 18 August 2015 | ||||||||
Dates: |
|
||||||||
Volume: | 29 | ||||||||
Number: | 3 | ||||||||
Number of Pages: | 36 | ||||||||
Page Range: | pp. 1504-1539 | ||||||||
DOI: | 10.1137/130926997 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 31 December 2015 | ||||||||
Date of first compliant Open Access: | 31 December 2015 | ||||||||
Funder: | Trinity College (University of Cambridge), European Research Council (ERC), Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | 306493 (ERC), EP/K012045/1 (EPSRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year