Abstract. Any [Formula: see text]-tuple of points in the plane can be moved to any other [Formula: see text]-tuple by a continuous motion with at most [Formula: see text] intermediate changes of the order type. Even for tuples with the same order type, the cubic bound is sharp: there exist pairs of [Formula: see text]-tuples of the same order type requiring [Formula: see text] intermediate changes. We show that the upper bound can be slightly improved if the order types of the two [Formula: see text]-tuples are either not too elongated, or are not mirror images of one another.

Abstract. We show that every convex code realizable by compact sets in the plane admits a realization consisting of polygons, and analogously every open convex code in the plane can be realized by interiors of polygons. We give factorial-type bounds on the number of vertices needed to form such realizations. Consequently we show that there is an algorithm to decide whether a convex code admits a closed or open realization in the plane.

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. •Panchromatic Graphs: For fixed$k\in \mathbb{N}$, a$k$-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into$k$colour classes in which the common neighbourhoods of panchromatic$k$-sets of vertices are much larger than those of$k$-sets that repeat a colour. The question of their existence was raised by Karthik and Manurangsi [Combinatorica 2020]. •Threshold Graphs: For fixed$k\in \mathbb{N}$, a$k$-threshold graph is, roughly speaking, a balanced bipartite graph in which the common neighbourhoods of$k$-sets of vertices on one side are much larger than those of ($k+1$)-sets. The question of their existence was raised by Lin [JACM 2018]. Concretely, we provide probability distributions over graphs from which we can efficiently sample these objects in near linear time. These probability distributions are defined via varieties cut out by (carefully chosen) random polynomials, and the analysis of these constructions relies on machinery from algebraic geometry (such as the Lang-Weil estimate, for example). The technical tools developed to accomplish this might be of independent interest. As applications of our constructions, we show the following conditional time lower bounds on the parameterized set intersection problem where, given a collection of$n$sets over universe [$n$] and a parameter$k$, the goal is to find$k$sets with the largest intersection. •Assuming ETH, for any computable function$F:\mathbb{N}\rightarrow \mathbb{N}$, no$n^{o(k)}$-time algorithm can approximate the parameterized set intersection problem up to factor$F(k)$. This improves considerably on the previously best-known result under ETH due to Lin [JACM 2018], who ruled out any$n^{o(\sqrt{k})}$time approximation algorithm for this problem. •Assuming SETH, for every$\varepsilon > 0$and any computable function$F:\mathbb{N} \rightarrow \mathbb{N}$, no$n^{k-\varepsilon}$-time algorithm can approximate the parameterized set intersection problem up to factor$F(k)$. No result of comparable strength was previously known under SETH, even for solving this problem exactly. Both these time lower bounds are obtained by composing panchromatic graphs with instances of the coloured variant of the parameterized set intersection problem (for which tight lower bounds were previously known).

Given two random finite sequences from $[k]^n$ such that a prefix of the first sequence is a suffix of the second, we examine the length of their longest common subsequence (LCS). If $\ell$ is the length of the overlap, we prove that the expected length of an LCS is approximately $\max(\ell, {E}[L_n])$, where $L_n$ is the length of an LCS between two independent random sequences. We also obtain tail bounds on this quantity.

Let $a_1,\ldots,a_n$ be a permutation of $[n]$. Two disjoint order-isomorphic subsequences are called twins. We show that every permutation of $[n]$ contains twins of length $\Omega(n^{3/5})$ improving the trivial bound of $\Omega(n^{1/2})$. We also show that a random permutation contains twins of length $\Omega(n^{2/3})$, which is sharp.

We study how a single value of the shatter function of a set system restricts its asymptotic growth. Along the way, we refute a conjecture of Bondy and Hajnal which generalizes Sauer's lemma.

We consider list decoding in the zero-rate regime for two cases-the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ∈ [0, 1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by L or more of them. As M → ∞ the maximal τ decreases to a well-known critical value τL. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ(M-1) when L is even, thus extending the classical results of Plotkin and Levenshtein for L = 2. For L = 3, the rate is shown to be Θ(M-(2/3)). For the similar question about spherical codes, we prove the rate is Ω(M-1) and O(M-(2L/L(2)-L+2)).

In this paper, we present a fractional version of Haemers' bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers' bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers' bound. We show also that this bound is multiplicative, unlike Haemers' bound.

We consider incidences among colored sets of lines in $\mathbb{R}^d$ and examine whether the existence of certain concurrences between lines of $k$ colors force the existence of at least one concurrence between lines of $k+1$ colors. This question is relevant for problems in 3D reconstruction in computer vision.

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed k ≥ 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/3. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 – ⊝(1/k), since 1 – 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between 1/3 and 1/2 for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.

An $L$-spherical code is a set of Euclidean unit vectors whose pairwise inner products belong to the set $L$. We show, for a fixed $0<\alpha,\beta<1$, that the size of any $[-1,-\beta]\cup\{\alpha\}$-spherical code is at most linear in the dimension. In particular, this bound applies to sets of lines such that every two are at a fixed angle to each another.

Given a set of $t\ge k+2$ words of length $n$ over a $k$-letter alphabet, it is proved that there exists a common subsequence among two of them of length at least $\frac{n}{k}+cn^{1-1/(t-k-2)}$ for some $c>0$ depending on $k$ and $t$. This is sharp up to the value of $c$.

We present a generalization of a version of the Kruskal–Katona theorem due to Lovász. A shadow of a d-tuple $(S_1,\dots,S_d)\in\binom{X}{r}^d$ consists of d-tuples $(S_1',\dots,S_d')\in\binom{X}{r-1}^d$ obtained by removing one element from each of the $S_i$. We show that if a family $\mathcal{F}\subset\binom{X}{r}^d$ has size $|\mathcal{F}|=\binom{x}{r}^d$ for a real number $x\geq r$, then the shadow of $\mathcal{F}$ has size at least $\binom{x}{r-1}^d$.

We define the crossing number for an embedding of a graph G into R3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give the sharp bounds on the space crossing numbers of pseudo-random graphs

A set N ⊂ Rd is called a weak ε-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ Rd for which every weak 1/r-net has at least Ω(r logd-1 r) points; this is the first superlinear lower bound for weak ε-nets in a fixed dimension.