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

Research output not available from this repository, contact author.

Request Changes to record.

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 > Mathematics
Journal or Publication Title:	Discrete Mathematics
Publisher:	Elsevier BV
ISSN:	0012-365X
Official Date:	6 November 2010
Dates:	Date Event 6 November 2010 Published
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