On the Subspace Choosability in Graphs¹¹1An extended abstract of this work appeared in Proc. of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb), 2021 [7].

Graph coloring is the problem of minimizing the number of colors in a vertex coloring of a graph $G$ where adjacent vertices receive distinct colors. This minimum is known as the chromatic number of $G$ and is denoted by $\chi(G)$. Being one of the most popular topics in graph theory, the graph coloring problem was extended and generalized over the years in various ways. One classical variant, initiated independently by Vizing in 1976 [19] and by Erdös, Rubin, and Taylor in 1979 [8], is that of choosability, also known as list coloring, which deals with vertex colorings with some restrictions on the colors available to each vertex. A graph $G=(V,E)$ is said to be $k$-choosable if for every assignment of a set $S_{v}$ of $k$ colors to each vertex $v\in V$, there exists a choice of colors $c_{v}\in S_{v}$ that form a proper coloring of $G$ (that is, $c_{v}\neq c_{v^{\prime}}$ whenever $v$ and $v^{\prime}$ are adjacent in $G$). The choice number of a graph $G$, denoted $\mathop{\mathrm{ch}}(G)$, is the smallest integer $k$ for which $G$ is $k$-choosable. It is well known that the choice number $\mathop{\mathrm{ch}}(G)$ behaves quite differently from the standard chromatic number $\chi(G)$. In particular, it can be arbitrarily large even for bipartite graphs (see, e.g., [8]). The choice number of graphs enjoys an intensive study in graph theory involving combinatorial, algebraic, and probabilistic tools (see, e.g., [1]). The computational decision problem associated with the choice number is unlikely to be tractable, because it is known to be complete for the complexity class $\Pi_{2}$ of the second level of the polynomial-time hierarchy even for bipartite planar graphs [8, 10, 11].

Another interesting variant of graph coloring, introduced by Lovász [14] in the study of Shannon capacity of graphs, is that of orthogonal representations, where the vertices of the graph do not receive colors but vectors from some given vector space. A $t$-dimensional orthogonal representation of a graph $G=(V,E)$ over $\mathbb{R}$ is an assignment of a nonzero vector $x_{v}\in\mathbb{R}^{t}$ to every vertex $v\in V$, such that $\langle x_{v},x_{v^{\prime}}\rangle=0$ whenever $v$ and $v^{\prime}$ are adjacent in $G$.²²2Orthogonal representations of graphs are sometimes defined in the literature as orthogonal representations of the complement, namely, the definition requires vectors associated with non-adjacent vertices to be orthogonal. The orthogonality dimension of a graph $G$ over $\mathbb{R}$ is the smallest integer $t$ for which there exists a $t$-dimensional orthogonal representation of $G$ over $\mathbb{R}$. The orthogonality dimension parameter is closely related to several other well-studied graph parameters, and in particular, for every graph $G$ it is bounded from above by the chromatic number $\chi(G)$. The orthogonality dimension of graphs and its extensions to fields other than the reals have found a variety of applications in combinatorics, information theory, and theoretical computer science (see, e.g., [15, Chapter 10] and [12]). As for the computational aspect, the decision problem associated with the orthogonality dimension of graphs is known to be $\mathsf{NP}$-hard over every field [16] (see also [9]).

In 2010, Haynes, Park, Schaeffer, Webster, and Mitchell [13] introduced another variant of the chromatic number of graphs that captures both the choice number and the orthogonality dimension. In this setting, which we refer to as subspace choosability, each vertex of a graph $G$ is assigned a $k$-dimensional subspace of some finite-dimensional vector space, and the goal is to choose for each vertex a nonzero vector from its subspace so that adjacent vertices receive orthogonal vectors. The smallest integer $k$ for which such a choice is guaranteed to exist for all possible subspace assignments is called the subspace choice number of the graph $G$, formally defined as follows.

