The number of the maximal triangle-free graphs

被引：11

作者：

Balogh, Jozsef ^{[1
,2
]}

Petrickova, Sarka ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Univ Szeged, Bolyai Inst, H-6720 Szeged, Hungary

来源：

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY | 2014年 / 46卷

基金：

美国国家科学基金会;

关键词：

D O I：

10.1112/blms/bdu059

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Paul Erdos suggested the following problem: Determine or estimate the number of maximal triangle-free graphs on n vertices. Here we show that the number of maximal triangle-free graphs is at most 2(n2)/(8+o(n2)), which matches the previously known lower bound. Our proof uses among others the Ruzsa-Szemeredi triangle-removal lemma, and recent results on characterizing of the structure of independent sets in hypergraphs.

引用

页码：1003 / 1006

页数：4