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

CREATORJagdeep Singh
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text