<p>I'm interested in large families of vectors, which include many large linearly-independent sets, with the property that percolation results in any individual vector in the family not being spanned with non-negligible probability. More precisely,  does there exist some finite field <span class="math-container">$\mathbb{F}$</span> such that for arbitrarily large dimension <span class="math-container">$d$</span> and integer <span class="math-container">$k=k(d) = \omega(1)$</span> (e.g. <span class="math-container">$k=\log d$</span> or <span class="math-container">$k=\log \log d$</span> will do), there is a family of vectors <span class="math-container">$B \subseteq \mathbb{F}^d$</span> such that:</p>
<ul>
<li><span class="math-container">$B$</span> is the disjoint union of <span class="math-container">$B_1,\ldots,B_k$</span>, where each <span class="math-container">$B_i$</span> is an independent set of size on the order of <span class="math-container">$d$</span> (for example, <span class="math-container">$|B_i| \geq d/2$</span>).</li>
<li>If <span class="math-container">$S$</span> is a uniformly random subset of <span class="math-container">$B$</span> (i.e., it includes each element of <span class="math-container">$B$</span> independently with probability <span class="math-container">$1/2$</span>), then any <span class="math-container">$e \in B$</span> is not spanned by <span class="math-container">$S$</span> with probability at least on the order of <span class="math-container">$1/k$</span>. Formally, the following should hold for each <span class="math-container">$e \in B$</span>: <span class="math-container">$$\Pr [ e \not\in span(S)] \geq \Omega\left(\frac{1}{k}\right)$$</span></li>
</ul>
<p>This is a question that seems vaguely related to error correcting codes, as well as to constructions of vector families with certain girth properties. I was able to prove that anything substantially larger than <span class="math-container">$1/k$</span> is impossible, but I can't seem rule out a construction which attains something on the order of <span class="math-container">$1/k$</span>. Any pointers to related constructions appreciated.</p>

CC BY-SA 4.0
2024-09-16T10:38:58.160Z
Can you be more precise about your quantifiers? For example, "for all $\mathbb{F}$". Also, you need $k\frac{d}{2} \le |\mathbb{F}^d|$. Why not just be precise? idgi
mathworker21
CC BY-SA 4.0
2024-09-16T19:07:55.513Z
You are right. Hopefully this is more clear.
sd234
CC BY-SA 4.0
2024-09-16T19:33:29.357Z
Thanks, but it's still vague. You should say "for SOME arbitrarily large ...", since "such that for arbitrarily large ..." means "such that for ALL arbitrarily large ...", which you don't want, since you need $k$ to be small (but you're asking if there is some $k = k(d)$ that is $\omega(1)$).
mathworker21
<co.combinatorics><linear-algebra><coding-theory><matroids>
Large vector families with certain spanning properties on percolation
sd234
# Large vector families with certain spanning properties on percolation

(Asked by: username_0 on 2024-09-13)

I'm interested in large families of vectors, which include many large linearly-independent sets, with the property that percolation results in any individual vector in the family not being spanned with non-negligible probability. More precisely, does there exist some finite field $\mathbb{F}$ such that for arbitrarily large dimension $d$ and integer $k=k(d) = \omega(1)$ (e.g. $k=\log d$ or $k=\log \log d$ will do), there is a family of vectors $B \subseteq \mathbb{F}^d$ such that:

* $B$ is the disjoint union of $B\_1,\ldots,B\_k$, where each $B\_i$ is an independent set of size on the order of $d$ (for example, $|B\_i| \geq d/2$).
* If $S$ is a uniformly random subset of $B$ (i.e., it includes each element of $B$ independently with probability $1/2$), then any $e \in B$ is not spanned by $S$ with probability at least on the order of $1/k$. Formally, the following should hold for each $e \in B$: $$\Pr [ e \not\in span(S)] \geq \Omega\left(\frac{1}{k}\right)$$

This is a question that seems vaguely related to error correcting codes, as well as to constructions of vector families with certain girth properties. I was able to prove that anything substantially larger than $1/k$ is impossible, but I can't seem rule out a construction which attains something on the order of $1/k$. Any pointers to related constructions appreciated.

**Tags:** co.combinatorics, linear-algebra, coding-theory, matroids

> **Comments:**
> **username_1**: Can you be more precise about your quantifiers? For example, "for all $\mathbb{F}$". Also, you need $k\frac{d}{2} \le |\mathbb{F}^d|$. Why not just be precise? idgi  
> **username_0**: You are right. Hopefully this is more clear.  
> **username_1**: Thanks, but it's still vague. You should say "for SOME arbitrarily large ...", since "such that for arbitrarily large ..." means "such that for ALL arbitrarily large ...", which you don't want, since you need $k$ to be small (but you're asking if there is some $k = k(d)$ that is $\omega(1)$).  

---

## 0 answers

