Median orders are great tools for dealing with a-priori unknown orientations of edges in tournaments, because they provide us with local properties on oriented edge density.
I've been wondering if given $\varepsilon>0$, and a tournament $T=(V,E)$ with $n$ vertices, is it true that if $\sigma:V\to \{1,..,n\}$ is a median order of $T$, and $X\subseteq V$ with $|X|= \varepsilon n$ restricting a median order $\sigma$ to $\sigma|_{V-X}$ yields a 'good enough' ordering, this means an order that is close in some sense to a median order of the induced sub-tournament $T[V-X]$.
Here $\sigma|_{V-X}:V-X\to \{1,...,(1-\varepsilon)n\}$ is the ordering that satisfies $\sigma(v)<\sigma(w) \iff \sigma|_{V-X}(v) < \sigma|_{V-X}(w)$, for all $v,w \in V-X$.
More precisely, for a tournament $T=(V,E)$ and vertex orderings $\sigma, \mu : V \to \{1,...,n\}$, we can define the following metrics:
$d_\infty(\sigma,\mu) := \max\limits_{v \in V} |\sigma(v)- \mu(v)|$,
$d_1(\sigma,\mu):= \frac{1}{|V|}\cdot \sum\limits_{v\in V} |\sigma (v)-\mu(v)|$,
This is not a metric, but if we define the ratio $r(\sigma)$ of increasing edges of an order $\sigma$ as $r(\sigma):= \frac{1}{|E|}|\{e=(e_1,e_2) \in E: \sigma(e_1) < \sigma (e_2)\}|$, we can then define $$d_{r}(\sigma,\mu):=\left|r(\sigma)-r(\mu)\right|.$$
Statement: The question is, can we bound $\min\limits_{\nu \text{ is a median order}\\ \hspace{4mm}\text{ of }T[V-X]} d(\sigma|_{V-X},\nu)$ in terms of some function of $\varepsilon$, $n$ and $\sigma$, for some choice of $d$ defined in 1, 2 and 3?
Further comments:
- Something that is easy to compute by comparing the set of increasing edges of $T[V-X]$ under $\sigma|_{V-X}$ with that of $T$ and $\sigma$ is that $\frac{1}{(1-\varepsilon)^{2}}(r(\sigma)-(3\varepsilon^{2}-2\varepsilon))≤r(\sigma|_{V-X})$. Note that this is a comparison between orders of different tournaments (and of different sizes!), but yields a lower bound on the increasing edge density of the restricted order. This also implies a lower bound on the ratio $r(\nu)$ for each median order $\nu$ of $T[V-X]$ ( as $\sigma|_{V-X}$ is indeed an order of $V-X$). How much bigger can then $r(\nu)$ be?
