The Library
An analytic approach to stability
Tools
Pikhurko, Oleg (2010) An analytic approach to stability. Discrete Mathematics, Vol.310 (No.21). pp. 2951-2964. doi:10.1016/j.disc.2010.07.002 ISSN 0012-365X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.disc.2010.07.002
Abstract
The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order n can be made isomorphic by changing o(n2) edges.
Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erdős–Simonovits stability theorem.
Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fractional versions are within a constant factor from each other, thus answering a question of Goldreich, Krivelevich, Newman, and Rozenberg.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Mathematics | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 0012-365X | ||||
Official Date: | 6 November 2010 | ||||
Dates: |
|
||||
Volume: | Vol.310 | ||||
Number: | No.21 | ||||
Page Range: | pp. 2951-2964 | ||||
DOI: | 10.1016/j.disc.2010.07.002 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |