Color-unavoidable covers from cyclic interval unrolling

---

Standing

This page gives a positive, independently checkable instance of the color-unavoidable covering step left open in incidence-cover extraction. It does not prove that the covered axis-line families have unbounded dissociated chromatic number, or that arbitrary binary matrices satisfy the proposed cover inequality.

Write $\chi_1$ for partition number into fully dissociated column sets and $\chi_{\mathbb Q}$ for partition number into rationally independent column sets. Columns are indexed throughout. The rank-at-most-three theorem in Section 5 additionally assumes distinct, nonzero columns.

The principal proved facts are:

• A seven-column binary matrix of rational rank three has $\chi_1=2$, but an explicit two-sheet incidence cover has $\chi_1=3$.
• If all $n$ columns of a matrix are circular intervals in one cyclic order of its $r$ rows, then

$$\sup_{\widetilde A\text{ finite incidence cover of }A} \chi_1(\widetilde A)\geq\left\lceil\frac nr\right\rceil. \tag{1}$$

• For every binary matrix with distinct nonzero columns and rational rank at most three,

$$\sup_{\widetilde A\text{ finite incidence cover of }A} \chi_1(\widetilde A)\geq\chi_{\mathbb Q}(A). \tag{2}$$

All these statements have analytic proofs below. A finite enumeration motivated the first example but is not needed for any theorem on this page.

1. Interval columns have only the usual independence obstruction

Lemma. For columns that are indicators of intervals in one linear row order, dissociation is equivalent to rational linear independence.

Proof. On $N$ ordered rows apply the injective linear map

$$D(x_1,\ldots,x_N) =(x_1,x_2-x_1,\ldots,x_N-x_{N-1},-x_N).$$

It sends the indicator of $[a,b]$ to $e_a-e_{b+1}$. Thus it sends the column family to the oriented incidence columns of a graph on $\{1,\ldots,N+1\}$, allowing parallel edges. A forest has linearly independent incidence columns, as one sees by removing leaves. Every cycle has a nonzero relation with coefficients in $\{-1,0,1\}$, by following the cycle and assigning the orientation signs. Parallel edges give the two-edge version of the same relation. Consequently every rationally dependent subfamily has a ternary relation. Injectivity of $D$ transfers the conclusion back to the interval columns. $\square$

This proves the consequence usually obtained from total unimodularity, without importing a matrix theorem.

Exceptional-column corollary. Suppose deleting a set $E$ of $k$ columns from an $N$-row matrix leaves interval indicators in one row order. If its $n$ columns are partitioned into $q$ dissociated sets, then

$$n\leq qN+k. \tag{3}$$

Indeed, after deleting $E$, each color class is rationally independent and contains at most $N$ columns. Count the exceptional columns only once across the partition.

2. A two-sheet cover forces a third color

Let $B_3$ have all seven nonzero binary columns in three coordinates:

$$a,\ b,\ c,\quad a+b,\ a+c,\ b+c,\quad a+b+c.$$

Here letters denote distinct coordinate unit vectors. Its rational coloring number is three: seven columns cannot be partitioned into two independent sets in rank three, while the units, the three two-element columns, and the last column form three independent sets.

Its dissociated coloring number is only two. Put the three units in one class and the remaining four columns in the other. The rational kernel of the latter four-column matrix is generated by $(1,1,1,-2)$, so it contains no nonzero ternary vector.

Now take two sheets, labeled $0,1$. Use the identity incidence permutation everywhere except at the incidence of $c$ with the base column $b+c$, where use the transposition. The fourteen covered columns are the six coordinate units and

$$\begin{aligned} p_i&=a_i+b_i,& q_i&=a_i+c_i &&(i=0,1),\\ r_0&=b_0+c_1,&r_1&=b_1+c_0,\\ t_i&=a_i+b_i+c_i &&&(i=0,1). \end{aligned} \tag{4}$$

Order the six rows as

$$c_0,\ a_0,\ b_0,\ c_1,\ a_1,\ b_1. \tag{5}$$

After deleting just $r_1$, every remaining column is an interval in this order. The five remaining two-element columns are consecutive pairs; $t_0$ and $t_1$ are the first and last three-element intervals. Equation (3) with $n=14,N=6,k=1$ rules out two colors, since $14>2\cdot6+1$.

Three colors suffice: take the six units; the five columns $q_0,p_0,r_0,q_1,p_1$; and the three columns $r_1,t_0,t_1$. The middle class consists of the edges of a path and is independent; the last class is independent because the $a_0$ and $a_1$ coordinates first force the two triple coefficients to vanish. Hence this cover has

$$\chi_1=3=\chi_{\mathbb Q}(B_3). \tag{6}$$

This is an actual cover chosen before its columns are colored. It does not use fiber-monochromatic copies of complete covers.

3. Circular interval unrolling

Assume that every column of $A$ is a nonempty circular interval in one cyclic order $0,1,\ldots,r-1$ of the base rows. For each column choose a cyclic starting row and a length in $\{1,\ldots,r\}$; a full-row column may have any chosen starting row.

