The Library
Strong forms of stability from flag algebra calculations
Tools
Tools
Tools
Pikhurko, Oleg, Sliačan, Jakub and Tyros, Konstantinos (2019) Strong forms of stability from flag algebra calculations. Journal of Combinatorial Theory Series B, 135 . pp. 129-178. doi:10.1016/j.jctb.2018.08.001
|
PDF
WRAP-strong-forms-stability-flag-algebra-Pikhurko-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (929Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2018.08.001
Abstract
Given a hereditary family G of admissible graphs and a function λ ( G ) that linearly depends on the statistics of order- κ subgraphs in a graph G , we consider the extremal problem of determining λ ( n, G ), the maximum of λ ( G ) over all admissible graphs G of order n . We call the problem perfectly B -stable for a graph B if there is a constant C such that every admissible graph G of order n ≥ C can be made into a blow-up of B by changing at most C ( λ ( n, G ) − λ ( G )) ( n 2 ) adjacencies. As special cases, this property describes all almost extremal graphs of order n within o ( n 2 ) edges and shows that every extremal graph of order n ≥ n 0 is a blow-up of B . We develop general methods for establishing stability-type results from flag algebra computations and apply them to concrete examples. In fact, one of our sufficient conditions for perfect stability is stated in a way that allows automatic verification by a computer. This gives a unifying way to obtain computer-assisted proofs of many new results.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial number theory, Algebra | |||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory Series B | |||||||||
| Publisher: | Elsevier | |||||||||
| ISSN: | 0095-8956 | |||||||||
| Official Date: | March 2019 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 135 | |||||||||
| Page Range: | pp. 129-178 | |||||||||
| DOI: | 10.1016/j.jctb.2018.08.001 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
