DAVENPORT-SCHINZEL THEORY OF MATRICES

被引：80

作者：

FUREDI, Z

HAJNAL, P

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[2] MIT,DEPT MATH,CAMBRIDGE,MA 02139

来源：

DISCRETE MATHEMATICS | 1992年 / 103卷 / 03期

基金：

美国国家科学基金会; 匈牙利科学研究基金会;

关键词：

D O I：

10.1016/0012-365X(92)90316-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let C be a configuration of 1's. We define f (n; C) to be the maximal number of 1's in a 0-1 matrix of size n X n not having C as a subconfiguration. We consider the problem of determining the order of f (n; C) for several forbidden C's. Among other results we prove that f (n; (1 1 1 1)) = THETA(alpha(n)n), where alpha(n) is the inverse of the Ackermann function.

引用

页码：233 / 251

页数：19

共 19 条

[1] The Hilbert construction of real numbers [J].

Ackermann, W .

MATHEMATISCHE ANNALEN, 1928, 99 :118-133

[2]

ADAMEC R, FORBIDDEN WORDS

[3]

AGARWAL P, SHARP UPPER LOWER BO

[4]

BIENSTOCK D, IN PRESS SIAM J DISC

[5]

Bollobas B., 1978, LONDON MATH SOC MONO

[6] ON GRAPHS THAT DO NOT CONTAIN A THOMSEN GRAPH [J].

BROWN, WG .

CANADIAN MATHEMATICAL BULLETIN, 1966, 9 (03) :281-&

[7]

DAVENPORT H, 1971, ACTA ARITH, V17, P363

[8] ON THE STRUCTURE OF LINEAR GRAPHS [J].

ERDOS, P ;

STONE, AH .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091

[9]

Erdos P., 1966, STUDIA SCI MATH HUNG, V1, P215

[10]

Erdos P., 1966, STUDIA SCI MATH HUNG, V1, P51

← 1 2 →