Let me state two problems that look very much alike. The first one can be solved putting together answers that different people have given to some questions I asked here a few weeks ago. The second one, somewhat frustratingly, does not seem to be easily solvable in the same way - or perhaps I just don't know enough linear algebra (or what have you)! Perhaps the solution to the second problem will be obvious to some people here, especially once I sketch the solution to the first one.
(It should be clear that both problems are toy cases of a more general problem I am considering.)
Problem 1. Consider a word $w$ of length $2 n$ involving each of the letters $x_1,\dotsc,x_n,x_1^{-1},\dots x_n^{-1}$ exactly once. Define an $n$-by-$n$ matrix $A(w) = A_+ - A_-$, where $A_+ = (a_{+,i,j})_{1\leq i,j\leq n}$ is defined by $$a_{+,i,j} = \begin{cases} 1 &\text{if $x_j$ occurs between $x_i$ and $x_i^{-1}$,}\\ -1 &\text{if $x_j$ occurs between $x_i^{-1}$ and $x_i$,}\\ 0 &\text{otherwise.}\end{cases}$$ and $A_{-} = (a_{-,i,j})_{1\leq i,j\leq n}$ is defined in exactly the same way, only with $x_j^{-1}$ instead of $x_j$.
Define $r(w)$ to be the largest integer $r$ such that there is an $r$-by-$r$ non-singular minor of $A(w)$ such that its set $I\subset \{1,\dotsc,n\}$ of row indices and its set $J\subset \{1,\dotsc,n\}$ of column indices are disjoint.
Show that $r(w)$ is small compared to $n$ for relatively few words $w$.
("Relatively few" here means "not much more than $C^n$ for some large constant $C$", whereas $n!^{0.1}$ would be "many".)
Solution.- The matrix $A(w)$ is skew-symmetric. By the solution to the post Permutations, skew-symmetric forms and degeneracy, the rank of $A(w)$ equals $2 g$, where $g$ is the genus $g$ of a certain surface described in the post.
Let $\sigma \in \text{Sym}(2n)$ be the product of the transpositions $(r_i\, r_i')$, where $1\leq r_i,r_i'\leq 2 n$ are the places in $w$ where $x_i$ and $x_i^{-1}$ (respectively) appear. Let $\tau$ be the cycle $(1\, 2\, \dotsc \, 2 n)$. Then (by Euler's formula) $g = (1+n-b)/2$, where $b$ is the number of cycles in $\sigma \tau$. Thus, the rank of $A(w)$ is $n + 1 - b$.
It seems relatively straightforward to show that $b$ is small compared to $n$ for most words $w$. In fact, a closed expression can be found in https://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF01390325/fulltext.pdf , and the fact that $b$ is small for all but relatively few $w$ follows immediately.
By the answer to Does an antisymmetric matrix with high rank have a minor with disjoint rows and columns and high rank?, $r(w)$ is at least half the rank of $A(w)$. So we are done.
Problem 2.- Consider words $w$ involving each of the letters $x_1,\dotsc,x_n$ exactly twice. Define an $n$-by-$n$ matrix $A'(w) = (a'_{i,j})_{1\leq i,j\leq n}$, where $a'_{i,j}$ (for $i\ne j$) is the number of times $x_j$ appears between the two occurences of $x_i$, and $a'_{i,i}=0$. Define $r'(w)$ in terms of $A'(w)$ exactly as we defined $r(w)$ in terms of $A(w)$.
Show that $r'(w)$ is small compared to $n$ for relatively few words $w$.
Failed attempt at a solution.- We can define the same surface as before. The topological argument seems to work nicely even over $\mathbb{Z}/2\mathbb{Z}$. The rank of $A'(w)$ over $\mathbb{Z}$ is at least its rank over $\mathbb{Z}/2\mathbb{Z}$, which equals the rank of $A(w)$ over $\mathbb{Z}/2\mathbb{Z}$, which is, in turn, equal to $n+1-b$. We already know that $b$ is usually small.
The problem comes in applying the argument in the post Does an antisymmetric matrix with high rank have a minor with disjoint rows and columns and high rank? . Since $A'(w)$ is not antisymmetric, we cannot conclude that it has a minor with disjoint row and column indices and rank at least $(n+1-b)/2$. (And no, that argument doesn't work over $\mathbb{Z}/2\mathbb{Z}$.) Or am I missing something?
Perhaps Problem 2 is not that hard? Perhaps there is a proof that works for both problems?
