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


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. 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$).

  • $\begingroup$ Thank you Timothy Chow. As I told you in my latest email, I know how to prove it now. I am just not sure whether to try to publish it first as a small note somewhere, and then link to it from here, or just post the solution here. $\endgroup$ – Malkoun Mar 24 '18 at 21:37
  • $\begingroup$ I have just uploaded it onto arxiv, as well as submitted it to a journal. I will link to the arXiv version tomorrow. $\endgroup$ – Malkoun Mar 26 '18 at 12:53
  • 1
    $\begingroup$ My preprint can be found at arxiv.org/abs/1803.09554. The solution follows from a formula by Svrtan. $\endgroup$ – Malkoun Mar 28 '18 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.