| 要約: | <p>We begin by studying the possible intersection sizes of a $k$-dimensional linear subspace with the hypercube $\{0,1\}^n$. For a fixed $k$, the largest intersection size is $2^k$ and it was shown by Melo and Winter that the second largest intersection size is $2^{k-1} + 2^{k-2}$. We show that all intersections sizes larger than $2^{k-1}$ are of the form $2^{k-1} + 2^{i}$ or $35 \cdot 2^{k-6}$, completely determining the ``large'' intersection sizes and disproving a conjecture of Melo and Winter. We also show that the only possible intersection size in the interval $( 15 \cdot 2^{k-5}, 2^{k-1} )$ is $63 \cdot 2^{k-7}$, disproving a second conjecture of Melo and Winter that all of the ``small'' values are present.</p>
<p>Next we consider Lipschitz bijections between functions from $\{0,1\}^n$ to $\{0,1\}^n$ and consider how much these bijections must ``stretch'' the edges of the hypercube. We answer four questions posed by Rao and Shinkar.<br>
1. We show that there is no $O(1)$-bi-Lipschitz bijection from $\mathrm{Dictator}$ to $\mathrm{XOR}$ such that each output bit depends on $O(1)$-input bits.<br>
2. We give a construction for a mapping from $ \mathrm{XOR}$ to $ \mathrm{Majority}$ which has average stretch $O(\sqrt{n})$, matching a previously known lower bound.<br>
3. We give a $3$-Lipschitz embedding $\phi : \{0,1\}^n \to \{0,1\}^{2n+1}$ such that $ \mathrm{XOR}(x) = \mathrm{Majority}(\phi(x))$ for all $x \in \{0,1\}^n$.<br>
4. We show that with high probability there is a $O(1)$-bi-Lipschitz mapping from $\mathrm{Dictator}$ to a uniformly random balanced function.</p><br>
<p>Moving from (hyper)cubes to squares, we consider a problem about zero-sum squares in $\{-1,1\}$-matrices. Given a matrix $M = (a_{i,j})$ a {square} is a $2 \times 2$ submatrix with entries $a_{i,j}$, $a_{i, j+s}$, $a_{i+s, j}$, $a_{i+s, j +s}$ for some $s \geq 1$, and a {zero-sum square} is a square where the entries sum to $0$. Recently, Ar\'evalo, Montejano and Rold\'an-Pensado proved that all large $n \times n$ $\{-1,1\}$-matrices with discrepancy $|\sum a_{i,j}| \leq n$ contain a zero-sum square unless they are split, and conjectured that this can be improved to $Cn$ for large enough $n$. We show that a quadratic bound holds: all large $n \times n$ $\{-1,1\}$-matrices with discrepancy at most $n^2/4$ are either split or contain a zero-sum square.</p>
<p>We next consider another problem regarding squares, but this time squares in permutations. A square in a permutation is a factor $S = (S_1; S_2)$ where $S_1$ and $S_2$ have the same pattern, and a permutation is said to be square-free if it contains no non-trivial squares. The permutation is further said to be bicrucial with respect to squares if every extension to both the left and right contains a square. We completely classify for which $n$ there exists a bicrucial square-free permutation, confirming two conjectures of Gent, Kitaev, Konovalov, Linton and Nightingale.</p>
<p>Two permutations $\sigma$ and $\pi$ are said to be $\ell$-similar if they can be partitioned into subpermutations $\sigma^{(1)}, \dots, \sigma^{(\ell)}$ and $\pi^{(1)}, \dots, \pi^{(\ell)}$ respectively such that $\sigma^{(i)}$ and $\pi^{(i)}$ have the same pattern for all $i \in [\ell]$. Clearly, two permutations may only be $n$-similar, but what happens in the ``average'' case? It is easy to get an upper bound of $O(n^{1/2})$ using the Erd\H{o}s-Szekeres Theorem, and a lower bound of $\Omega(n^{1/3})$ follows from the length of the longest twin in a random permutation. We prove that two independent uniformly random permutations are $O\big(n^{1/3}\log^{11/6}(n)\big)$-similar with high probability, matching the lower bound up to a polylogarithmic factor.</p>
<p>Finally, we consider creating uniformly random permutations using sequences of independent lazy transpositions and ask how long such a sequence must be. We give an improved construction which uses $(2/3)\binom{n}{2}+O(n\log(n))$ lazy transpositions, giving a negative answer to a problem of Angel and Holroyd. The best-known lower bound of $\Omega(n\log(n))$ is based on the number of transpositions needed to ``reach'' each configuration with positive probability. We introduce similar reachability questions for smaller subsets and settle the case of subsets of size 2 exactly: the smallest sequence of transpositions such that each pair of distinct positions $(x,y)$ has a subsequence mapping $(1,2)$ to $(x,y)$ has length $\lceil 3n/2\rceil-2 $. We also consider the case where all transpositions are of the form $(1, \cdot)$ and use the structure in this case to provide the first separation between uniformity and reachability.</p>
|
|---|