The work [13] has initiated the study of the subspace choice number of graphs over the real and complex fields. Among other things, it was shown there that a graph is $2$-subspace choosable over $\mathbb{R}$ if and only if it contains no cycles. We note that this is in contrast to the characterization given in [8] for the (chromatic) $2$-choosable graphs, which include additional graphs such as even cycles. This implies that the choice number and the subspace choice number do not coincide even on the $4$-cycle graph. Over the complex field $\mathbb{C}$, however, it was shown in [13] that a graph is $2$-subspace choosable if and only if it either contains no cycles or contains only one cycle and that cycle is even. This demonstrates the possible effect of the field on the subspace choice number. It further follows from [13] that for every graph $G$ and every field $\mathbb{F}$, it holds that $\mathop{\mathrm{ch\text{-}s}}(G,\mathbb{F})\leq\Delta(G)+1$ where $\Delta(G)$ stands for the maximum degree in $G$. In fact, a similar argument shows that $\Delta(G)$ can be replaced in this bound by the degeneracy of $G$ (i.e., the smallest integer $k$ for which every subgraph of $G$ contains a vertex of degree at most $k$).

In this section we relate the subspace choice number of a graph over a general field to its average degree and prove Theorem 1.2. We start with the following definition of $k$-partitioned graphs (for an example, see Lemma 2.6).

The following theorem shows that the subspace choice number of a $k$-partitioned graph exceeds $k$ over any field.

• Proof:

  Fix an arbitrary field $\mathbb{F}$. Let $G=(V,E)$ be a $k$-partitioned graph, and for every vertex $v\in V$, let $E_{v}=E_{v}^{(1)}\cup\cdots\cup E_{v}^{(k)}$ be the corresponding partition of the edges incident with $v$, as in Definition 2.1. We use these partitions to define a $k$-subspace assignment over $\mathbb{F}$ to the vertices of $G$ involving vectors from the space $\mathbb{F}^{|E|}$, where each entry corresponds to an edge $e\in E$. To a vertex $v\in V$ we assign the subspace $W_{v}$ spanned by the $k$ vectors $w^{(1)}_{v},\ldots,w^{(k)}_{v}$, where $w^{(i)}_{v}$ is the $0,1$ indicator vector of the subset $E_{v}^{(i)}$ of $E$. In fact, some of the sets $E^{(i)}_{v}$ might be empty, and thus some of the vectors $w^{(i)}_{v}$ might be zeros, resulting in subspaces $W_{v}$ of dimension smaller than $k$. To fix it, one can increase the length of the vectors from $|E|$ to $|E|+k\cdot|V|$ and to add to each of the $k\cdot|V|$ vectors $w^{(i)}_{v}$ a nonzero entry in a coordinate on which all the others have zeros. These entries ensure that the dimension of every subspace $W_{v}$ is precisely $k$. For simplicity of notation, we refer from now on to these modified vectors as $w^{(i)}_{v}$.

  We show now that no choice of nonzero vectors from these subspaces satisfies that every two adjacent vertices receive orthogonal vectors over $\mathbb{F}$. To see this, consider some choice of a nonzero vector $x_{v}\in W_{v}$ for each vertex $v\in V$. We define a function $g:V\rightarrow[k]$ as follows. For every $v\in V$, $x_{v}$ is a nonzero linear combination of the vectors $w^{(1)}_{v},\ldots,w^{(k)}_{v}$, hence there exists some $j_{v}\in[k]$ for which the coefficient of $w^{(j_{v})}_{v}$ in this linear combination is nonzero. We define $g(v)$ to be such an index $j_{v}$. By assumption, there exist two adjacent vertices $v_{1},v_{2}\in V$ such that $\{v_{1},v_{2}\}\in E_{v_{1}}^{(g(v_{1}))}\cap E_{v_{2}}^{(g(v_{2}))}$. This implies that the entry that corresponds to the edge $\{v_{1},v_{2}\}$ of $G$ is nonzero in both $x_{v_{1}}$ and $x_{v_{2}}$. However, the supports of the subspaces $W_{v_{1}}$ and $W_{v_{2}}$ intersect at this single entry, implying that the vectors $x_{v_{1}}$ and $x_{v_{2}}$ are not orthogonal over $\mathbb{F}$. This implies that there exists a $k$-subspace assignment over $\mathbb{F}$ to the vertices of $G$ with no appropriate choice of nonzero vectors, yielding that $\mathop{\mathrm{ch\text{-}s}}(G,\mathbb{F})>k$, as required.  

