Seventeenth ROMANIAN MASTER OF MATHEMATICS

First solution. First we provide a proof that $k\ge n-1$. Let $T$ be the path where $v_i$ and $v_{i+1}$ are adjacent for all $1\le i\le n-1$. Let $\omega$ be a primitive root of unity of order $n$ and let $a_i={\omega }^i$ for all $1\le i\le n$. If $f(X)=P(X,\omega X)$, then for all $1\le i\le n-1$ we have $f({\omega }^i)=P(a_i,a_{i+1})=0$. Since $f(1)=P(a_n,a_1)\ne 0$, $f$ is non-zero and has at least $n-1$ roots. This means that $\mathrm{deg}P\ge \mathrm{deg}f\ge n-1$, proving $k\ge n-1$.

It remains to prove that $k=n-1$ is sufficient i.e. for any tree $T$ and any $a_1,a_2,\dots ,a_n$ we can find a polynomial $P$ of degree at most $n-1$. For brevity, we call a two-variable polynomial $A(X,Y)$ symmetric if $A(X,Y)=A(Y,X)$. We begin with the following observation. Suppose that $A$ and $B$ are two variable polynomials of degree at most $d$. Then we can find $\alpha \in \mathbb{C}$ such that for any $1\le i,j\le n$, $A(a_i,a_j)+\alpha B(a_i,a_j)=0$ if and only if $A(a_i,a_j)=B(a_i,a_j)=0$. This means that we can "merge" two conditions of degree at most $d$ into a condition of degree at most $d$ (note that this produces a symmetric polynomial if the initial polynomials are symmetric). For any integer $t\ge 2$, let a star of size $t$ be a collection of $t$ edges for which there is a vertex which belongs to all edges. We will prove the following claims.

Claim 1. Let $G$ be a graph with vertices $v_1,v_2,\dots ,v_n$ and $E$ edges. Suppose that we can partition the edges of $G$ into a number of stars. Then for any distinct complex numbers $a_1,a_2,\dots ,a_n$ we can find a symmetric polynomial $P$ of degree at most $E$ such that for all $1\le i,j\le n,i\ne j$, $P(a_i,a_j)=0$ if and only if there is an edge between $v_i$ and $v_j$ in $G$. Proof. We will first prove the claim when $G$ consists of a star of size $E\le n-1$ and some isolated vertices. Without loss of generality, let $v_1{v}_2,v_1{v}_3,\dots ,v_1{v}_{E+1}$ be the edges of $G$. Also let $s_1=a_1+a_2,s_2=a_1+a_3,\dots ,s_E=a_1+a_{E+1}$. Consider merging the polynomials $(X-a_1)(Y-a_1)$ and $(X+Y-s_1)(X+Y-s_2)\dots (X+Y-s_E)$ into a polynomial of degree at most $E$ (which is of course symmetric). They both vanish at a pair $a_i,a_j$ if and only if $1\in \{i,j\}$ and $a_i+a_j\in \{s_1,s_2,\dots ,s_E\}$. These two happen if and only if $v_i$ and $v_j$ are adjacent, so this produces a valid polynomial. For the general case, let $S_1\cup S_2\cup \cdots \cup S_k$ be the partition of the edges of $G$. For each $1\le i\le k$, we can find a two variable polynomial $P_i$ of degree at most $|S_i|$ which vanishes only at the edges of $S_i$. Then we can let $P=P_1{P}_2\dots P_k$, which satisfies the claim as $\mathrm{deg}P\le |S_1|+|S_2|+\cdots +|S_k|=E$, as desired.