For degree $m$, put the $rm$ covered rows in the cyclic order obtained by repeating the base row order $m$ times. For each base interval, take its $m$ translates by multiples of $r$, each as a consecutive interval of the same length on this larger cycle. They define its $m$ covered columns.

This is an incidence cover: for any one row type lying in a base column, its occurrences in the $m$ translated intervals run bijectively through the $m$ sheets. Thus the incidence correspondence at that base incidence is a permutation, exactly as required by the covering definition.

Cut the large cycle at any row boundary. At most one translate of each base column crosses that cut, because its length is at most $r$ and successive starts are $r$ positions apart. Delete those columns. There are at most $n$ of them, and every remaining column is an ordinary interval in the resulting linear row order.

If this cover had a dissociated $q$-coloring, (3) would give

$$mn\leq qrm+n. \tag{7}$$

For any integer $q<n/r$, choose $m>n/(n-qr)$. Then (7) is impossible. Taking $q=\lceil n/r\rceil-1$ proves (1).

Only the columns crossing one global cut are discarded; their number is bounded independently of the cover degree. This bounded-exception property is the reason the argument yields the base density rather than an entropy bound with a logarithmic loss.

4. A general growing family, and its scope

Let $C_r$ consist of all distinct nonempty circular intervals on $r\geq2$ cyclically ordered rows. There are

$$|C_r|=r(r-1)+1$$

columns: $r$ intervals of each proper length and one full-row interval. It follows from (1) that

$$\sup_{\widetilde C_r}\chi_1(\widetilde C_r)\geq r. \tag{8}$$

Also $\chi_{\mathbb Q}(C_r)=r$. The lower bound is the column/row ratio. For the upper bound, group the proper intervals by starting row; the $r-1$ nested intervals in one group are independent. Put the full-row interval in one such group; that enlarged chain of $r$ intervals is still independent. Thus (8) reaches the rational coloring number for this entire family.

There is an explicit degree bound, and the constructed covers have exactly $r$ colors. Choose the full-row intervals to start at the global cut, then repeat them every $r$ positions. For each proper length $\ell$, all $rm$ possible starting positions occur, and exactly $\ell-1$ of those intervals cross the cut. Hence the exceptional count is exactly

$$k_r=\sum_{\ell=1}^{r-1}(\ell-1)=\binom{r-1}{2}.$$

A dissociated $(r-1)$-coloring would imply

$$m\bigl(r(r-1)+1\bigr)\leq (r-1)rm+k_r, \quad\text{or equivalently}\quad m\leq k_r.$$

Thus $m=k_r+1$ suffices. Conversely, color by the base starting row. For each such color, its covered columns form $m$ nested chains supported on disjoint blocks of $r$ consecutive covered rows. Put the full-row columns in the color corresponding to their chosen starting row. Every color class is rationally independent, so this explicit cover satisfies

$$\chi_1(\widetilde C_r)=\chi_{\mathbb Q}(\widetilde C_r)=r \quad\text{when }m>\binom{r-1}{2}. \tag{9}$$

The case $r=3,m=2$ is the fourteen-column construction above, after relabeling rows.

The full Boolean-column matrix $B_r$, containing every nonzero vector in $\{0,1\}^r$, contains $C_r$. Any cover of a column submatrix extends to a cover of the whole matrix by assigning arbitrary incidence permutations to its other columns. Therefore

$$\sup_{\widetilde B_r}\chi_1(\widetilde B_r)\geq r. \tag{10}$$

For $r=4$, this also proves the proposed inequality for the full Boolean matrix $B_4$, with a cover of degree four, since $\chi_{\mathbb Q}(B_4)=4$. For clarity, an explicit four-independent-set partition is obtained from the four cyclic starting-row chains: put the full-row column in the chain starting at 1; add $e_1+e_3$ to the chain starting at 2; add $e_2+e_4$ to the chain starting at 3; leave the fourth chain unchanged. The two added columns have a nonzero coordinate outside the support of their respective three-column chains. These four classes account for all fifteen columns.

No theorem for all rank-four binary matrices is claimed. Nor does (9) reach $\chi_{\mathbb Q}(B_r)$ in growing rank: the elementary bound $\chi_{\mathbb Q}(B_r)\geq\lceil(2^r-1)/r\rceil$ is already larger than $r$ for every $r\geq5$.

4.1 The circular family cannot have uniform proportional extraction

This family cannot replace the axis-line family in the required problem. Set $n_r=r(r-1)+1$. Each row of $C_r$, and of any incidence cover of it, has total degree at most $n_r$. For a dissociated subset $D$ in a degree-$m$ cover, all its $2^{|D|}$ subset sums are distinct integer vectors in $\{0,\ldots,n_r\}^{rm}$. Consequently

$$|D|\leq rm\log_2(n_r+1),\qquad \frac{|D|}{mn_r}\leq\frac{r\log_2(n_r+1)}{n_r}\longrightarrow0. \tag{11}$$

Thus even the full covered configurations fail every fixed positive proportional-extraction bound as $r$ grows. This is a proved obstruction, not merely an unverified extraction hypothesis.

