×

Saturation problems about forbidden 0-1 submatrices. (English) Zbl 1473.05143

Summary: A 0-1 matrix \(M\) is saturating for a 0-1 matrix \(P\) if \(M\) does not contain a submatrix that can be turned into \(P\) by changing some 1 entries to 0 entries, and changing an arbitrary 0 to 1 in \(M\) introduces such a submatrix in \(M\). In saturation problems for 0-1 matrices we are interested in estimating the minimum number of 1 entries in an \(m \times n\) matrix that is saturating for \(P\), in terms of \(m\) and \(n\). In other words, we wish to give good estimates for the saturation function of \(P\). Recently, R. A. Brualdi and L. Cao [“Pattern-avoiding (0,1)-matrices”, Preprint, arXiv:2005.00379] initiated the study of saturation problems in the context of 0-1 matrices. We extend their work in several directions. We prove that every 0-1 forbidden matrix has its saturation function either in \(\Theta(1)\) or \(\Theta(n)\) in the case when we restrict ourselves to square saturating matrices. Then we give a partial answer to a question posed by Brualdi and Cao [loc. cit.] about the saturation function of \(J_k\), which is obtained from the identity matrix \(I_k\) by putting the first row after the last row. Furthermore, we exhibit a \(5\times 5\) permutation matrix with the saturation function bounded from the above by a fixed constant. We complement this result by identifying large classes of 0-1 matrices with linear saturation function. Finally, we completely resolve the related semisaturation problem as far as the constant versus linear dichotomy is concerned.

MSC:

05C35 Extremal problems in graph theory
05D10 Ramsey theory
06A07 Combinatorics of partially ordered sets
15B34 Boolean and Hadamard matrices
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)

References:

[1] R. A. Brualdi and L. Cao, Pattern-avoiding (0, 1)-matrices, preprint, arXiv:2005.00379, 2020, http://arxiv.org/abs/2005.00379.
[2] G. Damásdi, B. Keszegh, D. Malec, C. Tompkins, Z. Wang, and O. Zamora, Saturation problems in the Ramsey theory of graphs, posets and point sets, European J. Combin., 95 (2021), 103321. · Zbl 1466.05210
[3] A. Dudek, O. Pikhurko, and A. Thomason, On minimum saturated matrices, Graphs Combin., 29 (2013), pp. 1269-1286. · Zbl 1272.05016
[4] P. Erdös, A. Hajnal, and J. W. Moon, A problem in graph theory, Am. Math. Mon., 71 (1964), pp. 1107-1110. · Zbl 0126.39401
[5] M. Ferrara, B. Kay, L. Kramer, R. R. Martin, B. Reiniger, H. C. Smith, and E. Sullivan, The saturation number of induced subposets of the Boolean lattice, Discrete Math., 340 (2017), pp. 2479-2487. · Zbl 1423.06006
[6] N. Frankl, S. Kiselev, A. Kupavskii, and B. Patkós, VC-saturated set systems, preprint, arXiv:2005.12545, 2020, http://arxiv.org/abs/2005.12545.
[7] Z. Füredi and Y. Kim, Cycle-saturated graphs with minimum number of edges, J. Graph Theory, 73 (2013), pp. 203-215. · Zbl 1262.05084
[8] R. Fulek, Linear bound on extremal functions of some forbidden patterns in 0-1 matrices, Discrete Math., 309 (2009), pp. 1736-1739. · Zbl 1193.05043
[9] Z. Füredi, The maximum number of unit distances in a convex n-gon, J. Combin. Theory Ser. A, 55 (1990), pp. 316-320. · Zbl 0742.52010
[10] Z. Füredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Math., 103 (1992), pp. 233-251. · Zbl 0776.05024
[11] J. T. Geneson, Extremal functions of forbidden double permutation matrices, J. Combin. Theory Ser. A, 116 (2009), pp. 1235-1244. · Zbl 1228.05094
[12] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. Pálvölgyi, and B. Patkós, Saturating sperner families, Graphs Combin., 29 (2013), pp. 1355-1364. · Zbl 1272.05212
[13] B. Keszegh, On linear forbidden submatrices, J. Combin. Theory Ser. A, 116 (2009), pp. 232-241. · Zbl 1189.05036
[14] B. Keszegh, N. Lemons, R. R. Martin, D. Pálvölgyi, and B. Patkós, Induced and non-induced poset saturation problems, J. Combin. Theory Ser. A, 187 (2021), 105497. · Zbl 1471.05106
[15] M. Klazar, The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, in Formal Power Series and Algebraic Combinatorics, D. Krob, A. A. Mikhalev, and A. V. Mikhalev, eds., Springer, Berlin, Heidelberg, 2000, pp. 250-255. · Zbl 0954.05048
[16] D. Korándi, G. Tardos, I. Tomon, and C. Weidert, On the Turán number of ordered forests, J. Combin. Theory Ser. A, 165 (2019), pp. 32-43. · Zbl 1414.05165
[17] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory, 10 (1986), pp. 203-210. · Zbl 0593.05041
[18] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A, 107 (2004), pp. 153-160. · Zbl 1051.05004
[19] J. S. B. Mitchell, L1 shortest paths among polygonal obstacles in the plane, Algorithmica, 8 (1992), pp. 55-88. · Zbl 0753.68093
[20] J. Pach and G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel J. Math., 155 (2006), pp. 359-380. · Zbl 1132.05035
[21] S. Pettie, Degrees of nonlinearity in forbidden 0-1 matrix problems, Discrete Math., 311 (2011), pp. 2396-2410. · Zbl 1239.05028
[22] G. Tardos, On 0-1 matrices and small excluded submatrices, J. Combin. Theory Ser. A, 111 (2005), pp. 266-288. · Zbl 1070.05019
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.