Travis, Dillon and Sali, Attila (2021) Exponential multivalued forbidden configurations. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 23 (1). ISSN 1462-7264
|
Text
2006.16305v3.pdf - Published Version Available under License Creative Commons Attribution. Download (181kB) | Preview |
Abstract
The forbidden number forb(m,F), which denotes the maximum number of unique columns in an m-rowed (0, 1)-matrix with no submatrix that is a row and column permutation of F, has been widely studied in extremal set theory. Recently, this function was extended to r-matrices, whose entries lie in {0, 1, . . . , r-1}. The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many (0, 1)-matrices F, including all 2-rowed matrices when r > 3. We also prove a stability result for the 2 × 2 identity matrix. Along the way, we expose some interesting qualitative differences between the cases r = 2, r = 3, and r > 3. © 2021 Discrete Mathematics and Theoretical Computer Science. All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | Lawrence UniversityWI, United States Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Computer Science, Budapest University of Technology and Economics, Budapest, Hungary Cited By :1 Export Date: 4 September 2023 Funding details: Emberi Eroforrások Minisztériuma, EMMI, BME FIKP-MI/SC Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K– 116769, K–132696 Funding details: Nemzeti Kutatási, Fejlesztési és Innovaciós Alap, NKFIA, TUDFO/51757/2019-ITM Funding details: National Research, Development and Innovation Office Funding text 1: †This author’s work is partially supported by the National Research, Development and Innovation Office (NKFIH) [grant K– 116769 and K–132696]; the National Research, Development and Innovation Fund [TUDFO/51757/2019-ITM, Thematic Excellence Program]; the BME NC TKP2020 grant of NKFIH Hungary; and the BME-Artificial Intelligence FIKP grant of EMMI [BME FIKP-MI/SC]. It is also connected to the “Development of quality-oriented and harmonized R+D+I strategy and functional model at BME” project supported by the New Hungary Development Plan [Project ID: TÁMOP-4.2.1/B-09/1/KMR-2010-0002]. |
| Uncontrolled Keywords: | Matrix algebra; Computer science; Combinatorial mathematics; A-stability; Extremal set theory; Combinatorics; Forbidden configurations; Qualitative differences; 1)-matrices; (0; Multi-valued; Column permutations; Identity matrices; R matrices; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 15 Jul 2025 09:44 |
| Last Modified: | 15 Jul 2025 09:44 |
| URI: | https://real.mtak.hu/id/eprint/221115 |
Actions (login required)
 |
Edit Item |
