Questions about interlacing polynomials

Question

• If we have a finite set of real-rooted polynomials of the same degree such that any two of them have a common interlacing then does it imply that this set has a common interlacer?

• Lemma $4.2$ (top of page 7) in this paper, https://arxiv.org/pdf/1304.4132.pdf says that if a finite set of polynomials of the same degree with positive leading coefficients have a common interlacing then one of these polynomials must have its largest root less than or equal to the largest root of of the sum of them. (..this is known that here one can replace the sum by any positive linear combination of the polynomials as in Lemma 24.3.1 here, http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf..)

  Now does this lemma still hold if the assumption is only that the polynomials are pairwise common interlacing? (assuming that "no" is the answer to my first question!)

---

Defining "interlacing" : If $g = \prod_{i=1}^n (x-\alpha_i)$ and $f=\prod_{i=1}^n (x-\beta_i)$ are two degree $n$ real-rooted polynomials then we say that ``$g$ interlaces $f$" if $\beta_1 \leq \alpha_1 \leq \beta_2 \leq \alpha_2 .. \leq \beta_n \leq \alpha_n$.

Defining : "common interlacing". Given $\{f_1,f_2,..,f_k\}$ as set of degree $n$ real-rooted polynomials we say that they have a common interlacing $g$ (another degree $n$ real-rooted polynomial) if $g$ interlaces each $f_i$.

Answer 1

The answer to the first question is yes. If $f$ has roots $\alpha_1, \ldots, \alpha_n$ and $g$ has roots $\beta_1, \ldots, \beta_n$, then $f$ and $g$ have a common interlacing if and only if for all $1 \leq i < n$ the intervals $[\alpha_i, \alpha_{i+1}]$ and $[\beta_i, \beta_{i+1}]$ intersect. But if this is true for any pair of polynomials in some family, then for each $i$ the intervals from the $i$th to the $(i+1)$st roots must all have a common intersection, by the trivial 1-dimensional case of Helly's theorem. So there is a common interlacing.

Answer 2

It has nothing essential to do with polynomials. Just sets of numbers.

Let $\beta_{11} \lt \beta_{21} \lt \cdots \beta_{n1}$ and $\beta_{12} \lt \beta_{22} \lt \cdots \beta_{n2}$ be two lists. They have a common interlacing exactly if $\beta_{i1} \lt \beta_{(i+1)2}$ and $\beta_{i2} \lt \beta_{(i+1)1}$ for all $1 \leq i \lt n.$

So given $k$ sets $\beta_{1j} \lt \beta_{2j} \lt \cdots \beta_{nj},$ there is an common interlacing for each pair exactly if $\beta_{ij} \lt \beta_{(i+1)j'}$ for all $1 \leq i \lt n$ and $1 \leq j \lt j' \leq k. $ Then a particular sequence that interlaces all $k$ sets is $\alpha_{i}=\frac{\max\beta_{ij}+\min\beta_{(i+1)j}}2$ for $1\leq i\lt n$ and $\alpha_n=\max \beta_{nj}+1.$