Claim 2. Any tree $\Gamma$ with odd number of vertices can be partitioned into stars of size 2. Proof. We prove this by induction on the number of the vertices of $\Gamma$. The base case is clear, since $\Gamma$ is a star of size 2 when $\Gamma$ has three vertices. For the inductive step, let $\Gamma$ be a tree with $2m+1$ vertices, where $m\ge 2$. Let $u_1{u}_2\dots u_t$ be a path of maximal length in $\Gamma$ (of course, $t\ge 3$). Then any neighbour of $u_2$ except for maybe $u_3$ must have degree 1, otherwise we can delete $u_1$ and insert two edges, contradicting the maximality of $t$. If $\mathrm{deg}{u}_2=2$, we can form the star $u_1{u}_2,u_2{u}_3$ and apply the inductive hypothesis on $\Gamma \setminus \{u_1,u_2\}$. If $\mathrm{deg}{u}_2\ge 3$, let $u\ne u_1,u_3$ be a neighbour of $u_2$. Then create the star $u_1{u}_2,u{u}_2$ and apply the inductive hypothesis on $\Gamma \setminus \{u,u_1\}$. This proves the claim.

The case where $n$ is odd becomes trivial, since $T$ has $n-1$ edges. Assume that $n$ is even. Without loss of generality, let $\mathrm{deg}{v}_n=1$ and let $v_n$ be adjacent to $v_{n-1}$. Consider the graph $T^{\prime }$ formed by deleting the edge $v_{n-1}{v}_n$ from $T$ (but not permuting the $n$ vertices). Clearly, $T^{\prime }$ consists of $v_n$ and a tree on $v_1,v_2,\dots ,v_{n-1}$. As $n-1$ is odd, the edges of $T^{\prime }$ can be partitioned into stars of size 2 from Claim 2. From Claim 1 it follows that there is a symmetric polynomial $Q(X,Y)$ of degree at most $n-2$ such that $Q(a_i,a_j)=0$ if and only if $i,j\le n-1$ and $v_i,v_j$ are adjacent in $T$. Let $g(X)$ be the polynomial of degree $n-1$ such that $g(a_1)=g(a_2)=\cdots =g(a_{n-1})=0$ and $g(a_n)=-Q(a_{n-1},a_n)=-Q(a_n,a_{n-1})$. Let $P$ be the polynomial of degree at most $n-1$ obtained by merging $F_1(X,Y)=Q(X,Y)+g(X)+g(Y)$ and $F_2(X,Y)=Q(X,Y)(X+Y-s)$, where $s=a_n+a_{n-1}$. It is easy to see that $P$ vanishes at each $(a_i,a_j)$ for which $v_i,v_j$ are adjacent in $T$. Suppose that $v_i$ and $v_j$ are not adjacent in $T$. If $i,j\le n-1$, then $F_1(a_i,a_j)=Q(a_i,a_j)\ne 0$. If $n\in \{i,j\}$, then $a_i+a_j\ne s$ and $Q(a_i,a_j)\ne 0$, so $F_2(a_i,a_j)\ne 0$. Hence $P(a_i,a_j)\ne 0$. This proves that $P$ satisfies the required conditions, as desired.

---

Alternative solution.

Second solution. Establish the lower bound as in Solution 1. We now address the upper bound differently. Let $G$ be a graph on vertices $v_1,\dots ,v_n$. Say that a polynomial $P(X,Y)$ is $G$-good if it satisfies the conditions in the statement of the problem. We prove the more general fact below:

Claim. Let $d_i$ be the degree of $v_i$. Assume that these degrees satisfy $d_i\le n-i$ for all $i\le n-1$, and $d_n=1$. Then there is a $G$-admissible polynomial of degree at most $n-1$. Notice here that, if $G$ is a tree with vertices ordered so that $d_1\ge d_2\ge \cdots \ge d_n$, then it satisfies the conditions in the Claim. Indeed, we have $d_n=1$, and if $d_i>n-i$ for some $i\le n-1$, then we have $2n-2{\sum }_{j=1}^n{d}_j\ge {\sum }_{j=1}^i(n-i+1)+{\sum }_{j=i+1}^{n}1=i(n-i+1)+(n-i)=(i+1)(n-i+1)-1\ge 2n-1$, which is a contradiction. So, it suffices to prove the Claim.