Theorem 2.2 motivates the problem of determining the largest integer $k$ for which a given graph is $k$-partitioned. The following lemma uses a probabilistic argument to prove a lower bound on this quantity in terms of the average degree.

It is natural to ask whether Theorem 2.2 can be used to obtain better lower bounds on the subspace choice number of graphs than the one achieved by Theorem 1.2. The following lemma shows that for graphs with similar average and maximum degrees, Lemma 2.3 is tight up to the logarithmic term. Hence, the approach suggested by Theorem 2.2 cannot yield significantly better bounds for such graphs.

The proof of Lemma 2.4 uses the Lovász local lemma stated below (see, e.g., [4, Chapter 5]).

• Proof of Lemma 2.4:

  Let $G=(V,E)$ be a graph with maximum degree $D$, and let $k\geq c\cdot\sqrt{D}$ be an integer for some constant $c$ to be determined. We prove that $G$ is not $k$-partitioned by a probabilistic argument. For every vertex $v\in V$, consider a partition $E_{v}=E_{v}^{(1)}\cup\cdots\cup E_{v}^{(k)}$ of the set of the edges incident with $v$ into $k$ sets (some of the sets may be empty). We claim that there exists a function $g:V\rightarrow[k]$ such that no edge $\{v_{1},v_{2}\}$ of $G$ satisfies $\{v_{1},v_{2}\}\in E_{v_{1}}^{(g(v_{1}))}\cap E_{v_{2}}^{(g(v_{2}))}$. To prove it, consider a random function $g:V\rightarrow[k]$ such that each value $g(v)$ for $v\in V$ is chosen uniformly and independently at random from $[k]$. For every edge $e=\{v_{1},v_{2}\}\in E$, let $A_{e}$ denote the event that $e\in E_{v_{1}}^{(g(v_{1}))}\cap E_{v_{2}}^{(g(v_{2}))}$. The probability of each event $A_{e}$ is clearly $1/k^{2}$. In addition, every event $A_{e}$ is mutually independent of the set of all the other events $A_{e^{\prime}}$ but those satisfying $e\cap e^{\prime}\neq\emptyset$, whose number is at most $2\cdot(D-1)$. By the Lovász local lemma (Lemma 2.5), it follows that if

  $$e\cdot\tfrac{1}{k^{2}}\cdot(2D-1)\leq 1$$

  then with positive probability no event $A_{e}$ occurs. This implies that for an appropriate choice of the constant $c$, there exists a function $g$ with the required property. Since this holds for all possible partitions of the sets $E_{v}$ into $k$ sets, it follows that $G$ is not $k$-partitioned, and we are done.  

We end this section by proving that for certain graphs, the logarithmic term in Lemma 2.3 can be avoided. Here, the proof does not use a probabilistic construction of partitions, but an explicit one, based on finite projective planes.

