# A combinatorial question on complete graphs and polynomials

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}$?

Your problem bears a family resemblance to Rota's Basis 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$).