Let $K\_n$ denote the complete graph on $n$ vertices. Let us denote the vertices simply by $1,\ldots,n$. Suppose that, for each edge $ij$, with $1\leq i<j \leq n$, we assign an ordered basis $(p^+\_{ij}, p^-\_{ij})$ of $\mathbb{C}^2$, where we think of the latter as the space of complex polynomials of degree less than or equal to $1$.


Here is the proposed problem. An admissible choice is, for each oriented edge $ij$, as above, a choice of either $p^+\_{ij}$ or $p^-\_{ij}$. We then assign to the edge $ji$ the "other" choice (if you chose $p^+$ for $ij$, you must assign $p^-$ to $ji$, and vice versa).


Once an admissible choice is made, one then forms, for each $i$, the polynomial $p\_i$, which is equal to the product of the chosen $p\_{ij}$'s, for $j$ running over all values in $\{1,\ldots,n\}$, with $j \neq i$. Thus each $p\_i$ is a polynomial of degree less than or equal to $n-1$.


Problem: given any initial assignment of ordered bases to the edges, does there always exist some admissible choice such that the corresponding polynomials $p\_1,\ldots,p\_n$ are linearly independent over $\mathbb{C}$?



A combinatorial question on complete graphs and polynomials
This is a nice question! Thanks for contacting me by email; I want to summarize here some of the email discussion that we've had.


Your problem bears a family resemblance to [Rota's Basis Conjecture](http://michaelnielsen.org/polymath1/index.php?title=Rota%27s_conjecture). The well-known connection between the Alon–Tarsi conjecture and Rota's Basis Conjecture suggests the following first step towards proving your conjecture. On each edge of your graph, you have two linear polynomials $a\_i x + b\_i$ and $c\_ix + d\_i$. Let
$$P := \prod\_i (a\_i d\_i - b\_i c\_i).$$
so that $P$ is a polynomial in $a\_i,b\_i,c\_i,d\_i$ of degree $n(n-1)$, and $P\ne 0$ if and only if $a\_i x + b\_i$ and $c\_i x + d\_i$ are linearly independent (which you stipulated that they must be). Now, you're asking that, for each edge, we make one of two possible choices; thus, there are $2^{n(n-1)/2}$ different choices we can make. For each choice, we get $n$ polynomials $p\_1, \ldots, p\_n$ in $x$, each of which has degree $n-1$ and whose coefficients are polynomials of degree $n-1$ in $a\_i,b\_i,c\_i,d\_i$. If we write down the $n\times n$ matrix of coefficients, then its determinant is a polynomial of degree $n(n-1)$ in $a\_i,b\_i,c\_i,d\_i$; let $S$ denote the set of $2^{n(n-1)/2}$ determinants that arise in this way.


We may conjecture that there is some (scalar) linear combination of the elements of $S$ that equals $K\_n P$ where $K\_n$ is some nonzero complex number. If we could prove this then your conjecture would follow, because $K\_nP \ne 0$ implies that some determinant in $S$ is nonzero.


In the case of Rota's Basis Conjecture, the analogue of $K\_n$ is the Alon–Tarsi constant, which is conjectured to be nonzero but whose non-vanishing has turned out to be notoriously hard to prove. With luck, in your problem, it won't be too hard to prove that $K\_n \ne 0$ (assuming of course that there is indeed some scalar linear combination of elements of $S$ that equals $K\_n P$).