• Proof:

  The proof is based on a well-known construction of projective planes, some of whose properties are described next (see, e.g., [6, Chapter 9]). For every prime power $q$, there exists a collection of $n=q^{2}+q+1$ elements called points, and $n$ sets of points, called lines, satisfying that every two lines intersect at a single point, every two points belong together to a single line, every point belongs to precisely $q+1$ of the lines, and every line includes precisely $q+1$ of the points. Fix some point $p$, let $L_{1},\ldots,L_{q+1}$ be the $q+1$ lines that include $p$, and put $L^{\prime}_{i}=L_{i}\setminus\{p\}$ for every $i\in[q+1]$. Note that the sets $L^{\prime}_{i}$ are pairwise disjoint. We view the graph $H$ as the graph on the vertex set $\cup_{i\in[q+1]}{L^{\prime}_{i}}$ in which two vertices are adjacent if they belong to distinct sets $L^{\prime}_{i}$. Observe that every two vertices of $H$ are adjacent if and only if the line that includes their points does not include $p$.

  Let $G=(V,E)$ be some subgraph of $H$ obtained by removing at most $q-1$ of its vertices, and observe that the number of its vertices satisfies

  $$|V|\geq(q+1)\cdot q-(q-1)=q^{2}+1.$$

  We show that $G$ is $q$-partitioned. To do so, we assign to every edge of the graph $G$ the line that includes the points represented by its vertices. This assignment induces for every vertex $v\in V$ a partition of the set $E_{v}$ of the edges incident with $v$ in $G$, where the sets of the partition correspond to the lines associated with the edges. Observe that this partition of $E_{v}$ consists of at most $q$ sets. Indeed, the vertex $v$ represents a point that belongs to $q+1$ lines, but no edge of $E_{v}$ is assigned the line that includes the point $p$ and the point of $v$.

  In order to show that these partitions satisfy the condition of Definition 2.1, we shall verify that if one chooses for every point represented by a vertex in $G$ a line that corresponds to an edge incident with it, then there exist two adjacent vertices in $G$ for which the same line was chosen. This indeed follows from the fact that no edge of $G$ corresponds to a line that includes $p$, hence the total number of lines associated with the edges of $G$ is at most $q^{2}$. Since the number of vertices in $G$ exceeds $q^{2}$, it follows that two vertices are assigned the same line. Since this line does not include $p$, the two vertices must be adjacent in $G$, completing the proof.  

Note that the graph $H$ from Lemma 2.6 is regular with degree $q^{2}$, hence the minimum degree of its subgraph $G$ is at least $q^{2}-q+1$, and yet $G$ is $q$-partitioned. This shows that the logarithmic term from Lemma 2.3 is not needed for $G$. By combining Lemma 2.6 with Theorem 2.2, we derive the following.

In this section we prove Theorem 1.3, which provides an upper bound on the subspace choice number of complete graphs over finite fields. We start with two useful lemmas.

• Proof:

  Consider the function $f:\mathbb{F}^{3}\rightarrow\mathbb{F}$ defined by $f(\alpha_{1},\alpha_{2},\alpha_{3})=\big{\langle}\sum_{i\in[3]}{\alpha_{i}\cdot w_{i}},\sum_{i\in[3]}{\alpha_{i}\cdot z_{i}}\big{\rangle}$. The function $f$ is a degree $2$ polynomial on $3$ variables over $\mathbb{F}$, and $(0,0,0)$ forms a root of $f$. The Chevalley theorem (see, e.g., [18, Chapter IV, Theorem 1D]) implies that $f$ has another root, as required.  

