Triple systems not containing a fano configuration

被引：57

作者：

Füredi, Z

Simonovits, M

机构：

[1] Hungarian Acad Sci, Renyi Inst Math, H-1364 Budapest, Hungary

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

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2005年 / 14卷 / 04期

关键词：

D O I：

10.1017/S0963548305006784

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A Fano configuration is the hypergraph of 7 vertices and 7 triplets defined by the points and lines of the finite projective plane of order 2. Proving a conjecture of T Sos, the largest triple system on n vertices containing no Fano configuration is determined (for n > n(1)). It is 2-chromatic with ((3) (n)) - ((3) ([n/2])) - (([n/2)(3)]) triples. This is one of the very few nontrivial exact results for hypergraph extremal problems.

引用

页码：467 / 484

页数：18

共 19 条

[1]

Andrasfai B., 1974, Discrete Mathematics, V8, P205, DOI 10.1016/0012-365X(74)90133-2

[2]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[3]

Bondy JA, 1997, J GRAPH THEOR, V25, P267, DOI 10.1002/(SICI)1097-0118(199708)25:4<267::AID-JGT4>3.0.CO

[4]

2-I