Proof of the Claim. Let $$P(X,Y)=\sum _{j=0}^{n-1}{R}_j(Y)X^j$$ be the sought polynomial; set $R_{n-1}(X)=1$. Denote $$Q_i(X)=P(X,a_i)=X^{n-1}+\sum _{j=0}^{n-2}{q}_{ij}{X}^j,\text{where }{q}_{ij}=R_j(a_i).$$ So, we will seek for the sequences $C_j=(q_{1j},q_{2j},\dots ,q_{nj})$ such that there exists a polynomial $R_j$ with $\mathrm{deg}{R}_j\le n-j-1$ such that $q_{ij}=R_j(a_i)$. Notice that the first $n-j$ terms of such a sequence determine it uniquely; in particular, there are no restrictions on the sequence $C_0$. We know that the polynomial $Q_i$ has $d_i$ prescribed roots. For every $i\le n-1$, augment this list by some numbers not from the set $A=\{a_1,a_2,\dots ,a_n\}$ to the list $b_{i1},b_{i2},\dots ,b_{i,n-i}$. Also, denote by $b_{n1}$ the unique prescribed root of $Q_n$. Thus, we should have $$Q_i(X)=S_i(X)\prod _{j=1}^{\max (n-i,1)}(X-b_{ij}),(1)$$ where $S_i$ is a monic polynomial with $\mathrm{deg}{S}_i=i-1$ for $i\le n-1$ and $\mathrm{deg}{S}_n=n-2$. The only extra conditions we have are that each $S_i$ should achieve non-zero values at the prescribed finite subset $A_i$ of $A$ (containing no prescribed roots of $Q_i$). The polynomial $Q_1$ is uniquely determined by (1). Assume that the polynomials $Q_1,\dots ,Q_{i-1}$ have already been determined, for some $i\le n-2$. This means that the sequences $S_1,\dots ,S_{i-1}$ are also determined. This determines the polynomial $S_i$ up to the constant term. So we may choose this constant term so that $S_i$ has no prohibited roots, thus defining $Q_i$.

---

Alternative solution.

Third solution. The answer is $n-1$. Use the same argument as Solution 1 for the lower bound. We can construct such a polynomial via a method that uses no graph theory other than the fact that $T$ has $n-1$ edges.

Lemma 1. Let $k$ be a positive integer and let $A,B\subseteq {\mathbb{C}}^2$ be two disjoint finite sets. Suppose $|A|=2k$ and no line intersects $A\cup B$ in more than $k+1$ points. Then there exists a polynomial of degree $k$ that vanishes on $A$ and is non-zero on $B$. Proof. We first argue that we may reduce to the case when $|B|=1$. This is since if $P$ and $P^{\prime }$ are polynomials that are zero on $A$ and nonzero on $B$ and $B^{\prime }$, then a generic linear combination of $P$ and $P^{\prime }$ is nonzero on $A$ and nonzero on $B\cup B^{\prime }$. Now suppose $B=\{b\}$. For $a,a^{\prime }\in A$, write $a\sim a^{\prime }$ if $a,a^{\prime },b$ are collinear. This is an equivalence relation, and each equivalence class has at most $k$ elements. Thus we may pair up the elements of $A$ such that no two paired elements are collinear with $b$. Now let $P$ be the polynomial vanishing on the union of the $k$ lines determined by the pairs, which is nonzero at $b$ by construction.

Lemma 2. Let $a_1,a_2,\dots ,a_n$ be distinct complex numbers. Then a line can intersect at most $n$ points of the form $(a_i,a_j)$. Proof. If not, then by the pigeonhole principle such a line must contain two points with the same $x$-coordinate. But then it is vertical and thus can only contain $n$ points. We are done by applying Lemma 1 with $$A=\{(a_i,a_j):v_i{v}_j\in E(T)\}\text{and}B=\{(a_i,a_j):i\ne j,v_i{v}_j\notin E(T)\}.$$