• Proof:

  Let $U_{1},U_{2},U_{3}\subseteq\mathbb{F}^{t}$ be three subspaces as in the statement of the lemma.

  Assume first that $\dim(U_{1}\cap U_{2})\geq 3$. In this case, there exist three linearly independent vectors in $U_{1}\cap U_{2}$. By Lemma 3.1, there exists a nonzero self-orthogonal linear combination of them. By choosing $x_{1}$ and $x_{2}$ to be this vector, it obviously holds that $\langle x_{1},x_{2}\rangle=0$ and that

  $$\dim(U_{3}\cap(x_{1})^{\perp}\cap(x_{2})^{\perp})=\dim(U_{3}\cap(x_{1})^{\perp})\geq\dim(U_{3})-1,$$

  as required.

  Assume next that $\dim(U_{1}\cap U_{3}^{\perp})\geq 1$. Here, $x_{1}$ can be chosen as an arbitrary nonzero vector of $U_{1}\cap U_{3}^{\perp}$, and $x_{2}$ as an arbitrary nonzero vector of $U_{2}$ satisfying $\langle x_{1},x_{2}\rangle=0$. Such a vector exists because $\dim(U_{2})\geq 2$. By $x_{1}\in U_{3}^{\perp}$, it follows that

  $$\dim(U_{3}\cap(x_{1})^{\perp}\cap(x_{2})^{\perp})=\dim(U_{3}\cap(x_{2})^{\perp})\geq\dim(U_{3})-1.$$

  The case $\dim(U_{2}\cap U_{3}^{\perp})\geq 1$ is handled similarly.

  Otherwise, we have $\dim(U_{1}\cap U_{2})\leq 2$ and $\dim(U_{1}\cap U_{3}^{\perp})=\dim(U_{2}\cap U_{3}^{\perp})=0$. This implies that

  	$\displaystyle\dim(U_{1}+U_{2})$	$\displaystyle=$	$\displaystyle\dim(U_{1})+\dim(U_{2})-\dim(U_{1}\cap U_{2})$
  		$\displaystyle\geq$	$\displaystyle\dim(U_{1})+\dim(U_{2})-2\geq\dim(U_{3})+3,$

  where for the last inequality we have used the assumption $\dim(U_{1})+\dim(U_{2})-\dim(U_{3})\geq 5$. It thus follows that

  	$\displaystyle\dim((U_{1}+U_{2})\cap U_{3}^{\perp})$	$\displaystyle=$	$\displaystyle\dim(U_{1}+U_{2})+\dim(U_{3}^{\perp})-\dim(U_{1}+U_{2}+U_{3}^{\perp})$
  		$\displaystyle\geq$	$\displaystyle\dim(U_{1}+U_{2})+(t-\dim(U_{3}))-t\geq 3.$

  Hence, there exist vectors $w_{1},w_{2},w_{3}\in U_{1}$ and $z_{1},z_{2},z_{3}\in U_{2}$ for which the three sums

  $$w_{1}+z_{1},~{}w_{2}+z_{2},~{}w_{3}+z_{3}$$

  are linearly independent vectors that belong to $U_{3}^{\perp}$. By Lemma 3.1, there exist $\alpha_{1},\alpha_{2},\alpha_{3}\in\mathbb{F}$, not all zeros, such that the vectors $x_{1}=\sum_{i\in[3]}{\alpha_{i}\cdot w_{i}}$ and $x_{2}=\sum_{i\in[3]}{\alpha_{i}\cdot z_{i}}$ satisfy $\langle x_{1},x_{2}\rangle=0$. These vectors further satisfy that

  $$x_{1}+x_{2}=\sum_{i\in[3]}{\alpha_{i}\cdot(w_{i}+z_{i})}\in U_{3}^{\perp}.$$

  It follows that $x_{1}+x_{2}$ is nonzero, because the vectors $w_{i}+z_{i}$ are linearly independent. Observe that $x_{1}$ belongs to $U_{1}$ and that it is nonzero, because otherwise the vector $x_{2}$ would be a nonzero vector that belongs to $U_{2}\cap U_{3}^{\perp}$, in contradiction to $\dim(U_{2}\cap U_{3}^{\perp})=0$. By the same reasoning, $x_{2}$ is a nonzero vector of $U_{2}$. Finally, notice that for every vector $u\in U_{3}$ such that $\langle u,x_{1}\rangle=0$, it also holds that $\langle u,x_{2}\rangle=0$, and thus

  $$\dim(U_{3}\cap(x_{1})^{\perp}\cap(x_{2})^{\perp})=\dim(U_{3}\cap(x_{1})^{\perp})\geq\dim(U_{3})-1,$$

  so we are done.  

We are ready to prove the following result, which implies Theorem 1.3.

