Note on the \(f\)-vectors of cutsets in the subspace lattice (Q1942055): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2013.01.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2003958315 / rank | |||
Normal rank |
Latest revision as of 19:25, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Note on the \(f\)-vectors of cutsets in the subspace lattice |
scientific article |
Statements
Note on the \(f\)-vectors of cutsets in the subspace lattice (English)
0 references
15 March 2013
0 references
Let \(P\) be a finite poset with minimal element \(\hat{0}\) and maximal element \(\hat{1}\). A \textit{cutset} in \(P\) is a subset \(K \subseteq P\) with the property that each maximal chain in \(P\) contains an element of \(K\). A cutset is nontrivial if it contains neither \(\hat{0}\) nor \(\hat{1}\). When \(P\) is graded, the \(f\)-\textit{vector} of a cutset is the vector \((f_0, f_1, \ldots, f_n)\), where \(f_i\) counts the number of elements of rank \(i\) in \(K\). This paper considers the poset \(\mathcal{L}_n(q)\) of subspaces of \(\mathbb{F}_q^n\), the \(n\)-dimensional vector space over the finite field \(\mathbb{F}_q\). The subspaces are ordered by containment and the poset is graded by dimension. The number of elements of rank \(k\) in \(\mathcal{L}_q(n)\) is enumerated by the \(q\)-binomial coefficient \(\begin{bmatrix} n \\ k \end{bmatrix}\). One can consider the set of all \(0 < \alpha \leq 1\) for which there exists a nontrivial cutset in \(\mathcal{L}_n(q)\) containing \(\left\lfloor \alpha \begin{bmatrix} n\\k\end{bmatrix} \right\rfloor\) elements of rank \(k\) for each \(0 < k < n\). The function \(\alpha(n)\) denotes the infimum of all such \(\alpha\). The main result of this paper shows that when \(n\) is sufficiently large, \[ \frac{1}{n} \leq \alpha(n) \leq \frac{3}{2\ln \lceil n/2 \rceil}. \] In particular, \(\alpha_n \rightarrow 0\) as \(n \rightarrow \infty\). This parallels a result of \textit{M. Haines} and \textit{S. Shahriari} [J. Comb. Theory, Ser. A 93, No. 1, 177--181 (2001; Zbl 0981.06001)], which establishes an analogous result for the Boolean lattice.
0 references
cutset
0 references
subspace lattice
0 references
\(f\)-vector
0 references