k k -loose elements and k k -paving matroids
Jagdeep Singh · 2024
Read k k -loose elements and k k -paving matroids by Jagdeep Singh (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10326.txt.
Introduction
Singh studies matroid elements that sit only in large circuits, in this 2024 paper. A matroid abstracts the idea of independence across many settings. An element earns the label k-loose when every circuit through it exceeds the rank minus k, making it loosely bound to the structure.
With a co-author, Singh had earlier classified binary matroids holding a 1-loose element. The new work sets a sharp linear cap, in terms of rank, on the size of any binary matroid with a k-loose element. It also bounds the rank of paving matroids, where every element is loose, over finite fields. The bounds tighten what builders of such structures can attempt.
Catalog record
| CREATOR | Jagdeep Singh |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-10326
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
k k -loose elements and k k -paving matroids Jagdeep Singh Abstract . For a matroid of rank r r and a non-negative integer k k , an element is called k k -loose if every circuit containing it has size greater than r − k r-k . Zaslavsky and the author characterized all binary matroids with a 1 1 -loose element. In this paper, we establish a sharp linear bound on the size of a binary matroid, in terms of its rank, that contains a k k -loose element. A matroid is called k k -paving if all its elements are k k -loose. Rajpal showed that for a prime power q q , the rank of a G F ( q ) GF(q) -matroid that is k k -paving is bounded. We provide a bound on the rank of G F ( q ) GF(q) -matroids that are cosimple and have two k k -loose elements. Consequently, we strengthen the result of Rajpal by providing a bound on the rank of G F ( q ) GF(q) -matroids that are k k -paving. Additionally, we provide a bound on the size of binary matroids that are k k -paving. 1991 Mathematics Subject Classification 05B35, 94B65 1. Introduction The notation and terminology follow [ 2 ] unless stated otherwise. All graphs and matroids considered here are finite and simple. For a matroid of rank r and a non-negative integer k , an element t of M is called k -loose if every circuit of M that contains t has size greater than r-k . A matroid M is called k -paving if every element of M is k -loose. Note that a matroid M is paving if and only if M is 1 -paving. Acketa [ 1 ] provided a characterization of all 1 -paving matroids that are binary, while Oxley [ 3 ] determined all ternary 1 -paving matroids. Zaslavsky and the author characterized all binary matroids with a 1 -loose element [ 6 ] . In Section 2, we show that the size of a binary matroid that contains a k -loose element is linear in terms of its rank. In particular, we provide the following sharp bound. Theorem 1.1 . For r\geq 5 and 0\leq k\leq\frac{r-2}{3} , let M be a simple binary matroid of rank r with no coloops and a k -loose element. Then |E(M)|\leq 2^{k}(r-k+1) . We say a matroid M is a GF(q) -matroid if M is representable over the field of q elements. Section 3 considers GF(q) -matroids that have two k -loose elements. We show that the rank of such a matroid is bounded unless the two k -loose elements form a cocircuit of size two. The following is the precise statement. Theorem 1.2 . Let M be a simple GF(q) -matroid with no coloops that has two k -loose elements e and f . Then r(M)\leq(q+1)(k-1)+2q , or \{e,f\} is a cocircuit of M . An immediate consequence of Theorem 1.2 is the following. Corollary 1.3 . Let M be a simple GF(q) -matroid with no coloops that is k -paving. Then M is a circuit or r(M)\leq(q+1)(k-1)+2q . Rajpal [ 5 , Proposition 8] demonstrated the existence of a rank bound for k -paving matroids representable over GF(q) . Corollary 1.3 strengthens this result by giving an explicit rank bound for GF(q) -matroids that are k -paving. Observe that paving matroids are precisely 1 -paving matroids. Therefore by Corollary 1.3 , a paving matroid representable over GF(q) has rank at most 2q , unless it is a circuit. A binary k -paving matroid is maximal if it is not a proper minor of any other binary k -paving matroid. Rajpal [ 5 ] established a connection between maximal binary k -paving matroids and Reed-Muller codes, proving the following. Proposition 1.4 . For k\geq 1 , let G be a generator matrix of the Reed-Muller code R(1,k+2) . Then the vector matroid of G is a maximal binary k -paving matroid. Additionally, Rajpal determined all binary 2 -paving matroids. In Section 4, we provide a bound on the size of binary k -paving matroids. Theorem 1.5 . Let M be a simple binary k -paving matroid of rank r , where M is not a circuit and r\geq k+4 , and let t=\lfloor\frac{3k+1-r}{2}\rfloor . Then r(M)\leq 3k+1 , and |E(M)|\leq(r+1)+\sum_{i=0}^{t}\binom{k}{i}. Note that every simple binary matroid with rank at most k+2 is k -paving, and every simple triangle-free binary matroid of rank k+3 is k -paving. This includes binary affine matroids of rank k+3 . To demonstrate the assistance Theorem 1.5 provides in finding all k -paving binary matroids, we apply it to 3 -paving binary matroids and obtain the following result. Corollary 1.6 . Let M be a simple binary 3 -paving matroid of rank at least seven. Then, r(M)\leq 10 and |E(M)|\leq 13 . In particular, the size of M is at most 12,13,11, and 12 when the rank of M is 7,8,9, and 10, respectively. 2. k -loose elements in binary matroids Theorem 1.1 provides a sharp linear bound on the size of a binary matroid containing a k -loose element, in terms of its rank. Specifically, if a binary matroid M has a 1 -loose element, then the size of M is at most 2r . If M has a 2 -loose element, then the size of M does not exceed 4r-4 . Proof of Theorem 1.1 . Let e be a k -loose element of M . Note that if k=0 , then by [ 4 , Lemma 3.1] , M is a circuit, and the result follows. Therefore k\geq 1 . Suppose that e is not (k-1) -loose. It follows that there is a basis B=\{e_{1},\ldots,e_{r}\} of M such that, in the standard binary representation P=[I_{r}|Q] of M with respect to B , the column e^{P} labeled by e has its first k entries equal to zero, while all other entries are non-zero. We call the set of indices of the non-zero entries of a column f^{P} in Q the support of f^{P} , denoted as \text{supp}(f^{P}) . The entries of f^{P} , excluding the first k entries, are called the root entries of f^{P} , and the set of indices of the non-zero root entries of f^{P} is the root support of f^{P} . Let Q-e^{P} denote the columns in Q excluding e^{P} . 2.0.1 . For a column f^{P} in Q-e^{P} , the sum of the number of zeroes in the first k entries of f^{P} and the number of non-zero root entries of f^{P} is at most k+1 . Suppose otherwise. Then e^{P}+f^{P} has at least k+2 zeroes, so at most r-(k+2) columns from I_{r} can be added to e^{P}+f^{P} to obtain a column with all entries equal to zero. It follows that e is in a circuit of size at most r-k , a contradiction. Therefore 2.0.1 holds. Let F be a set of all columns in Q-e^{P} such that, for any pair f^{P},g^{P} in F , the sum f^{P}+g^{P} has its first k entries equal to zero. It is clear that the