• Proof:

  For an integer $k\geq 1$ and a finite field $\mathbb{F}$, consider the complete graph $K_{n}$ on $n=k^{2}+2k+3$ vertices. Let $V=A\cup B\cup C$ be the vertex set of the graph, where $A=\{v_{1},\ldots,v_{k}\}$ is a set of $k$ vertices, $B$ is a set of $k^{2}+k$ vertices, and $C$ consists of the three remaining vertices. To prove that $\mathop{\mathrm{ch\text{-}s}}(K_{n},\mathbb{F})\leq n-k$, suppose that for some integer $t$, we are given a subspace $U_{v}\subseteq\mathbb{F}^{t}$ with $\dim(U_{v})=n-k$ for every $v\in V$. Our goal is to show that there exist pairwise orthogonal nonzero vectors $x_{v}\in U_{v}$ for $v\in V$. We describe now a process with several steps for choosing the vectors. Throughout the process we maintain for every vertex $v\in V$ a subspace $U^{\prime}_{v}$ defined as the subspace of the vectors currently available to the vertex $v$. Namely, for every partial choice of vectors, $U^{\prime}_{v}$ is the subspace of $U_{v}$ that consists of all the vectors of $U_{v}$ that are orthogonal to all the previously chosen vectors. Initially, we have $U^{\prime}_{v}=U_{v}$ for every $v\in V$.

  Consider some partition of the set $B$ into $k$ sets, $B=B_{1}\cup\cdots\cup B_{k}$, where $|B_{i}|=2\cdot(k-i+1)$ for every $i\in[k]$. Note that this is possible, because $|B|=k^{2}+k=2\cdot\sum_{i=1}^{k}({k-i+1)}$. Our process starts with $k$ initial steps, where the role of the $i$th step ($i\in[k]$) is to choose vectors for the vertices of $B_{i}$ in a way that poses only $k-i+1$ linear constraints on the choice of the vector for $v_{i}$. Note that for the other vertices, the choice of the vectors for the vertices of $B_{i}$ might pose twice this number of linear constraints.

  For $i\in[k]$, the $i$th step is performed as follows. Consider an arbitrary partition of the set $B_{i}$ into $k-i+1$ pairs, denoted by $(a_{1},b_{1}),\ldots,(a_{k-i+1},b_{k-i+1})$. For every $j\in[k-i+1]$, we choose two nonzero vectors $u_{a_{j}}\in U^{\prime}_{a_{j}}$ and $u_{b_{j}}\in U^{\prime}_{b_{j}}$ such that $\langle u_{a_{j}},u_{b_{j}}\rangle=0$ and

  $$\dim(U^{\prime}_{v_{i}}\cap(u_{a_{j}})^{\perp}\cap(u_{b_{j}})^{\perp})\geq\dim(U^{\prime}_{v_{i}})-1.$$

  Observe that such a choice, if it exists, satisfies that $u_{a_{j}}$ and $u_{b_{j}}$ are nonzero vectors that belong to the subspaces of the vertices $a_{j}$ and $b_{j}$ respectively, they are orthogonal to all the previously chosen vectors and to one another, and in addition, their choice reduces the dimension of $U^{\prime}_{v_{i}}$ by at most $1$. To prove the existence of such a choice we apply Lemma 3.2. The number of vectors chosen before the $(i,j)$ iteration is $\sum_{l=1}^{i-1}{|B_{l}|}+2(j-1)$, hence each of $\dim(U^{\prime}_{a_{j}})$ and $\dim(U^{\prime}_{b_{j}})$ is at least

  $$(n-k)-\sum_{l=1}^{i-1}{|B_{l}|}-2(j-1).$$

  Additionally, since the $2(j-1)$ already chosen vectors of the $i$th step reduce the dimension of $U^{\prime}_{v_{i}}$ by at most $j-1$, it can be assumed that

  $$\dim(U^{\prime}_{v_{i}})=(n-k)-\sum_{l=1}^{i-1}{|B_{l}|}-(j-1).$$

  It thus follows that in the $(i,j)$ iteration, it holds that

  	$\displaystyle\dim(U^{\prime}_{a_{j}})+\dim(U^{\prime}_{b_{j}})-\dim(U^{\prime}_{v_{i}})$	$\displaystyle\geq$	$\displaystyle(n-k)-\sum_{l=1}^{i-1}{|B_{l}|}-3(j-1)$
  		$\displaystyle=$	$\displaystyle\sum_{l=i}^{k}{|B_{l}|}+3-3(j-1)$
  		$\displaystyle=$	$\displaystyle(k-i+1)(k-i+2)-3j+6$
  		$\displaystyle\geq$	$\displaystyle(k-i+1)(k-i+2)-3(k-i+1)+6$
  		$\displaystyle\geq$	$\displaystyle(k-i+1)(k-i-1)+6=(k-i)^{2}+5\geq 5,$

  where for the first equality we use the fact that $n=|B|+k+3$, and for the second inequality we use the fact $j\leq k-i+1$. The above bound, which also implies that $\dim(U_{a_{j}})\geq 2$ and that $\dim(U_{b_{j}})\geq 2$, allows us to apply Lemma 3.2 and to obtain the required vectors $u_{a_{j}}$ and $u_{b_{j}}$.

  We next show that given the above choice for the vertices of $B$, one can choose vectors for the vertices of $A\cup C$ to obtain the required pairwise orthogonal vectors. First, for the three vertices of $C$, choose arbitrary pairwise orthogonal nonzero vectors from the currently available subspaces. This is indeed possible, because so far we chose $n-(k+3)$ vectors, so the dimension of the subspace available to each of them is at least $3$. The choice for the first one leaves the available subspaces of the other two with dimension at least $2$, and the choice of the second one leaves the available subspace of the third with dimension at least $1$, allowing us to choose its nonzero vector.

  Finally, we choose the vectors for the vertices of $A$. For each $i\in[k]$, among the $n-k$ vectors chosen so far, there are $k-i+1$ pairs of vectors whose choice reduced the dimension of $U^{\prime}_{v_{i}}$ by at most $1$. This implies that we currently have

  $$\dim(U^{\prime}_{v_{i}})\geq(n-k)-((n-k)-(k-i+1))=k-i+1.$$

  This allows us to go over the vertices $v_{k},v_{k-1},\ldots,v_{1}$, in this order, and to choose a nonzero vector from the subspace currently available to each of them, completing the proof.  

