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

共 13 条

[1] Balogh J., J AM MATH S IN PRESS
[2] Balogh J., 2012, J AM MATH SOC
[3] Notes on sum-free and related sets
Cameron, PJ
Erdos, P
[J]. COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (1-2) : 95 - 107
[4] SUPERSATURATED GRAPHS AND HYPERGRAPHS
ERDOS, P
SIMONOVITS, M
[J]. COMBINATORICA, 1983, 3 (02) : 181 - 192
[5] Erds P., 1976, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, P19
[6] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN TRIANGLE-FREE GRAPHS
HUJTER, M
TUZA, Z
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) : 284 - 288
[7] Mantel W., 1907, WISKUNDIGE OPGAVEN, V10, P60
[8] McKay B., OPEN PROBLE IN PRESS
[9] For which densities are random triangle-free graphs almost surely bipartite?
Osthus, D
Prömel, HJ
Taraz, A
[J]. COMBINATORICA, 2003, 23 (01) : 105 - 150
[10] Ruzsa Imre Z, 1978, C MATH SOC J BOLYAI, V18, P939

← 1 2 →