On 0-1 matrices and small excluded submatrices. (English) Zbl 1070.05019
Summary: We say that a 0-1 matrix \(A\) avoids another 0-1 matrix (pattern) \(P\) if no matrix \(P^{\prime}\) obtained from \(P\) by increasing some of the entries is a submatrix of \(A\). Following the lead of [D. Bienstock and E. Györi, SIAM J. Discrete Math. 4, 17–27 (1991; Zbl 0752.05012); Z. Füredi, J. Comb. Theory, Ser. A 55, 316–320 (1990; Zbl 0742.52010); and Z. Füredi and P. Hajnal, Discrete Math. 103, 233–251 (1992; Zbl 0776.05024)] and other papers we investigate \(n\) by \(n\) 0-1 matrices avoiding a pattern \(P\) and the maximal number ex\((n,P)\) of 1 entries they can have. Finishing the work of Füredi and Hajnal [loc. cit.] we find the order of magnitude of ex\((n,P)\) for all patterns \(P\) with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered.
MSC:
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15B36 | Matrices of integers |
Keywords:
patternsReferences:
| [1] | Baker, R.; Harman, G.; Pintz, J., The difference between consecutive primes II, Proc. London Math. Soc., 83, 3, 532-562 (2001) · Zbl 1016.11037 |
| [2] | Bienstock, D.; Győri, E., An extremal problem on sparse 0-1 matrices, SIAM J. Discrete Math., 4, 17-27 (1991) · Zbl 0752.05012 |
| [3] | Brass, P.; Károlyi, Gy.; Valtr, P., A Turán-type extremal theory of convex geometric graphs, (Aronov, B.; etal., Discrete and Computational Geometry—The Goodman-Pollack Festscrift (2003), Springer: Springer Berlin), 277-302 |
| [4] | Czipszer, J.; Erdős, P.; Hajnal, A., Some extremal problems on infinite graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 7, 441-457 (1962) · Zbl 0114.01301 |
| [5] | Efrat, A.; Sharir, M., A near-linear algorithm for the planar segment center problem, Discrete Comput. Geom., 16, 239-257 (1996) · Zbl 0868.68112 |
| [6] | R. Faudree, M. Simonovits, On a class of degenerate extremal graph problems II, in preparation.; R. Faudree, M. Simonovits, On a class of degenerate extremal graph problems II, in preparation. · Zbl 0521.05037 |
| [7] | Füredi, Z., The maximum number of unit distances in a convex \(n\)-gon, J. Combin. Theory Ser. A, 55, 316-320 (1990) · Zbl 0742.52010 |
| [8] | Füredi, Z.; Hajnal, P., Davenport-Schinzel theory of matrices, Discrete Math., 103, 233-251 (1992) · Zbl 0776.05024 |
| [9] | Klazar, M., The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, (Krob, D.; Mikhalev, A. A.; Mikhalev, A. V., Formal Power Series and Algebraic Combinatorics (2000), Springer: Springer Berlin), 250-255 · Zbl 0954.05048 |
| [10] | Klazar, M., A general upper bound in extremal theory of sequences, Comment. Math. Univ. Carolinae, 33, 737-747 (1992) · Zbl 0781.05049 |
| [11] | Klazar, M., Generalized Davenport-Schinzel sequencesresults, problems, and applications, Integers, 2, A11, 39 (2002) · Zbl 1004.05004 |
| [12] | Klazar, M., Extremal problems for ordered (hyper)graphsapplications of Davenport-Schinzel sequences, European J. Combin., 25, 125-140 (2004) · Zbl 1031.05071 |
| [13] | Klazar, M.; Valtr, P., Generalized Davenport-Schinzel sequences, Combinatorica, 14, 463-476 (1994) · Zbl 0812.05067 |
| [14] | Marcus, A.; Tardos, G., Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A, 107, 153-160 (2004) · Zbl 1051.05004 |
| [15] | J. Pach, G. Tardos, Forbidden patterns and unit distances, SoCG 2005, submitted, available from; J. Pach, G. Tardos, Forbidden patterns and unit distances, SoCG 2005, submitted, available from · Zbl 1387.05124 |
| [16] | I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proceedings of the Fifth Hungarian Colloquium Keszthely, 1976), vol. II, Colloquium Mathemtical Society, János Bolyai, vol. 18, North-Holland, Amsterdam, New York, 1978, pp. 939-945.; I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proceedings of the Fifth Hungarian Colloquium Keszthely, 1976), vol. II, Colloquium Mathemtical Society, János Bolyai, vol. 18, North-Holland, Amsterdam, New York, 1978, pp. 939-945. · Zbl 0393.05031 |
| [17] | G. Tardos, Construction of locally plane graphs, SIAM J. Discrete Math., 2004, submitted available from; G. Tardos, Construction of locally plane graphs, SIAM J. Discrete Math., 2004, submitted available from |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