4.2 Bounded-exception intervalization fails for the controlled line bases

Let $L_t$ have side lengths $d_i=i+2$, let $N=\prod_i d_i$, and put $s_t=\sum_i1/d_i$, so that $|L_t|=Ns_t$. In any ordinary degree-$m$ incidence cover, every column has size at least three, and any two distinct columns meet in at most one row. The latter fact follows by projection: two distinct base lines meet in at most one point, and distinct lifts of the same base line are disjoint.

Suppose deleting some columns leaves intervals in one linear order of the $N'=mN$ covered rows. An interval column $E$ contains $|E|-1$ adjacent row pairs. No such pair can belong to two remaining columns, because that would give an intersection of size at least two. Hence

$$\sum_{E\text{ remaining}}(|E|-1)\leq N'-1, \qquad |\{E\text{ remaining}\}|\leq\frac{mN-1}{2}.$$

The number of deleted columns must therefore be at least

$$mNs_t-\frac{mN-1}{2} =mN\left(s_t-\frac12\right)+\frac12. \tag{12}$$

For $t\geq2$, $s_t\geq1/3+1/4=7/12$, so this lower bound grows linearly with the cover degree. In particular the bounded-exception interval-unrolling mechanism of Section 3 cannot be implemented on these line covers.

The same conclusion holds if every base row is first duplicated $R$ times. Covered columns then have size at least $3R$, and pairwise intersections have size at most $R$. In any proposed interval subfamily, the consecutive blocks of $R+1$ rows used by different columns must be disjoint as blocks. Thus

$$\sum_{E\text{ remaining}}(|E|-R)\leq RmN-R,$$

again giving at most $(mN-1)/2$ remaining columns and the same bound (12). Here the word "disjoint" refers to the collections of consecutive blocks; distinct blocks may themselves overlap in rows.

This excludes only an interval-indicator reduction after a bounded number of column deletions. It does not exclude other oriented graph incidence representations, other integer-cycle constructions, or the proposed cover inequality itself.

5. The proposed inequality in rational rank at most three

Let $A$ have distinct nonzero binary columns and rational rank at most three. Choose a basis of its row space. Restriction of columns to these basis rows is injective, because every other row is their rational linear combination. No nonzero column restricts to zero. Thus, in rank $s$, there are at most $2^s-1$ columns.

Every proper subfamily of the seven nonzero three-bit vectors is the union of two rationally independent sets. One may verify this without a matroid partition theorem. Up to coordinate permutations, the missing vector has weight one, two, or three, and the following partitions of the other six vectors suffice:

Restrictions of these partitions handle every smaller family, including ranks one and two after adjoining zero coordinates. Therefore $\chi_{\mathbb Q}(A)\leq2$, unless its rank is three and all seven nonzero three-bit patterns occur.

If $\chi_{\mathbb Q}(A)=1$, inequality (2) is immediate. If it is two, the columns have a nonzero integer relation. The integer-relation covering lift produces a cover containing a nonzero ternary relation, so its dissociated coloring number is at least two.

It remains to consider all seven three-bit patterns. Any additional base row is a rational linear functional $\lambda_1x_1+\lambda_2x_2+ \lambda_3x_3$ taking values in $\{0,1\}$ on all these patterns. Evaluation on the units gives $\lambda_i\in\{0,1\}$, and evaluation on $(1,1,1)$ shows that at most one coefficient is 1. Every row of $A$ is consequently zero or a duplicate of one of the three basis rows. Use the cover in Section 2, copying its incidence permutations identically to every duplicate base row. Zero rows are immaterial. The covered matrix has exactly the same relations as the fourteen-column example, and hence needs three colors. This completes (2).

The distinct-column hypothesis matters to this reduction: repeated columns can make the rational coloring number arbitrarily large even in bounded rank. No statement about that case is inferred here.

6. Finite discovery computation: exact range, not a proof dependency

One bounded standard-library Python computation checked all 32 normalized degree-two covers of $B_3$. In each column fiber, relabel the two sheet indices so that its incidence at the first row in its support is the identity. There remain five independent binary choices: one noninitial incidence for each two-element column, and two for the three-element column. The singleton columns have no remaining choice. This normalization does not assert that the 32 representatives are pairwise nonisomorphic; it covers every degree-two incidence assignment up to these independent column-fiber relabelings.

For each representative the computation enumerated all $2^{14}$ subset sums. Equal-sum pairs identify ternary-relation supports after canceling their common columns. Taking the upward closure of those supports identifies every nondissociated subset; testing each subset and its complement then counts the labeled two-color partitions exactly.

The distribution of these counts was

The representative (4) is one of the twelve with zero two-color partitions. Its dissociated-subset counts by sizes $0,1,\ldots,7$ were

$$1,14,91,354,877,1336,1018,16,$$

and none had size eight or more. Subsequent finite scrutiny of this same fourteen-column representative recovered the interval-deletion proof in Section 2. No cover degree or dimension beyond the stated 32-cover range was computationally explored for this task. The analytic proofs above do not rely on the reported counts, and no enumeration artifact is required as a theorem certificate.