In this section we prove Proposition 1.9, which asserts that for every finite field $\mathbb{F}$ and for every graph $G$, $\mathop{\mathrm{ch\text{-}s}}(G,\mathbb{F})\leq 2$ if and only if $G$ contains no cycles.

• Proof of Proposition 1.9:

  If $G$ contains no cycles then it is $1$-degenerate, implying that it is $2$-subspace choosable over every field $\mathbb{F}$. To complete the proof, we fix some finite field $\mathbb{F}$ and turn to show that for every $\ell\geq 3$, the $\ell$-cycle $C_{\ell}$ satisfies $\mathop{\mathrm{ch\text{-}s}}(C_{\ell},\mathbb{F})>2$. We first prove it for $\ell=3$ and for $\ell=4$.

  • –

    For $\ell=3$, assign to the vertices of the cycle $C_{3}$ the subspaces of $\mathbb{F}^{3}$ defined by

    $$U_{1}=\mathop{\mathrm{span}}(e_{1},e_{2}),~{}~{}~{}U_{2}=\mathop{\mathrm{span}}(e_{1},e_{2}+e_{3}),\mbox{~{}~{}~{}and~{}~{}~{}}U_{3}=\mathop{\mathrm{span}}(e_{1}+\alpha\cdot e_{3},e_{2}),$$

    where $\alpha\in\mathbb{F}$ is some field element to be determined. We claim that for some $\alpha\in\mathbb{F}$ it is impossible to choose three pairwise orthogonal nonzero vectors $x_{i}\in U_{i}$ ($i\in[3]$). Indeed, it is easy to verify that $x_{1}$ cannot be chosen as a scalar multiple of $e_{1}$ nor of $e_{2}$. So assume without loss of generality that $x_{1}$ is proportional to $e_{1}+z\cdot e_{2}$ for some $z\neq 0$. If $x_{1}$ is orthogonal to $x_{2}$ and to $x_{3}$, then $x_{2}$ is proportional to $z\cdot e_{1}-e_{2}-e_{3}$ and $x_{3}$ is proportional to $z\cdot e_{1}+\alpha z\cdot e_{3}-e_{2}$. However, the inner product of the latter two is $z^{2}-\alpha\cdot z+1$, so it suffices to show that there exists $\alpha\in\mathbb{F}$ for which this quadratic polynomial has no root. Notice that in case that $z^{2}-\alpha\cdot z+1$ has a root, it can be written as $(z-\gamma)\cdot(z-\gamma^{-1})$ for some $\gamma\neq 0$. Since the number of possible values of $\alpha$ is larger than the number of possible invertible values of $\gamma$, it follows that the required $\alpha$ exists.

  • –

    For $\ell=4$, suppose first that the field $\mathbb{F}$ is of characteristic larger than $2$, and assign to the vertices along the cycle $C_{4}$ the subspaces of $\mathbb{F}^{4}$ defined by

    $$U_{1}=U_{2}=\mathop{\mathrm{span}}(e_{1},e_{2}),~{}~{}~{}U_{3}=\mathop{\mathrm{span}}(e_{1}+e_{4},e_{2}+e_{3}),\mbox{~{}~{}~{}and~{}~{}~{}}U_{4}=\mathop{\mathrm{span}}(e_{1}+\alpha\cdot e_{3},e_{2}+e_{4}),$$

    where $\alpha\in\mathbb{F}$ is some nonzero field element to be determined. We claim that for some $\alpha\neq 0$ it is impossible to choose four nonzero vectors $x_{i}\in U_{i}$ ($i\in[4]$) that form a valid choice for $C_{4}$. By $\alpha\neq 0$, it is easy to verify, as before, that $x_{1}$ cannot be chosen as a scalar multiple of $e_{1}$ nor of $e_{2}$, so it can be assumed that it is proportional to $e_{1}+z\cdot e_{2}$ for some $z\neq 0$. If the vectors $x_{i}$ form a valid choice for $C_{4}$, then $x_{2}$ is proportional to $z\cdot e_{1}-e_{2}$, thus $x_{3}$ is proportional to $e_{1}+e_{4}+z\cdot e_{2}+z\cdot e_{3}$, and $x_{4}$ is proportional to $z\cdot e_{1}+\alpha z\cdot e_{3}-e_{2}-e_{4}$. However, the inner product of the latter two is $\alpha\cdot z^{2}-1$, so it suffices to show that there exists $\alpha\neq 0$ for which $\alpha\cdot z^{2}\neq 1$ for all values of $z$. Since $\mathbb{F}$ is of characteristic larger than $2$, it has a non-square element, whose choice for $\alpha$ completes the argument.

    If, however, $\mathbb{F}$ is of characteristic $2$, one can consider the subspaces of $\mathbb{F}^{5}$ defined by $U_{1}=U_{2}=\mathop{\mathrm{span}}(e_{1},e_{2})$, $U_{3}=\mathop{\mathrm{span}}(e_{1}+e_{4},e_{2}+e_{3}+e_{5})$, $U_{4}=\mathop{\mathrm{span}}(e_{1}+e_{3},e_{2}+\alpha\cdot e_{4}+e_{5})$, where $\alpha\in\mathbb{F}$ is some nonzero field element for which $z^{2}+z\neq\alpha$ for all values of $z$. Notice that such an $\alpha$ exists because the function $z\mapsto z^{2}+z$ maps both $0$ and $1$ to $0$, so some nonzero element does not belong to its image. It can be verified that for the above subspace assignment, no valid choice of vectors for $C_{4}$ exists.

  Finally, observe that for every odd $\ell>3$, one can extend the above subspace assignment for $C_{3}$ by adding $\ell-3$ copies of the subspace $\mathop{\mathrm{span}}(e_{1},e_{2})$ between $U_{1}$ and $U_{2}$ to get a subspace assignment showing that $\mathop{\mathrm{ch\text{-}s}}(C_{\ell},\mathbb{F})>2$. Similarly, for every even $\ell>4$, one can extend the above subspace assignment for $C_{4}$ by adding $\ell-4$ copies of the subspace $\mathop{\mathrm{span}}(e_{1},e_{2})$ between $U_{1}$ and $U_{2}$.