Partitioning large matrices is an important problem in distributed linear algebra computing (used in ML among others).
Briefly, our goal is to perform a sequence of matrix algebra operations in a distributed manner (whenever possible) on these large matrices.
However, not all partitioning schemes work well with different matrix algebra operations and their implementations (algorithms). This is a type of data tiling problem.
In this work we consider a theoretical model for a version of the matrix  tiling problem in the setting of hypergraph labeling.
We prove some hardness results and give a  theoretical characterization of its complexity on random instances.
Additionally we develop a greedy algorithm and experimentally  show  its efficacy.

§ INTRODUCTION

Our problem is motivated by the following. Machine Learning and Scientific Computing usually involve linear algebra operations over large matrices and tensors (elements) ([19, 18]).
To achieve scalability, operations involving these elements are usually carried out using distributed algorithms.
If the involved elements are too large to be stored within a single shared memory system, then distribution is the only viable option in most cases.
In this setting, the problem of partitioning data elements across a collection of nodes over which the computation will be carried out emerges as a problem whose solution can yield significant benefits.

First, we give an informal description of the tiling problem.
We consider a user program $\cal P$ as a high-level collection of operations involving large elements. We consider only matrices and vectors; however, our formulation can be extended to higher dimensions without great difficulty.
These operations may be logically dependent, which is given by a dependency graph $\cal G$.
We want to execute the operations (in $\cal P$) in a distributed manner on a set of computational nodes.
In general, for different operations, we may have one or more distributed algorithms implementing the operation.
For example, suppose we have several different distributed implementations of matrix multiplication, which takes two input matrices and returns their product.
This operation can be implemented using multiple distributed algorithms (e.g., Cannon's Algorithm, Distributed Stressen's [3], PUMMA [8] etc.)  each may prefer a different type of partitioning scheme for the matrices involved.
An element may participate in multiple operations, and each operation may introduce a different set of constraints on the preferable partition of the element.
Considering the matrix example again, suppose a matrix $A$ is involved in two different operations: $C = \mathsf{mul}_{cannon}(A,B)$ and $D = \mathsf{inv}_{gj}(A)$.
Further, suppose multiplication has been implemented using Cannon's algorithm, which prefers that the matrices be partitioned block-wise.
On the other hand, a matrix inversion using Gauss-Jordan may prefer the matrix $A$ to be distributed as blocks of columns (column tiling).
Unless we want to keep multiple copies of $A$, the choice of the partitioning scheme will affect the performance of different operations involving $A$.
This example leads us to a natural optimization problem: given a collection of operations, determine an optimal partitioning scheme for the elements to minimize the communication cost.

§.§ Problem Formulation

In this section, we describe some elements of our model at a high level. In subsequent sections, we adapt it based on the specific result we seek.
We often use the phrase “user program" to indicate a collection of possibly dependent high-level operations. Abstracting away local operations, external memory read-write, etc. We only concern ourselves with operations in the program involving the distributed matrices.
However, our optimization framework is fairly generic.

§.§.§ Partitioning Schemes

First, we discuss the type and the degree of granularity in the partitioning scheme that we consider.
In general, a collection of matrices (either sparse or dense) can be considered as a  hypergraph where the elements of the matrices are vertices, and an edge indicates if the elements are involved in some operation (here operation refers to atomic operations like sum, comparisons, etc.).
Hence a collection of matrices and dependent expressions gives way to a set of hypergraphs, and the goal is to find an optimal $p$-partition (where $p$ is the number of processing nodes) that minimizes the total number of cut-edges.
Hypergraph partitioning has been used extensively for partitioning data or the computation ([15, 4, 10]).
This problem is approximation-hard and various heuristic based solvers used in practice are best suited when dealing with one such graph at a time.
Further, determination of the exact communication pattern (and thus the edges) may be non-trivial.

On the other hand, most distributed matrix algebra algorithms use some type of block decomposition (especially for dense matrices).
Thus it makes sense to look at the partitioning scheme at a higher level, which we call tilings.
As an example in figure <ref> three commonly used tilings are shown. A tiling need not be contiguous or necessarily disjoint, and as such, there can be many different tiling types (a parameter of our model discussed later).

A tile is highlighted as the shaded rectangular region. Three types of tilings. From left to right order: row ($r$), column ($c$) and block ($b$).

§.§.§ Operations

The second element in our model is the matrix algebra operations.
They are encapsulated at a high level as expressions like $A = \mathsf{mul}(B, C)$. These are the “atomic expressions" in our model.
So an expression like the following is a composite expression:

\begin{align}\label{eq: exp ex}
A = \mathsf{sum}(B, C, \mathsf{mul}(D,E,F^T)),
\end{align}

A possible computation DAG corresponding to the expression in Eq <ref>. Here $G$ is an additional matrix to hold the intermediate result $\mathsf{mul}(D, E, F^T)$.

where $F^T$ is the transpose of $T$.
The above expression does not immediately tell us how we should go about computing the product $DEF^T$.
Interpreting this as $D(EF^T)$ is not the same as $(DE)F^T$ in terms of the number of arithmetic operations used,
since different parenthesization of the matrices in the product term may lead to a differing number of arithmetic operations to compute the final product. This is another optimization issue[We can solve this easily using dynamic programming formulation.] separate from the partitioning problem.
Also, note that the expression does not explicitly tell us where/how to store this temporary product.
For example, if the result matrix $DE$ will be used later in some other expression, it may be a good idea to store it as a separate matrix.
This is another orthogonal optimization problem.
To avoid ambiguities in classifying expressions, we consider an abstraction based on hypergraphs (introduced in section 4). However, to prove a lower bound, a simpler model using graphs is considered (section 3).
A possible computation DAG of the expression given in Eq. <ref> is shown in figure <ref>.
Even in the hypergraphic model, we use a partial order to encode the dependency of the expressions similar to using a computational DAG.

§.§.§ Cost Model

A solution to our partitioning problem is a tiling of the matrices.
There are various ways to define a cost function based on the communication complexity of the tiling.
A choice of tiling may affect the performance of a distributed algorithm in a non-trivial way.
In most cases, this would require experimental evaluations.
We decouple our cost model from specific system architectures by only considering the abstract cost of the number of retiling operations.
Where Retiling is the operation of changing the current tiling of the matrix to meet the algorithm's requirements in the implementation.
[Alternatively, we may think of this as the cost of accessing non-local memory as if the matrix has been tiled correctly.]
That is, given a tiling of the matrices, we determine the number of instances in which a matrix is not tiled according to the specification of the operation.
If the matrices have unequal sizes, we can use weights to scale the retiling cost accordingly.
In summary, we consider a data partitioning problem on a collection of distributed matrix algebra operations to minimize overall communication, which is approximated by the retiling cost.

§ EXPERIMENTAL RESULTS

We implemented the greedy algorithm in Python
[https://github.com/folshost/TilingSolver] to facilitate its use in Python-based distributed processing API's which have shown significant growth throughout the past few years.
For the experiments, we chose to investigate the performance of our algorithm on a mix of modifications on known algorithms and random algorithms.
We chose these modified algorithms due to the limited number of supported expressions in our implementation of the greedy algorithm.
For known algorithms, we chose an approximate Linear Regression program, an approximate PCA with a 3-round power method for eigenvector determination, a bi-directional power set series of multiplications, and two random programs.
Although our implementation was sensitive to matrix size as a factor in cost calculations, we chose to leave all matrices used in our simulated programs the same size to simplify testing.

We compared our results between the three algorithms: 1) a local solver, 2) exhaustive search, and 3) our greedy algorithm described in the previous section.
According to the execution order specified by the computation DAG, the local solver chooses locally optimal tilings for each expression in a single forward pass of the program.
The exhaustive search enumerates all possible tilings and finds the lowest cost available.
To obtain improvements in computation time (i.e., to make exhaustive search tractable), we restricted our expressions to one implementation for each algorithm.

The greedy search algorithm has three configurable parameters.
All of the experimental data was collected using $\alpha=10$.
However, we chose to vary $\beta$ and $\eta$ in a grid search to investigate the effects of these parameters.
Figure <ref> shows the effects of this variation.
The figure is an average across our five test programs of the max-normalized times yielded by the grid search.
That is, for each program, the grid search yielded a number of times, which were then normalized against the maximum amount of time required for that program.
To aggregate across the five programs, we averaged the five generated grids on an element-wise basis to characterize the effects of $\beta$ and $\eta$ across all programs, giving equal weight to all programs.
The greedy search algorithm gave equal scores for the solutions derived, irrespective of the parameterization of $\beta$ or $\eta$.

From figure <ref> we can see a significant effect of the $\beta$ (bucket size) parameter, while it would not appear that there is a significant effect due to $\eta$ (weight ratio).

Test     Local     E Search     Greedy
Linear Regression     0.0012        0.3443     0.019366

Parallel PCA          0.0020      605.7924     0.042917

Power Set             0.0042     1275.4500     0.042180

Random 1              0.0041        1.0372     0.029209

Random 2              0.0014        0.0517     0.023032

Times for search execution (in seconds)

Each program has three searches performed for it

Effects on search time of Beta and Eta parameters

In figure <ref> we can see that in all cases but one, our algorithm matched the solution found by exhaustive search, and in all cases did better than the local solver.
Table <ref> shows us that our algorithm in most cases is comparable in timing to the local solver operation, while the exhaustive search is almost always more than an order of magnitude slower.
For our tests then, our greedy algorithm was generally successful in obtaining the benefits of both of the competing algorithms while retaining none of their drawbacks.

As we noted previously, one of our goals is to make the greedy algorithm work in the distributed HPC environment.
Since this tiling solver would run for every program executed in that environment, it must allow running at such a speed that it does not significantly impact the actual user program's total run time.
With this in mind, although the exhaustive search would yield good results, in certain cases, the number of involved matrices and operations in a user program could result in a lengthy solve process, as typified by the Parallel PCA and Power Set Multiplication programs.
All of the programs we used were less than 18 matrix operations.
For comparison, SOTA deep neural networks like BERT[11] or GPT-3[7] often use a large number of layers (in large BERT's case 24 transformer layers, in GPT-3's 96 transformer layers), without taking into consideration any preprocessing steps for data, meaning user programs for investigation could substantially exceed the size of our experimental programs.
We also kept our search space small with the number of implementations of edges in these experiments.
With these facts in mind, in certain circumstances, it could become prohibitive, even with further parallelization of the search process (on server processors or across multiple nodes), to exhaustively search the entirety of that space.

§.§ Hardware

For these experiments, we ran all of the tests as multi-threaded processes on an i5-8600k, with a base clock of 3.6 GHz, running in Python 3.6.8 and using Numpy 1.18.1.

§ A MEMORY OCCUPANCY PROBLEM

Here we take a digression and discuss an interesting problem arising out of our tiling optimization study.
Let $G$ be the program DAG and  $H(V,E)$ is the corresponding hypergraph as introduced previously.
Here we consider an optimization of the memory storage by reordering the expressions consistent with the partial order $P$ induced by $G$ on the set $E$ of expression.
Lifespan of a matrix is the interval starting from the first time it appeared in an expression to the last time. If the matrix is one of the outputs (we denote the set of outputs as $O \subset V$, here  $O$ can be empty if the output of the program is a scalar) of the program then it must be kept in memory at least until the last expression is executed.
The number of matrices that must be kept simultaneously in memory (where the lifespans overlap) depends on the order in which the expressions are executed.
Our goal is to minimize the maximum memory load during the execution of the user program. We will show that this problem is NP hard by a reduction from the cut-width problem.

We continue to define some more terms.

Let $L$ be a linear extension of $P$.
For every matrix $ A \not \in O$ let $s_A$ and $t_A$ be the first and the last expression in the ordering $L$ that the matrix $A$ was involved in.
If $A \in O$ then we associate with $A$ the interval $[s_A, m]$ ($m$ is the number of expression).
This forces us to keep the output matrix to stay in memory after it has been computed.
We can create an interval graph $I_{L}$ based on the intervals $[s_A, t_A]$ corresponding to the matrices in $V$ for the linear extension $L$.
If two intervals overlaps then the corresponding matrices must be kept in memory together during the execution of overlapping expressions.
The maximum memory needed to execute the program depends on the maximal set of mutually overlapping intervals for a given ordering of the expressions.
In order to reduce the maximum memory consumption we want to choose a linear extension that minimizes the maximum overlapping set of intervals.
Since output matrices must stay in memory after they have been computed, hence we need to hold at least $|O|$ matrices simultaneously, regardless of the order in which they have been computed.
Let $\kappa(I_L)$ be the clique number of $I_L$. Then the decision version of this memory occupancy problem ($\mathsf{MOP}$) is as follows: given $G, H$ and a positive integer $k$ decide if there is a  linear extension $L$ such that  $\kappa(I_L) \le k$.
As an example consider the following program, where we use the notation $(out, \{input\})$ to indicate the set of input and output matrices involved within an expression[For this problem the matrix operations can be arbitrary.].

\begin{align}
e_1: (A_{1}; \{A_2, A_3\})\\
e_2: (A_{4}; \{A_3, A_1\})\\
e_3: (A_{5}; \{A_1, A_2\})\\
e_4: (A_{6}; \{A_1, A_2, A_4\})
\end{align}

where $O = \{A_5,A_6\}$. The intervals for two different ordering of the expressions for the above program is shown in Figure  <ref>.

The graph $G_{int}$ corresponding to the program $P_1$. Here the output set is $\{A\}$

Next we prove that $\mathsf{MOP}$ is NP-complete.

Deciding whether $\mathsf{MOP}$ has a satisfiable instance for some $k$ is NP-Complete.

This can be proven by reducing the cut-width problem for simple undirected graphs to our problem.
If vertices of a graph is linearly ordered along a line, then the edges between the points (vertices) on this line forms intervals (see Fig <ref>).
Let $R$ be some left to right ordering of the vertices. A vertex is denoted by its order from the left. An edge is  represented by an interval $[l,r]$.
We say an interval crosses the $i^{th}$ vertex in $R$ if $i \in [l,r-1]$. Let $\theta_i(R)$ be the number of intervals crossing the $i^{th}$ vertex in $R$.
The cut-width of the ordering $R$ is then $\max_{1\le i\le n} \theta_i(R)$. The cut-width of $G$ is minimum cut-width over all possible orderings ($\min_{R \in {\cal S}_n}\max_{1\le i\le n} \theta_i(R)$).

It is known that determining the cut-width of a graph is NP-hard for an arbitrary $k$, but fixed parameter tractable in $k$ (see [20]).

A graph $G$ (left) along with a linear representation (right). Maximum number of edges crossing any vertex is the width, which in this case is 2.

Given an instance of the cut-width problem (a graph $G(V, E))$ we reduce it to an instance of $\mathsf{MOP}$ in the following way.

Identify a matrix $B_{ij}$ for every edge $(i,j) \in E_v$ and $i, j \in V$ and a matrix $C_i$ for each vertex.
We create an initial expression:

$$e_{-1} : (A_{-1}; \{C_1,\ldots,C_n\})$$

In the above and what follows the matrix before the semicolon is the output matrix and the set of matrices after the semicolon are the input matrices.
For each vertex $i \in V$ create an expression:

$$e_i : (A_i;  \{ B_{ij}\mid j \in N(i)\}\cup \{C_i\}\cup \{A_{-1}\})$$

where $N(i)$ is the set of neighbors of $i$ in $G$.
Now we create an additional expression:

$$e_{n+1} : (A_{n+1} ; \{A_1,\ldots,A_n,A_{-1}\})$$

and set $O = \{A_{n+1}\}$. Let $A = \{A_{-1},A_1,\ldots,A_{n+1}\}$, $B =\{B_{ij}\mid \ (i,j) \in E\} $ and $C = \{C_1,\ldots, C_n\}$.

Let $G'$ be the program DAG determined by the above expressions $\{e_{-1},e_1,\ldots,e_{n+1}\}$ with the vertex set $A\cup B\cup C$.
Next we show that $G'$ has a satisfying instance of size at most $k+n+1$ if and only if $G$ has a cut-width of at most $k$.
Let us prove the only if direction first.
Let $R$ be an ordering of the expressions that produces a satisfying instance of size at most $k+n+1$.
Firstly, In the partial order $P$ induced by $G'$ we have $e_{-1}\succ e_i \succ e_{n+1}$ for all $i \le n$. Further $e_i$ and $e_j$ are incomaparble if $i \ne j$ and $i,j \not \in \{-1,n+1\}$.
Secondly, each expression $e_i$ has a unique (input) matrix $C_i$ associated with it.
The number of matrices from $A \cup C$ that need to be kept in memory just after executing the $i^{th}$ expression  (according to $R$) is exactly $n+1$.
This is independent of the ordering $R$. Hence if $G'$ has a satisfying instance of size at most $n+1+k$ then there are at most $k$ matrices from the set $B$ are kept in memory at any given time. From our construction we see that these are precisely those matrices that corresponds to edges in $G$.
Hence cut-width of $G$ on $R$ is at most $k$.
To prove the other direction assume $G$ has a cut-width of at most $k$ and let $R'$ be an optimal ordering on $V$ ($v_{R'(1)}, \ldots, v_{R'(1)}$). We then extend $R'$ to get an ordering of the expressions $R = (e_{-1},e_{R'(1)}, \ldots, e_{R'(1)},e_{n+1})$ for which we only need to keep at most $k$ matrices from $B$ in memory at any given time. Hence $R$ is an satisfying ordering of size at most $n+1+k$.

In [20] authors show that the cut-width problem is fixed parameter tractable in $k$. Here we conjecture that $\mathsf{MOP}$ is also fixed parameter tractable if $\min_L \kappa(I_L)$ is bounded. The problem is to determine the cut-width of $G$ when ordering of the vertices are restricted to linear extensions of a given partial order.

Let $w$ be the width of the partial order $P$. The hardness of $\mathsf{MOP}$ is sensitive to $w$. Consider the two extreme case: 1) when $w = 1$, then $P$ is a total order and the solution is trivial. 2) $w = \Omega(n)$ then $P$ is an anti-chain, and from the proof above we see that $\mathsf{MOP}$ is NP-hard.
This motivates us to come up with an exact algorithm when $w$ is bounded.

$\mathsf{MOP}$ can be solved exactly in time $O(w^2n)$ when $w$ is bounded.

We can use dynamic programming here.
Let $R_i$ be an optimal ordering of the expression fr

[1]
Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
O ($\sqrt{\log n}$) approximation algorithms for min uncut, min 2cnf
deletion, and directed cut problems.
In Proceedings of the thirty-seventh annual ACM symposium on
Theory of computing, pages 573–581, 2005.

[2]
Adi Avidor and Michael Langberg.
The multi-multiway cut problem.
Theoretical Computer Science, 377(1-3):35–42, 2007.

[3]
Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, and Oded Schwartz.
Communication-optimal parallel algorithm for strassen's matrix
In Proceedings of the twenty-fourth annual ACM symposium on
Parallelism in algorithms and architectures, pages 193–204, 2012.

[4]
Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz.
Brief announcement: Hypergraph partitioning for parallel sparse
matrix-matrix multiplication.
In Proceedings of the 27th ACM symposium on Parallelism in
Algorithms and Architectures, pages 86–88, 2015.

[5]
Michael Bauer and Michael Garland.
Legate numpy: accelerated and distributed array computing.
In Proceedings of the International Conference for High
Performance Computing, Networking, Storage and Analysis, pages 1–23, 2019.

[6]
Michael Bauer, Sean Treichler, Elliott Slaughter, and Alex Aiken.
Legion: Expressing locality and independence with logical regions.
In SC'12: Proceedings of the International Conference on High
Performance Computing, Networking, Storage and Analysis, pages 1–11. IEEE,

[7]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan,
Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda
Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan,
Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,
Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray,
Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford,
Ilya Sutskever, and Dario Amodei.
Language models are few-shot learners, 2020.

[8]
Jaeyoung Choi, David W Walker, and Jack J Dongarra.
Pumma: Parallel universal matrix multiplication algorithms on
distributed memory concurrent computers.
Concurrency: Practice and Experience, 6(7):543–570, 1994.

[9]
Bhaskar DasGupta, German Andres Enciso, Eduardo Sontag, and Yi Zhang.
Algorithmic and complexity results for decompositions of biological
networks into monotone subsystems.
Biosystems, 90(1):161–178, 2007.

[10]
Karen D Devine, Erik G Boman, Robert T Heaphy, Rob H Bisseling, and Umit V
Parallel hypergraph partitioning for scientific computing.
In Proceedings 20th IEEE International Parallel & Distributed
Processing Symposium, pages 10–pp. IEEE, 2006.

[11]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
BERT: pre-training of deep bidirectional transformers for language
CoRR, abs/1810.04805, 2018.

[12]
Rong Gu, Yun Tang, Chen Tian, Hucheng Zhou, Guanru Li, Xudong Zheng, and Yihua
Improving execution concurrency of large-scale matrix multiplication
on distributed data-parallel platforms.
IEEE Transactions on Parallel and Distributed Systems,
28(9):2539–2552, 2017.

[13]
Chien-Chin Huang, Qi Chen, Zhaoguo Wang, Russell Power, Jorge Ortiz, Jinyang
Li, and Zhen Xiao.
Spartan: A distributed array framework with smart tiling.
In 2015 $\{$USENIX$\}$ Annual Technical Conference
($\{$USENIX$\}$$\{$ATC$\}$ 15), pages 1–15, 2015.

[14]
Falk Hüffner, Nadja Betzler, and Rolf Niedermeier.
Optimal edge deletions for signed graph balancing.
In International Workshop on Experimental and Efficient
Algorithms, pages 297–310. Springer, 2007.

[15]
George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar.
Multilevel hypergraph partitioning: applications in vlsi domain.
IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, 7(1):69–79, 1999.

[16]
Subhash Khot.
On the power of unique 2-prover 1-round games.
In Proceedings of the thiry-fourth annual ACM symposium on
Theory of computing, pages 767–775, 2002.

[17]
Subhash Khot and Nisheeth K Vishnoi.
On the unique games conjecture.
In FOCS, volume 5, page 3. Citeseer, 2005.

[18]
Pat Langley.
Elements of machine learning.
Morgan Kaufmann, 1996.

[19]
Chase Roberts, Ashley Milsted, Martin Ganahl, Adam Zalcman, Bruce Fontaine,
Yijian Zou, Jack Hidary, Guifre Vidal, and Stefan Leichenauer.
Tensornetwork: A library for physics and machine learning.
arXiv preprint arXiv:1905.01330, 2019.

[20]
Dimitrios M Thilikos, Maria Serna, and Hans L Bodlaender.
Cutwidth i: A linear time fixed parameter algorithm.
Journal of Algorithms, 56(1):1–24, 2005.

[21]
Mingxing Zhang, Yongwei Wu, Kang Chen, Teng Ma, and Weimin Zheng.
Measuring and optimizing distributed array programs.
Proceedings of the VLDB Endowment, 9(12):912–923, 2016.


#  On the spanning structure hierarchy of 3-connected planar graphs

On-Hei Solomon Lo School of Mathematical Sciences, Xiamen University, Xiamen
361005, PR China. This work was partially supported by NSFC grant 11971406.

###### Abstract

The prism over a graph $G$ is the Cartesian product of $G$ with the complete
graph $K_{2}$. $G$ is prism-hamiltonian if the prism over $G$ has a Hamilton
cycle. A good even cactus is a connected graph in which every block is either
an edge or an even cycle, and every vertex is contained in at most two blocks.
It is known that good even cacti are prism-hamiltonian. Indeed, showing the
existence of a spanning good even cactus has become one of the most common
techniques in proving prism-hamiltonicity. Špacapan asked whether having a
spanning good even cactus is equivalent to having a hamiltonian prism for
3-connected planar graphs. In this article we give a negative answer to this
question by showing that there are infinitely many 3-connected planar prism-
hamiltonian graphs that have no spanning good even cactus. We also prove the
existence of an infinite class of 3-connected planar graphs that have a
spanning good even cactus but no spanning good even cactus with maximum degree
three.

##  1 Introduction

In 1884, in an attempt to solve the Four Color Theorem (which was open then),
Tait [17] gave a proof which required that every 3-connected 3-regular planar
graph is hamiltonian. The proof, however, turned out to be false and the first
counterexample to the hypothesis, a non-hamiltonian 3-connected 3-regular
planar graph, was constructed by Tutte [19] in 1946. It is also known that
there are 3-connected 3-regular planar graphs that have no Hamilton path [9,
3].

On the positive side, Tutte [20] showed in 1956 that every 4-connected planar
graph does have a Hamilton cycle. Tutte’s result was strengthened by Thomassen
[18] who proved that every 4-connected planar graph is Hamilton-connected,
that is, any two vertices are connected by a Hamilton path.

Hamilton cycles and Hamilton paths can be generalized by the following notion.
A _$k$ -walk_ is a spanning closed walk that visits every vertex at most $k$
times; a _$k$ -tree_ is a spanning tree with maximum degree at most $k$.
Clearly, a graph has a $k$-walk if it has a $k$-tree. It was shown in [11]
that every $k$-walk contains a subgraph that is a $(k+1)$-tree. In particular,
1-walk and 2-tree are the same notion of Hamilton cycle and Hamilton path,
respectively.

The _prism_ over a graph $G$ is the Cartesian product of $G$ and $K_{2}$,
denoted by $G\square K_{2}$. $G$ is _prism-hamiltonian_ if and only if
$G\square K_{2}$ is hamiltonian. The following chain of implications on the
existence of spanning structures is well-known:

Hamilton cycle $\Rightarrow$ Hamilton path $\Rightarrow$ hamiltonian prism
$\Rightarrow$ 2-walk $\Rightarrow$ 3-tree

Barnette [1] showed that every 3-connected planar graph has a 3-tree.
Confirming a conjecture of Jackson and Wormald [11], Gao and Richter [7]
proved that every 3-connected planar graph has a 2-walk (see also [8]). It is
natural to ask if all 3-connected planar graphs can reach the level of
“hamiltonian prism” in the suggested hierarchy. This was formulated as a
conjecture by Kaiser, Ryjáček, Král’, Rosenfeld and Voss [12], which was also
attributed to Rosenfeld and Barnette in [16].

######  Conjecture 1 ([12, Conjecture 1]).

Every 3-connected planar graph has a hamiltonian prism.

Supporting this conjecture, a number of subclasses were shown to be prism-
hamiltonian: 3-connected 3-regular (not necessarily planar) graphs [14], Halin
graphs [12], 3-connected bipartite planar graphs [2], near-triangulations [2]
and 3-connected planar graphs with minimum degree at least four [15]. However,
a recent breakthrough by Špacapan [16] showed that the conjecture is not true
in general.

######  Theorem 2 ([16]).

There are infinitely many $3$-connected planar non-prism-hamiltonian graphs.

Based on Špacapan’s technique, Ikegami, Maezawa and Zamfirescu [10] provided
various classes of counterexamples with special properties.

A _good even cactus_ is a connected graph in which every block is either an
edge or an even cycle and every vertex is contained in at most two blocks (see
Figure 1). It is known that the prism of any good even cactus is hamiltonian.
Therefore, one can assert that a graph is prism-hamiltonian if it has a
spanning good even cactus. This strategy has been used in proving prism-
hamiltonicity for various planar and non-planar graph classes; we refer to
[14, 12, 2, 13, 4, 5, 6, 15] for examples.111Note that some graph classes in
the given examples were not explicitly shown to have the property of having a
spanning good even cactus, but one may justify it by modifying the
corresponding original proof. It is worth noting that in [14, 12, 13, 4, 5] a
more restrictive approach was adopted, namely showing the existence of a
spanning good even cactus with maximum degree at most three. This proof
technique motivates us to refine the spanning structure hierarchy as follows:

Hamilton cycle $\Rightarrow$ Hamilton path

$\Rightarrow$ spanning good even cactus with maximum degree at most three

$\Rightarrow$ spanning good even cactus $\Rightarrow$ hamiltonian prism
$\Rightarrow$ 2-walk $\Rightarrow$ 3-tree

Obviously the three new implications hold. There are 3-connected planar graphs
showing that the implication from “Hamilton path” to “spanning good even
cactus with maximum degree at most three” is sharp; an example is given in
Figure 2. Špacapan [16] recently asked whether the implication from “spanning
good even cactus” to “hamiltonian prism” can be reversed for 3-connected
planar graphs.

######  Problem 3 ([16, Problem 3.3]).

Prove or disprove the following statement. Every 3-connected planar prism-
hamiltonian graph has a spanning good even cactus.

Figure 1: A good even cactus with maximum degree three, which becomes a good
even cactus with maximum degree four if the thick edge is contracted. Figure
2: A variation of Herschel’s graph which has no Hamilton path (as it has eight
components when the six white vertices are removed) and has a spanning good
even cactus with maximum degree at most three (thick edges).

The main purpose of this article is to show that every implication in the new
hierarchy proposed above is sharp. Inspired by Špacapan’s counterexamples to
Conjecture 1, we show that there are infinitely many 3-connected planar graphs
that have a spanning good even cactus but no such spanning subgraph with
maximum degree at most three (Theorem 5) and there are infinitely many
3-connected planar graphs that have a hamiltonian prism but no spanning good
even cactus (Theorem 6), thereby answering the question raised by Špacapan.

We remark that “hamiltonian prism” can be replaced by “spanning good cactus”
in the hierarchy we consider above. As mentioned in [16], the partitioning
result given in [7] assures that every 3-connected planar graph has a good
cactus as a spanning subgraph.

The proofs of our results will be given in the next section. We conclude this
section with some terminology and notation.

Let $H$ be a graph and $V$ be a vertex set (not necessarily a subset of
$V(H)$). The subgraph of $H$ induced by $V\cap V(H)$ is denoted by $H[V]$. For
graphs $H_{1}$ and $H_{2}$, $H_{1}[H_{2}]$ means $H_{1}[V(H_{2})]$. For any
set $U$ of vertices and edges, we use $H-U$ to denote that graph obtained from
$H$ by deleting the elements in $U$; we may also write $H-u$ instead of
$H-\\{u\\}$ when $U=\\{u\\}$. The union $H_{1}\cup H_{2}$ of graphs $H_{1}$
and $H_{2}$ is defined to be $(V(H_{1})\cup V(H_{2}),E(H_{1})\cup E(H_{2}))$.
Let $H^{\prime}$ be a subgraph of $H$ and $E\subseteq E(H)$ be an edge set. We
may denote by $H^{\prime}\cup E$ the union of $H^{\prime}$ and the subgraph of
$H$ induced by $E$. Let $u,v$ be two vertices in a connected graph $H$. The
graph $H[u,v]$ is defined to be the minimal union of blocks of $H$ such that
$H[u,v]$ is connected and contains vertices $u$ and $v$. For any graph $H$ and
any $v\in V(H)$, let $H^{i}$ be a copy of $H$, we may denote by $v^{i}$ the
duplicate of $v$ in $H^{i}$.

A _cactus_ $Q$ is a connected graph such that every block of $Q$ is either an
edge or a cycle. For any $v\in V(Q)$, the _block degree_ $b_{Q}(v)$ of $v$ in
$Q$ is defined to be the number of blocks of $Q$ that contain $v$. We call a
block of $Q$ that is an edge (a cycle) an _edge block_ (a _cycle block_). We
say that $Q$ is _even_ if every cycle block of it is an even cycle. A path $P$
in $Q$ is an _edge path_ if every edge of $P$ is an edge block of $Q$. A
cactus $Q$ is _good_ if $b_{Q}(v)\leq 2$ for any $v\in V(Q)$. Note that if we
delete some vertex from a good even cactus, the new components are even cacti
but need not be good anymore. For this reason we introduce two more types of
cacti as follows:

  * •

Let $P$ be an edge path in a cactus $Q$. We say that $Q$ is a _$P$ -good_
cactus if (i) $b_{Q}(v)\leq 2$ for any vertex $v$ that is not an internal
vertex of $P$ and (ii) $b_{Q}(v)\leq 3$ for any internal vertex of $P$.

  * •

Let $P_{1}$ and $P_{2}$ be two edge paths in a cactus $Q$ that have at most
one common vertex. Then $Q$ is a _$\\{P_{1},P_{2}\\}$ -good_ cactus if (i)
$b_{Q}(v)\leq 2$ for any vertex $v$ that is neither an internal vertex of
$P_{1}$ nor an internal vertex of $P_{2}$, (ii) $b_{Q}(v)\leq 3$ for any
vertex $v$ that is an internal vertex of either $P_{1}$ or $P_{2}$ (but not
for both) and (iii) $b_{Q}(v)=4$ for any vertex $v$ that is an internal vertex
for both paths $P_{1}$ and $P_{2}$.

A cactus $Q$ is _$1$ -good_ if there exists an edge path $P$ in $Q$ such that
$Q$ is $P$-good; _$2$ -good_ if there exist two edge paths $P_{1}$ and $P_{2}$
in $Q$ sharing at most one vertex such that $Q$ is $\\{P_{1},P_{2}\\}$-good.

We always assume that the complete graph $K_{2}$ is on $\\{\alpha,\beta\\}$.
The prism $H\square K_{2}$ over $H$ is defined to be the graph on $V(H\square
K_{2}):=V(H)\times\\{\alpha,\beta\\}$ such that $(u,\gamma)(v,\delta)$ are
adjacent if and only if (i) $uv\in E(H)$ and $\gamma=\delta$ or (ii) $u=v$ and
$\gamma\neq\delta$. For any $\gamma\in V(K_{2})$, we denote by $\bar{\gamma}$
the vertex of $K_{2}$ other than $\gamma$. Let $S$ be a subgraph of $H\square
K_{2}$. The reflection $R$ of $S$ is a graph defined as follows: (i)
$(u,\gamma)\in V(R)$ if and only if $(u,\bar{\gamma})\in V(S)$; (ii)
$(u,\gamma)(v,\delta)\in E(R)$ if and only if
$(u,\bar{\gamma})(v,\bar{\delta})\in E(S)$.

##  2 Results

We first introduce three fragments that we need in our construction. The plane
graph $A$ is as depicted in Figure 3. Let $n$ be any positive integer. We
define $C_{n}$ to be the cycle of length $2n+3$ (see Figure 4(a)) and $D_{n}$
to be the cactus that has exactly two cycle blocks each of them has length
$2n+3$ (see Figure 4(b)). We refer to Figures 3 and 4 for names of vertices in
$A$, $C_{n}$ and $D_{n}$ that are not explicitly defined in the text.

Figure 3: The plane graph $A$ with endvertices $u_{1}$ and $u_{3}$. The thick
edges induce a spanning good even cactus $K_{A}$ of $A$ with
$b_{K_{A}}(u_{1})=b_{K_{A}}(u_{3})=1$.

Figure 4: (a) The plane graph $C_{n}$ with endvertices $l$ and $r$. (b) The
plane graph $D_{n}$ with endvertices $l$ and $r$.

We now define our main construction. Let $B$ be either $C_{n}$ or $D_{n}$
(which will be fixed throughout the construction). We take eight copies
$A^{1},\dots,A^{8}$ of $A$ and seven copies $B^{1},\dots,B^{7}$ of $B$, and
form a connected graph $G^{-}(B)$ from these fifthteen fragments by
identifying $u_{3}^{i}$ with $l^{i}$ and identifying $r^{i}$ with
$u_{1}^{i+1}$ for every $i\in\\{1,\dots,7\\}$. We see $G^{-}(B)$ as a plane
graph by inheriting the plane embeddings of $A$ and $B$ given by Figures 3 and
4. So the boundary walk around the unbounded face is the union of two edge-
disjoint paths with endvertices $u_{1}^{1}$ and $u_{3}^{8}$, so that the
vertices $w_{1}^{1},\dots,w_{1}^{7}$ and, if $B$ is $D_{n}$, the vertices
$x_{1}^{1},\dots,x_{1}^{7}$ will be contained in the “upper path” but not the
“lower path”. The graph $G(B)$ is obtained from $G^{-}(B)$ and two new
vertices $s$ and $t$ by joining $s$ to every vertex in the upper path and $t$
to every vertex in the lower path. We will simply write $G$ and $G^{-}$
instead of $G(B)$ and $G^{-}(B)$ if it is clear from the context what $B$
denotes or it causes no ambiguity. It is clear that $G$ is planar. Moreover,
it can be shown in exactly the same way as in the proof of [16, Lemma 2.5]
that $G$ is 3-connected. We conclude with the following lemma.

######  Lemma 4.

Let $n$ be any positive integer and $B$ be either $C_{n}$ or $D_{n}$. The
graph $G(B)$ constructed above is a $3$-connected planar graph.

The main goal of this article is to prove the following two results.

######  Theorem 5.

For any positive integer $n$, the $3$-connected planar graph $G(C_{n})$ has a
spanning good even cactus but no spanning good even cactus with maximum degree
three.

######  Theorem 6.

For any positive integer $n$, the $3$-connected planar graph $G(D_{n})$ is
prism-hamiltonian but has no spanning good even cactus.

The proofs of Theorems 5 and 6 will be given in Sections 2.2 and 2.3,
respectively. Before that, we provide in Section 2.1 a number of lemmas for
proving the results.

###  2.1 Preliminaries

We first discuss some properties of the fragments we use in the construction
regarding whether they can contain spanning cacti with specified block degree
condition.

######  Lemma 7.

Let $I:=A[\\{u_{1},u_{2}\\}\cup\\{v_{1},\dots,v_{12}\\}]$. Let $Q$ be a
spanning even cactus of $I$ that contains an edge path $P$ with endvertices
$u_{1}$ and $u_{2}$. Suppose that every vertex of $Q$ that is not an internal
vertex of $P$ has block degree at most two in $Q$. We have that $u_{1}$ and
$u_{2}$ have block degree two in $Q$.

###### Proof.

By symmetry, we may assume that $P$ is contained in
$I[\\{u_{1},u_{2}\\}\cup\\{v_{7},\dots,v_{12}\\}]$. Suppose that
$b_{Q}(u_{1})=1$ (reductio ad absurdum). It follows immediately that
$u_{1}v_{1}\notin E(Q)$, $u_{1}v_{6}\notin E(Q)$, and $v_{1}v_{2}$ and
$v_{2}v_{3}$ are two edge blocks of $Q$ (as $Q$ is a spanning cactus). If
$v_{4}$ is contained in any cycle block of $Q\subset
I-\\{u_{1}v_{1},u_{1}v_{6}\\}$, then that block must be
$v_{3}v_{4}v_{5}u_{2}v_{6}v_{3}$, which is however impossible since $Q$ is an
even cactus. By the same argument, we have that $v_{5}$ and $v_{6}$ are not in
any cycle block in $Q$.

Note that $Q$ has at least one edge of $v_{3}v_{6}$ and $v_{6}u_{2}$ and at
least one edge of $v_{3}v_{4}$ and $v_{5}u_{2}$, since $Q$ is a connected
spanning subgraph of $I$. We consider the following two cases. If both
$v_{3}v_{6}$ and $v_{6}u_{2}$ are in $E(Q)$, then (depending on $v_{3}v_{4}$
or $v_{5}u_{2}$ is an edge of $Q$) $v_{3}$ or $u_{2}$ has to have block degree
at least three in $Q$, contradicting the given condition. If exactly one of
$v_{3}v_{6},v_{6}u_{2}$ is in $E(Q)$, then $Q$ must contain
$v_{3}v_{4}v_{5}u_{2}$ as an edge path and $v_{3}$ or $u_{2}$ will have block
degree at least three in $Q$, again, a contradiction. We thus conclude that
$b_{Q}(u_{1})=b_{Q}(u_{2})=2$. ∎

######  Lemma 8.

Let $Q$ be an even cactus of $A$ that contains an edge path $P$ with
endvertices $u_{1}$ and $u_{3}$. If $Q$ is $P$-good, then $Q$ is no spanning
subgraph of $A$.

###### Proof.

Suppose that $Q$ is a spanning subgraph of $A$ (reductio ad absurdum). Let
$I_{1}:=A[\\{u_{1},u_{2}\\}\cup\\{v_{1},\dots,v_{12}\\}]$ and
$I_{2}:=A-\\{u_{1}\\}\cup\\{v_{1},\dots,v_{12}\\}$. Then, for $i\in\\{1,2\\}$,
$Q_{i}:=Q[I_{i}]$ is a spanning even cactus of $I_{i}$ having
$P_{i}:=P[I_{i}]$ as an edge path with endvertices $u_{i}$ and $u_{i+1}$. It
is also clear that every vertex of $Q_{i}$ that is not an internal vertex of
$P_{i}$ is contained in at most two blocks in $Q_{i}$. Therefore we can apply
Lemma 7 twice to conclude that $b_{Q_{1}}(u_{2})=b_{Q_{2}}(u_{2})=2$ and hence
$b_{Q}(u_{2})=4$, contradicting our assumption that $Q$ is $P$-good. ∎

######  Lemma 9.

Let $Q$ be a good even cactus of $B$ that contains vertices $l$ and $r$, where
$B$ is taken to be $C_{n}$ or $D_{n}$ for some positive integer $n$. If $l$
and $r$ have block degree one, then $Q$ is no spanning subgraph of $B$.

###### Proof.

It is readily to see that $Q$ has no cycle block and hence is an edge path
with endvertices $l,r$. In particular, $Q$ is no spanning subgraph of $B$. ∎

As mentioned before, one cannot guarantee that the components are good cacti
after removing some vertices from a good cactus. However, we may characterize,
in terms of good, 1-good and 2-good cacti, the components of the graph
obtained from some spanning good cactus of $G(B)$ by deleting vertices $s$ and
$t$.

######  Lemma 10.

Let $K$ be a good cactus with maximum degree at most three and $s,t$ be two
vertices in $K$. One of the following statements holds:

  1. (I)

$K-s-t$ is a vertex-disjoint union of at most four cacti, at most two of which
are $1$-good and the rest are good.

  2. (II)

$K-s-t$ is a vertex-disjoint union of at most three cacti, one of which is
$2$-good and the rest are good.

###### Proof.

As $K$ is a good cactus with maximum degree at most three, no two distinct
cycle blocks in $K$ can intersect.

We now consider the following cases. If $s$ and $t$ are in some cycle block
$S$ in $K$, then $K-s-t$ is comprised of $b_{K}(s)+b_{K}(t)-2$ good cacti and
$k$ 1-good cacti, where $k$ is the number of components of $S-s-t$. As every
vertex in $K$ has block degree at most two, $K-s-t$ has at most two good
cactus components, at most two 1-good cactus components and no other
components. So we are in Case (I). If $s$ and $t$ are in two cycle blocks
$S_{s}$ and $S_{t}$ in $K$, respectively, such that $S_{s}-s$ and $S_{t}-t$
are in the same component of $K-s-t$, then we are in Case (II) as $K-s-t$ is
comprised of one 2-good cactus and $b_{K}(s)+b_{K}(t)-2\leq 2$ good cacti.
Otherwise, it is not hard to see that $K-s-t$ has up to three components, at
most two of which are 1-good cacti and the rest are good cacti, which is
included in Case (I). ∎

The following lemma can be proved analogously, thus we omit the proof.

######  Lemma 11.

Let $K$ be a good cactus and $s,t$ be two vertices in $K$. One of the
following statements holds:

  1. (I)

$K-s-t$ is a vertex-disjoint union of at most four cacti, each of which is
good or $1$-good.

  2. (II)

$K-s-t$ is a vertex-disjoint union of at most three cacti, one of which is
$2$-good and each of the rest is good or $1$-good.

Suppose $G$ has a spanning subgraph $K$ that is a good even cactus. Let $Q$ be
a component of $K-s-t$. Let $H$ be any copy of $A$ or $B$ in $G^{-}$. We say
$H$ is a _bag_ of $Q$ if $Q$ contains the endvertices of $H$ but not all
vertices of $H$, where the endvertices of $A$ (respectively, $B$) are $u_{1}$
and $u_{3}$ (respectively, $l$ and $r$). For $i<1$, we define $l^{i}$ and
$r^{i}$ to be $u_{1}^{1}$; for $i>7$, we define $l^{i}$ and $r^{i}$ to be
$u_{3}^{8}$. We may choose $0\leq a\leq b\leq 8$ such that $Q$ is contained in
$G^{-}[l^{a},r^{b}]$ and, subject to this, $b-a$ is minimum. The following
three lemmas gives us lower bound on the number of bags of $Q$.

######  Lemma 12.

If $Q$ is a good even cactus, then it has at least $b-a-1$ bags.

###### Proof.

For every $a<i<b$, $Q[B^{i}]$ is an even cactus of $B^{i}$ containing $l^{i}$
and $r^{i}$. By the minimality of $b-a$, $l^{i}$ is contained in some block of
$Q[A^{i}]$ and hence has block degree one in $Q[B^{i}]$. Similarly, we have
$b_{Q[B^{i}]}(r^{i})=1$. As vertices in $Q[B^{i}]$ other than $l^{i},r^{i}$
has block degree at most two, we may apply Lemma 9 to conclude that $Q[B^{i}]$
does not span $B^{i}$ and hence $B^{i}$ is a bag of $Q$. Collecting all these
bags for every $a<i<b$, we conclude that $Q$ has $b-a-1$ bags. ∎

######  Lemma 13.

Suppose $Q$ is a $P$-good even cactus for some edge path $P$ in $Q$. We have
that $Q$ has at least $b-a-2$ bags. Moreover, if $Q$ has no bag and $b=a+2$,
then $P$ is contained in $G^{-}[r^{a},l^{b}]$.

###### Proof.

Choose $a\leq a^{\prime}\leq b^{\prime}\leq b$ such that $P[A^{i+1}]$ is a
path with endvertices $r^{i}$ and $l^{i+1}$ for any $a^{\prime}\leq
i<b^{\prime}$, and, subject to this, $b^{\prime}-a^{\prime}$ is maximum.

Note that if $P[A^{i+1}]$ is a path with endvertices $r^{i},l^{i+1}$, then
$Q[A^{i+1}]$ is a $P[A^{i+1}]$-good even cactus of $A^{i+1}$. Therefore, by
Lemma 8, $Q[A^{i+1}]$ does not span $A^{i+1}$ and $A^{i+1}$ is a bag of $Q$.

By the maximality of $b^{\prime}-a^{\prime}$ and the fact that $P$ is a path,
we have that $P$ is contained in $G^{-}[r^{a^{\prime}-1},l^{b^{\prime}+1}]$.
This and the minimality of $b-a$ imply that for any $i$ with $a<i<a^{\prime}$
or $b^{\prime}<i<b$, $Q[B^{i}]$ is an even cactus of $B^{i}$ containing
$l^{i}$ and $r^{i}$. Moreover, $l^{i}$ and $r^{i}$ have block degree one in
$Q[B^{i}]$ while all other vertices in $Q[B^{i}]$ have block degree at most
two. By Lemma 9, we assure that $B^{i}$ is a bag of $Q$. Thus we have that $Q$
has at least $(b^{\prime}-a^{\prime})+(a^{\prime}-a-1)+(b-b^{\prime}-1)=b-a-2$
bags.

Suppose $Q$ has no bag and $b=a+2$, we claim that $P$ is contained in
$G^{-}[r^{a},l^{a+2}]$. Otherwise, by symmetry, we may assume that $P$ has one
endvertex in $B^{a}-r^{a}$. Let $p$ be the other endvertex of $P$. If $p$ is
in $G^{-}[l^{a+1},r^{a+2}]$, then it follows from Lemma 8 that $A^{a}$ is a
bag of $Q$. If $p$ is not in $G^{-}[l^{a+1},r^{a+2}]$, then, by Lemma 9,
$B^{a+1}$ is a bag of $Q$. In any case it contradicts the assumption that $Q$
has no bag. This thus justifies our claim. ∎

######  Lemma 14.

If $Q$ is a $2$-good even cactus, then it has at least $b-a-3$ bags.

###### Proof.

The proof is similar to what we have done for the previous lemmas. Let $P_{1}$
and $P_{2}$ be two edge path in $Q$ having at most one common vertex such that
$Q$ is $\\{P_{1},P_{2}\\}$-good. We may choose $a\leq a^{\prime}\leq
b^{\prime}\leq a^{\prime\prime}\leq b^{\prime\prime}\leq b$ such that
$(P_{1}\cup P_{2})[A^{i+1}]$ is a path with endvertices $r^{i}$ and $l^{i+1}$
for any $i$ with $a^{\prime}\leq i<b^{\prime}$ or $a^{\prime\prime}\leq
i<b^{\prime\prime}$, and, subject to this,
$b^{\prime\prime}-a^{\prime\prime}+b^{\prime}-a^{\prime}$ is maximum. Now, if
$(P_{1}\cup P_{2})[A^{i+1}]$ is a path with endvertices $r^{i},l^{i+1}$, then
$Q[A^{i+1}]$ is an even cactus of $A^{i+1}$ satisfying the block degree
condition required by Lemma 8, from which it follows that $Q[A^{i+1}]$ does
not span $A^{i+1}$ and $A^{i+1}$ is a bag of $Q$.

As $a^{\prime},b^{\prime},a^{\prime\prime},b^{\prime\prime}$ are chosen with
$b^{\prime\prime}-a^{\prime\prime}+b^{\prime}-a^{\prime}$ maximized and
$P_{1}\cup P_{2}$ is either a vertex-disjoint union of two paths or a tree
that has at most one vertex of degree larger than two, we have that $P_{1}\cup
P_{2}$ is contained in $G^{-}[r^{a^{\prime}-1},l^{b^{\prime}+1}]\cup
G^{-}[r^{a^{\prime\prime}-1},l^{b^{\prime\prime}+1}]$. For any $i$ with
$a<i<a^{\prime}$ or $b^{\prime}<i<a^{\prime\prime}$ or $b^{\prime\prime}<i<b$,
$Q[B^{i}]$ is a good even cactus of $B^{i}$ containing vertices $l^{i}$ and
$r^{i}$ of block degree one. Applying Lemma 9, we have that $B^{i}$ is a bag
of $Q$, and hence $Q$ has at least
$(b^{\prime}-a^{\prime})+(b^{\prime\prime}-a^{\prime\prime})+(a^{\prime}-a-1)+(a^{\prime\prime}-b^{\prime}-1)+(b-b^{\prime\prime}-1)=b-a-3$
bags. ∎

###  2.2 Proof of Theorem 5

In this section we shall show that $G(C_{n})$ has a spanning good even cactus,
but it does not contain any spanning good even cactus with maximum degree
three. Note that $B$ will represent the fragment $C_{n}$ throughout this
section.

A spanning good even cactus $K_{A}$ of $A$ is depicted in Figure 3. We denote
by $K_{A}^{i}$ the corresponding copy of $K_{A}$ in $A^{i}$. It is
straightforward to verify that

$\displaystyle\left(\bigcup_{i=1}^{8}K_{A}^{i}\right)$
$\displaystyle\cup\left(\bigcup_{i=1,3}(B^{i}-l^{i}w_{1}^{i})\right)\cup\left(\bigcup_{i=5,7}(B^{i}-w_{n+1}^{i}r^{i})\right)$
$\displaystyle\cup\left(\bigcup_{i=2,4,6}(B^{i}-l^{i}v_{1}^{i}-w_{n+1}^{i}r^{i})\right)\cup\\{sl^{1},sw_{1}^{1},tl^{3},sw_{1}^{3},tw_{n+1}^{5},sr^{5},tw_{n+1}^{7},tr^{5}\\}$

is a spanning good even cactus of $G$.

Thus it is left to show that $G$ does not have any spanning good even cactus
with maximum degree at most three. Suppose that $G$ has a spanning good even
cactus $K$ with maximum degree at most three (reductio ad absurdum). Let
$Q_{1},\dots,Q_{k}$ be the components of $K-s-t$ that contain some vertex from
$U_{2}:=\\{u_{2}^{1},\dots,u_{2}^{8}\\}$. For every $Q_{j}$
($j\in\\{1,\dots,k\\}$), we choose $0\leq a(j)\leq b(j)\leq 8$ such that
$Q_{j}$ is contained in $G^{-}[l^{a(j)},r^{b(j)}]$ and, subject to this,
$b(j)-a(j)$ is minimum. Since the union of $Q_{1},\dots,Q_{k}$ contains all
vertices in $U_{2}$, we have that

$\sum_{j=1}^{k}(b(j)-a(j))\geq|U_{2}|=8.$

We denote by $q_{1}$ and $q_{2}$ the numbers of 1-good and 2-good components
among $Q_{1},\dots,Q_{k}$.

Let $c_{j}$ be the number of bags of $Q_{j}$. Note that every bag $H$ of
$Q_{j}$ does contain some component of $K-s-t$ that does not contain the
endvertices of $H$. We have that $c_{j}$ bags of $Q_{j}$ contain (at least)
$c_{j}$ distinct components of $K-s-t$. Moreover, it is not hard to see that
no distinct components from $Q_{1},\dots,Q_{k}$ can have any bag in common.
Therefore $K-s-t$ has at least $\sum_{j=1}^{k}(1+c_{j})$ components.

We consider the following two cases according to Lemma 10.

Case I. If $K-s-t$ has at most four components such that at most two of them
are 1-good even cacti and the rest are good even cacti, then, by Lemmas 12 and
13, $K-s-t$ has at least
$\sum_{j=1}^{k}(1+c_{j})\geq\sum_{j=1}^{k}(b(j)-a(j))-q_{1}\geq 8-2=6$
components, which contradicts that $K-s-t$ has at most four components.

Case II. If $K-s-t$ has at most three components such that one of them is a
2-good even cactus and the rest are good even cacti, then, by Lemmas 12 and
14, $K-s-t$ has at least
$\sum_{j=1}^{k}(1+c_{j})\geq\sum_{j=1}^{k}(b(j)-a(j))-2q_{2}\geq 8-2=6$
components, which contradicts that $K-s-t$ has at most three components.

Therefore we may conclude that $G$ has no spanning good even cactus with
maximum degree at most three, and this completes the proof of Theorem 5.

###  2.3 Proof of Theorem 6

In this section we shall show that there is a Hamilton cycle in the prism over
$G(D_{n})$, but there is no spanning subgraph of $G(D_{n})$ that is a good
even cactus. Note that $B$ will be the fragment $D_{n}$ throughout this
section.

We first prove that $G(D_{n})\square K_{2}$ is hamiltonian. Here we assume $n$
is odd, the case $n$ is even can be dealt with analogously.

We need the following result due to Ellingham, Salehi Nowbandegani and Shan
[6].

######  Proposition 15 ([6, Theorem 2.3]).

Let $Q$ be a good even cactus. The prism over $Q$ has a Hamilton cycle that
contains the edge at $(v,\alpha)(v,\beta)$ for any $v\in V(Q)$ with
$b_{Q}(v)=1$.

As shown in Figure 3, $A$ has a spanning good even cactus in which $u_{1}$ and
$u_{3}$ have block degree one. Hence it follows from Proposition 15 that there
exists a Hamilton cycle $H_{A}$ in $A\square K_{2}$ containing the edges
$(u_{1},\alpha)(u_{1},\beta)$ and $(u_{3},\alpha)(u_{3},\beta)$. In the prism
over $B$, we define $L_{B}$, $S_{B}$ and $\tilde{S}_{B}$ to be the graphs
depicted in Figures 5(a), (b) and (c), respectively; and $R_{B}$ and
$\tilde{R}_{B}$ be the reflections of $S_{B}$ and $\tilde{S}_{B}$,
respectively. Each of the graphs $L_{B}$, $S_{B}$, $\tilde{S}_{B}$, $R_{B}$
and $\tilde{R}_{B}$ is a union of vertex-disjoint paths that spans $B\square
K_{2}$. One can readily verify that

$\displaystyle(H_{A}^{1}-(u_{3}^{1},\alpha)(u_{3}^{1},\beta))\cup\left(\bigcup_{i=2}^{7}(H_{A}^{i}-(u_{1}^{i},\alpha)(u_{1}^{i},\beta)-(u_{3}^{i},\alpha)(u_{3}^{i},\beta))\right)\cup(H_{A}^{8}-(u_{1}^{8},\alpha)(u_{1}^{8},\beta))$
$\displaystyle\cup\left(\bigcup_{i=2,4,6}L_{B}^{i}\right)\cup
S_{B}^{1}\cup\\{(s,\beta)(w_{n}^{1},\beta),(t,\alpha)(x_{2n+1}^{1},\alpha)\\}\cup\tilde{S}_{B}^{3}\cup\\{(s,\beta)(w_{n}^{3},\beta),(t,\beta)(x_{2n}^{3},\beta)\\}$
$\displaystyle\cup
R_{B}^{5}\cup\\{(s,\alpha)(w_{n}^{5},\alpha),(t,\beta)(x_{2n+1}^{5},\beta)\\}\cup\tilde{R}_{B}^{7}\cup\\{(s,\alpha)(w_{n}^{7},\alpha),(t,\alpha)(x_{2n}^{7},\alpha)\\}$

is a Hamilton cycle of $G\square K_{2}$.

Figure 5: In each subfigure the thin and thick edges together represent the
prism over $D_{n}$ such that the vertices of $V(D_{n})\times\\{\alpha\\}$ are
placed above that of $V(D_{n})\times\\{\beta\\}$; the leftmost and rightmost
straight edges denote $(l,\alpha)(l,\beta)$ and $(r,\alpha)(r,\beta)$,
respectively; and each copy of $D_{n}$ is embedded in the same way as depicted
in Figure 4(b). (a) The graph $L_{D_{n}}$ (thick edges) consists of one path
with endvertices $(l,\alpha)$ and $(l,\beta)$ and one with endvertices
$(r,\alpha)$ and $(r,\beta)$. (b) The graph $S_{D_{n}}$ (thick edges) consists
of one path with endvertices $(l,\alpha)$ and $(w_{n},\beta)$, one with
endvertices $(l,\beta)$ and $(r,\beta)$ and one with endvertices $(r,\alpha)$
and $(x_{2n+1},\alpha)$. (c) The graph $S_{D_{n}}$ (thick edges) consists of
one path with endvertices $(l,\alpha)$ and $(w_{n},\beta)$, one with
endvertices $(l,\beta)$ and $(r,\beta)$ and one with endvertices $(r,\alpha)$
and $(x_{2n},\beta)$.

It is now left to show that $G$ does not have any spanning good even cactus.
Suppose that $G$ has a spanning good even cactus $K$ (reductio ad absurdum).
As in the proof of Theorem 5, we consider the components $Q_{1},\dots,Q_{k}$
of $K-s-t$ that contain some vertex from
$U_{2}:=\\{u_{2}^{1},\dots,u_{2}^{8}\\}$. For any component $Q_{j}$ of $K-s-t$
($j\in\\{1,\dots,k\\}$), we choose $0\leq a(j)\leq b(j)\leq 8$ such that
$Q_{j}$ is contained in $G^{-}[l^{a(j)},r^{b(j)}]$ and, subject to this,
$b(j)-a(j)$ is minimum. Again, the inequality $\sum_{j=1}^{k}(b(j)-a(j))\geq
8$ holds. Let $q_{1}$ and $q_{2}$ be the numbers of 1-good and 2-good cacti
among $Q_{1},\dots,Q_{k}$, respectively.

As we have discussed in the previous section, $K-s-t$ has at least
$\sum_{j=1}^{k}(1+c_{j})$ components, where $c_{j}$ is the number of bags of
$Q_{j}$. By Lemma 11, we have the following two cases.

Case I. If $K-s-t$ consists of at most four even cacti which are good or
1-good, then, by Lemmas 12 and 13, $K-s-t$ has at least
$\sum_{j=1}^{k}(1+c_{j})\geq\sum_{j=1}^{k}(b(j)-a(j))-q_{1}\geq 8-4=4$
components. Since there are at most four components in $K-s-t$, the equality
must hold. In this case we must have that $q_{1}=4$. This implies that $k=4$
and every component $Q_{j}$ is 1-good. Then we have $c_{j}=0$ for every $j$.
In other words, no $Q_{j}$ can have any bag. As $0=c_{j}\geq b(j)-a(j)-2$
holds for every $j$ and $\sum_{j=1}^{4}(b(j)-a(j))\geq 8$, we have that
$b(j)=a(j)+2$ for every $j\in\\{1,\dots,4\\}$. We may assume that
$a(j)=2(j-1)$ for any $j$, and that $Q_{1}$ and $Q_{2}$ are $P_{1}$-good and
$P_{2}$-good, respectively. By Lemma 13, $P_{1}$ and $P_{2}$ are contained in
$G^{-}[r^{0},l^{2}]$ and $G^{-}[r^{2},l^{4}]$, respectively. If either $Q_{1}$
or $Q_{2}$ does not intersect $B^{2}$, then $(Q_{1}\cup Q_{2})[B^{2}]$ is a
spanning good even cactus of $B^{2}$, indeed, an edge path with $l^{2}$ or
$r^{2}$ has block degree one, which is clearly impossible. If both $Q_{1}$ and
$Q_{2}$ intersect $B^{2}$, then $(Q_{1}\cup Q_{2})[B^{2}]$ is a union of two
edge paths, one of which has $l^{2}$ as endvertex and the other has $r^{2}$ as
endvertex, spanning the graph $B^{2}$, which is, again, impossible.

Case II. If $K-s-t$ has at most three components such that one of them is a
2-good even cactus and the rest are good or 1-good even cacti, then, by Lemmas
12, 13 and 14, $K-s-t$ has at least
$\sum_{j=1}^{k}(1+c_{j})\geq\sum_{j=1}^{k}(b(j)-a(j))-q_{1}-2q_{2}\geq 4$
components, which contradicts that $K-s-t$ has at most three components.

Hence we conclude that no spanning subgraph of $G$ can be a good even cactus,
and this completes the proof of Theorem 6.

## Acknowledgements

The author wishes to thank Carol T. Zamfirescu for helpful discussion.

## References

  * [1] D. W. Barnette.  Trees in polyhedral graphs.  Canadian J. Math., 18:731–736, 1966.
  * [2] D. P. Biebighauser and M. N. Ellingham.  Prism-hamiltonicity of triangulations.  J. Graph Theory, 57(3):181–197, 2008.
  * [3] T. A. Brown.  Simple paths on convex polyhedra.  Pacific J. Math., 11(4):1211–1214, 1961.
  * [4] L. R. Bueno and P. Horák.  On Hamiltonian cycles in the prism over the odd graphs.  J. Graph Theory, 68(3):177–188, 2011.
  * [5] M. N. Ellingham and P. Salehi Nowbandegani.  The Chvátal-Erdős condition for prism-Hamiltonicity.  Discrete Math., 343(7):111709, 2020.
  * [6] M. N. Ellingham, P. Salehi Nowbandegani, and S. Shan.  Toughness and prism-hamiltonicity of ${P}_{4}$-free graphs.  Discrete Appl. Math., 284:201–206, 2020.
  * [7] Z. Gao and R. B. Richter.  2-walks in circuit graphs.  J. Combin. Theory Ser. B, 62:259–267, 1994.
  * [8] Z. Gao, R. B. Richter, and X. Yu.  2-walks in 3-connected planar graphs.  Australas. J. Combin., 11:117–122, 1995.
  * [9] B. Grünbaum and T. S. Motzkin.  Longest simple paths in polyhedral graphs.  J. London Math. Soc., 37:152–160, 1962.
  * [10] D. Ikegami, S. Maezawa, and C. T. Zamfirescu.  On 3-polytopes with non-Hamiltonian prisms.  J. Graph Theory, 97(4):569–577, 2021.
  * [11] B. Jackson and N. C. Wormald.  $k$-walks of graphs.  Australas. J. Combin., 2:135–146, 1990.
  * [12] T. Kaiser, Z. Ryjáček, D. Král’, M. Rosenfeld, and H. Voss.  Hamilton cycles in prisms.  J. Graph Theory, 56(4):249–269, 2007.
  * [13] K. Ozeki.  A degree sum condition for graphs to be prism hamiltonian.  Discrete Math., 309(13):4266–4269, 2009.
  * [14] P. Paulraja.  A characterization of Hamiltonian prisms.  J. Graph Theory, 17(2):161–171, 1993.
  * [15] S. Špacapan.  Polyhedra without cubic vertices are prism-hamiltonian.  arXiv:2104.04266.
  * [16] S. Špacapan.  A counterexample to prism-hamiltonicity of 3-connected planar graphs.  J. Combin. Theory Ser. B, 146:364–371, 2021.
  * [17] P. G. Tait.  Listing’s topologie.  Phil. Mag. (5), 17:30–46, 1884.  Reprinted in Scientific Papers, Vol. II, pp. 85-98.
  * [18] C. Thomassen.  A theorem on paths in planar graphs.  J. Graph Theory, 7(2):169–176, 1983.
  * [19] W. T. Tutte.  On Hamiltonian circuits.  J. London Math. Soc., 21:98–101, 1946.
  * [20] W. T. Tutte.  A theorem on planar graphs.  Trans. Amer. Math. Soc., 82:99–116, 1956.


# Anticoncentration versus the Number of Subset Sums

Vishesh Jain  Ashwin Sah Supported by NSF Graduate Research Fellowship Program
DGE-1745302 Mehtaab Sawhney Supported by NSF Graduate Research Fellowship
Program DGE-1745302

###### Abstract

Let $\vec{w}=(w_{1},\dots,w_{n})\in\mathbb{R}^{n}$. We show that for any
$n^{-2}\leq\epsilon\leq 1$, if

$\\#\\{\vec{\xi}\in\\{0,1\\}^{n}:\langle\vec{\xi},\vec{w}\rangle=\tau\\}\geq
2^{-\epsilon n}\cdot 2^{n}$

for some $\tau\in\mathbb{R}$, then

$\\#\\{\langle\vec{\xi},\vec{w}\rangle:\vec{\xi}\in\\{0,1\\}^{n}\\}\leq
2^{O(\sqrt{\epsilon}n)}.$

This exponentially improves the $\epsilon$ dependence in a recent result of
Nederlof, Pawlewicz, Swennenhuis, and Wegrzycki and leads to a similar
improvement in the parameterized (by the number of bins) runtime of bin
packing.

title = Anticoncentration versus the Number of Subset Sums, author = Vishesh
Jain, Ashwin Sah, and Mehtaab Sawhney, plaintextauthor = Vishesh Jain, Ashwin
Sah, Mehtaab Sawhney, keywords = anticoncentration, year=2021, number=6,
received=19 January 2021, published=28 June 2021, doi=10.19086/aic.24872,

[classification=text]

##  1 Introduction

For $\vec{w}:=(w_{1},\dots,w_{n})\in\mathbb{R}^{n}$ and a real random variable
$\xi$, recall that the Lévy concentration function of $\vec{w}$ with respect
to $\xi$ is defined for all $r\geq 0$ by

$\mathcal{L}_{\xi}(\vec{w},r)=\sup_{\tau\in\mathbb{R}}\mathbb{P}[|w_{1}\xi_{1}+\dots+w_{n}\xi_{n}-\tau|\leq
r],$

where $\xi_{1},\dots,\xi_{n}$ are i.i.d. copies of $\xi$. In combinatorial
settings (where $\vec{w}\in\mathbb{Z}^{n}$) a particularly natural and
interesting case is when $r=0$ and $\xi$ is a Bernoulli random variable, i.e.,
$\xi=0$ with probability $1/2$ and $\xi=1$ with probability $1/2$. For
lightness of notation, we will denote this special case by

$\rho(\vec{w})=\mathcal{L}_{\operatorname{Ber}(1/2)}(\vec{w},0)=\sup_{\tau\in\mathbb{R}}\mathbb{P}[\langle\vec{w},\vec{\xi}\rangle=\tau].$

In this note, we study the following question.

######  Question 1.1.

For a vector $\vec{w}=(w_{1},\dots,w_{n})\in\mathbb{R}^{n}$ with
$\rho(\vec{w})\geq\rho$, how large can the range

$\mathcal{R}(\vec{w})=\\{w_{1}\xi_{1}+\dots+w_{n}\xi_{n}:\xi_{i}\in\\{0,1\\}\\}$

be?

The two extremal examples here are $\vec{w}=(0,0,\dots,0)$, which corresponds
to $\rho(\vec{w})=1$, $|\mathcal{R}(\vec{w})|=1$ and
$\vec{w}=(1,10,\dots,10^{n-1})$, which corresponds to $\rho(\vec{w})=2^{-n}$,
$|\mathcal{R}(\vec{w})|=2^{n}$. Motivated by these examples, one may ask if
there is a smooth trade-off between $\rho(\vec{w})$ and
$|\mathcal{R}(\vec{w})|$. This turns out not to be the case. Indeed, for any
$\epsilon>0$, Wiman [6] gave an example of a $\vec{w}\in\mathbb{Z}^{n}$ for
which $|\mathcal{R}(\vec{w})|\geq 2^{(1-\epsilon)n}$ and $\rho(\vec{w})\geq
2^{-0.7447n}$. At the other end of the spectrum, when $\rho(\vec{w})\geq
2^{-\epsilon n}$, the so-called inverse Littlewood–Offord theory [4, 5, 3]
_heuristically_ suggests that $\vec{w}$ is essentially contained in a low-rank
generalized arithmetic progression of ‘small’ volume so that
$|\mathcal{R}(\vec{w})|$ is also ‘small’. However, the number of ‘exceptional
elements’ in the inverse Littlewood–Offord theorems [4, 5, 3] is unfortunately
too large to be able to rigorously establish such a statement.

Nevertheless, in a recent work on the parameterized complexity of the bin
packing problem (see Section 1.1), Nederlof, Pawlewics, Swennenhuis and
Wegrzycki [2] showed that for any $\epsilon>0$,

$\rho(\vec{w})\geq 2^{-\epsilon n}\implies|\mathcal{R}(\vec{w})|\leq
2^{\delta(\epsilon)n},$

where

$\delta(\epsilon)=O\left(\frac{\log\log(\epsilon^{-1})}{\sqrt{\log(\epsilon^{-1})}}\right).$
(1.1)

In particular, $\delta(\epsilon)\to 0$ as $\epsilon\to 0$. Moreover, we must
have $\delta(\epsilon)\geq(2-o(1))\epsilon$, as can be seen by considering

$\vec{w}=(C_{1},\dots,C_{1},C_{2},\dots,C_{2},\dots,C_{n/k},\dots,C_{n/k})\in\mathbb{R}^{n},$

where each $C_{i}$ is repeated $k$ times, and $C_{i}$ is sufficiently small
compared to $C_{i+1}$ for all $i$. Indeed, for such $\vec{w}$, we have
$\rho(\vec{w})=2^{-(\frac{1}{2}+o_{k}(1))\frac{n}{k}\log_{2}{k}}$ while
$|\mathcal{R}(\vec{w})|\leq 2^{(1+o_{k}(1))\frac{n}{k}\log_{2}{k}}$.

We conjecture that this example is essentially the worst possible, so that
$\delta(\epsilon)\leq 2\epsilon$. We are able to show that

$\delta(\epsilon)=O(\sqrt{\epsilon}),$ (1.2)

thereby obtaining an exponential improvement over 1.1. More precisely,

######  Theorem 1.2.

Let $\epsilon>0$. For any $n\geq\epsilon^{-1/2}$ and any
$\vec{w}\in\mathbb{R}^{n}$ satisfying $\rho(\vec{w})\geq\exp(-\epsilon n)$, we
have

$|\mathcal{R}(\vec{w})|\leq\exp(C_{\ref{thm:main}}\epsilon^{1/2}n),$

where $C_{\ref{thm:main}}$ is an absolute constant.

We prove this theorem in Section 2.

###  1.1 Application to bin packing

The bin packing problem is a classic NP-complete problem whose decision
version may be stated as follows: given $n$ items with weights
$w_{1},\dots,w_{n}\in[0,1]$ and $m$ bins, each of capacity $1$, is there a way
to assign the items to the bins without violating the capacity constraints?
Formally, is there a map $f:[n]\to[m]$ such that $\sum_{i\in
f^{-1}(j)}w_{i}\leq 1$ for all $j\in[m]$?

Björklund, Husfeldt, and Koivisto [1] provided an algorithm for solving bin
packing in time $\tilde{O}(2^{n})$ where the tilde hides polynomial factors in
$n$. It is natural to ask whether the base of the exponent may be improved at
all i.e. is there a (possibly randomized) algorithm to solve bin packing in
time $\tilde{O}(2^{(1-\epsilon)n})$ for some absolute constant $\epsilon>0$?

In recent work, Nederlof, Pawlewics, Swennenhuis and Wegrzycki [2] showed that
this is true provided that the number of bins $m$ is fixed. More precisely,
they showed that there exists a function $\sigma:\mathbb{N}\to\mathbb{R}^{>0}$
and a randomized algorithm for solving bin packing which, on instances with
$m$ bins, runs in time $\tilde{O}(2^{(1-\sigma(m))n})$, where $\tilde{O}$
hides polynomials in $n$ as well as exponential factors in $m$. Their
analysis, which crucially relies on 1.1, gives a very small value of
$\sigma(m)$ satisfying

$\sigma(m)\leq 2^{-m^{9}}.$ (1.3)

Using Theorem 1.2 instead of 1.1 in a black-box manner in the analysis of [2],
we exponentially improve the bound on $\sigma(m)$.

######  Corollary 1.3.

With notation as above, the randomized algorithm of [2] solves bin packing
instances with $m$ bins in time $\tilde{O}(2^{(1-\sigma(m))n})$ with high
probability, for $\sigma\colon\mathbb{N}\to\mathbb{R}^{>0}$ satisfying

$\sigma(m)=\tilde{\Omega}(m^{-12}),$ (1.4)

where $\tilde{\Omega}$ hides logarithmic factors in $m$.

######  Remark.

This follows by noting that the function $f_{C}(m)$ in [2, Section 3.6] is
$\tilde{\Theta}(m^{-2})$ so that $\delta$ in [2, Section 3.6] is
$\tilde{\Theta}(m^{-3})$. With Theorem 1.2, the function $\varepsilon(\delta)$
in the runtime analysis of [2, Section 3.4] satisfies
$\varepsilon(\delta)=O(\delta^{2})$. Therefore, the function $f_{B}(\delta)$
in the same section is $\tilde{O}(\delta^{4})$, which is
$\tilde{\Omega}(m^{-12})$. Note that if one were able to establish the
conjecturally optimal bound $\delta=O(\epsilon)$, this would lead to
$f_{B}(\delta)=\tilde{O}(\delta^{2})$, thereby giving the quadratically better
$\sigma(m)=\tilde{\Omega}(m^{-6})$.

###  1.2 Notation

We use big-$O$ notation to mean that an absolute multiplicative constant is
being hidden. We use $\operatorname{Ber}(1/2)$ to denote the balanced
$\\{0,1\\}$ Bernoulli distribution and $\operatorname{Bin}(k)$ to denote the
binomial distribution on $k$ trials with parameter $1/2$. Recall that
$\operatorname{Bin}(k)$ is the sum of $k$ independent
$\operatorname{Ber}(1/2)$ random variables. Given a distribution $\mu$, we let
$\mu^{\otimes n}$ denote the distribution of a random vector with $n$
independent samples from $\mu$ as its coordinates. We also use the following
standard additive combinatorics notation: $C+D=\\{c+d:c\in C,d\in D\\}$ is the
sumset (if $C,D$ are subsets of the same abelian group), and for a positive
integer $k$, we let $k\cdot C=C+\cdots+C$ ($k$ times) be the iterated sumset.
Finally, in some cases we will use the notation $\Sigma\cdot$ or $\int\cdot$
to denote that the expression in the sum or integral is the same as in the
previous line to simplify the presentation of long expressions.

###  1.3 Outline of the proof

As in [2], the starting point of our proof is the following observation: let
$A$ denote a fixed (but otherwise arbitrary) set of unique preimages for
points in $\mathcal{R}(\vec{w})$ (hence, $|A|=|\mathcal{R}(\vec{w})|$) and let
$B$ denote the the set of preimages of a value $\tau\in\mathbb{R}$ realising
$\rho(\vec{w})$. Then (Lemma 2.2) for any $k\geq 1$, the map $A\times(k\cdot
B)\to A+k\cdot B$ is a bijection. In particular, if $\vec{a}$ is sampled from
the uniform distribution on $A$ and $\vec{b}_{1},\dots,\vec{b}_{k}$ are
independently sampled from the uniform distribution on $B$, then

$\displaystyle|A|$
$\displaystyle=|A|\cdot\mathbb{P}[\vec{a}+\vec{b}_{1}+\dots+\vec{b}_{k}\in\\{0,\dots,k+1\\}^{n}]$
$\displaystyle=|A|\cdot\sum_{\vec{x}\in\\{0,\dots,k+1\\}^{n}}\mathbb{P}[\vec{a}+\vec{b}_{1}+\dots+\vec{b}_{k}=\vec{x}]$
$\displaystyle\leq|A|\cdot\sum_{\vec{x}\in\\{0,\dots,k+1\\}^{n}}\mathbb{P}[\vec{a}=\vec{a}(\vec{x})]\cdot\mathbb{P}[\vec{b}_{1}+\dots+\vec{b}_{k}=\vec{x}-\vec{a}(\vec{x})]$
$\displaystyle\leq\sum_{\vec{x}\in\\{0,\dots,k+1\\}^{n}}\mathbb{P}[\vec{b}_{1}+\dots+\vec{b}_{k}=\vec{x}-\vec{a}(\vec{x})]$

In [2], the largeness of $B$ is exploited by finding, for every $a\in A$, a
large subset of $B$ which is ‘balanced’ (in a certain sense) with respect to
$a$. Instead, we exploit the largeness of $B$ directly by using the
observation that the density of the uniform measure on $B$ with respect to the
uniform measure on $\\{0,1\\}^{n}$ is at most $2^{n}/|B|\leq 2^{\varepsilon
n}$. In particular, if we let $\mu_{k}$ denote the measure on $k\cdot B$
induced by the product measure on $B\times\dots\times B$ via the map
$(b_{1},\dots,b_{k})\mapsto b_{1}+\dots+b_{k}$ and if we let
$\operatorname{Bin}(k)^{\otimes n}$ denote the $n$-fold product of the
$\operatorname{Binomial}(k,1/2)$ distribution, then the density of $\mu_{k}$
with respect to $\operatorname{Bin}(k)^{\otimes n}$ is at most
$2^{k\varepsilon n}$. This allows us to replace the measure $\mu_{k}$
appearing in the last line of the above equation by
$\operatorname{Bin}(k)^{\otimes n}$, at the cost of a factor of
$2^{k\varepsilon n}$. Thus,

$|A|\leq 2^{k\epsilon
n}\cdot\sum_{\vec{x}\in\\{0,\dots,k+1\\}^{n}}\mathbb{P}_{\vec{x}\sim\operatorname{Bin}(k)^{\otimes
n}}[\vec{x}-\vec{a}(\vec{x})]$

The above expression is still complicated by the presence of the shift
$\vec{a}(\vec{x})$, about which we have no information except that it lies in
the set $A$. The key technical lemma in the proof is Lemma 2.1, which
essentially allows us to remove this shift after paying a factor which depends
on $|A|$. Ultimately, this gives an upper bound on the sum in terms of $|A|$
and $k$, which amounts to an upper bound on $|A|$ in terms of $k,\epsilon$,
and $|A|$. Optimizing the value of the free parameter $k$ now gives the
desired conclusion.

##  2 Proof of Theorem 1.2Theorem 1.2

We begin by recording the following key comparison bound, which will be proved
at the end of this section.

######  Lemma 2.1.

Let $n\geq k\geq C_{\ref{lem:sup-ratio}}$, where $C_{\ref{lem:sup-ratio}}$ is
a sufficiently large absolute constant and let $\delta>0$. For any
$A\subseteq\\{0,1\\}^{n}$ with $|A|\leq\exp(\delta n)$, the following holds.
Let $\vec{x},\vec{b}\sim\operatorname{Bin}(k)^{\otimes n}$ be independent
$n$-dimensional random vectors. Then,

$\mathbb{E}_{\vec{x}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\bigg{]}\leq\exp\left(C_{\ref{lem:sup-
ratio}}\left(\frac{1}{k}+\sqrt{\frac{\delta}{k}}\right)n\right).$

Let $n$, $\epsilon$, and $\vec{w}$ be as in Theorem 1.2. Let $\tau$ be such
that $\mathbb{P}[\langle\vec{w},\vec{\xi}\rangle=\tau]=\rho(\vec{w})$, where
$\vec{\xi}$ is a random vector with i.i.d. $\operatorname{Ber}(1/2)$
components. Let

$B=\\{\vec{\xi}\in\\{0,1\\}^{n}:\langle\vec{w},\vec{\xi}\rangle=\tau\\}.$

In particular, $|B|\geq\exp(-\epsilon n)\cdot 2^{n}$. Let
$|\mathcal{R}(\vec{w})|=\exp(\delta n)$. For each $r\in\mathcal{R}(\vec{w})$,
let $\vec{\xi}(r)$ be a fixed (but otherwise arbitrary) element of
$\\{0,1\\}^{n}$ such that $\langle\vec{w},\vec{\xi}(r)\rangle=r$. Let

$A=\\{\vec{\xi}(r)\in\\{0,1\\}^{n}:r\in\mathcal{R}(\vec{w})\\}.$

Note that, by definition, for any distinct $\vec{a}_{1},\vec{a}_{2}\in A$, we
have that
$\langle\vec{w},\vec{a}_{1}\rangle\neq\langle\vec{w},\vec{a}_{2}\rangle$ and
that $|A|=|\mathcal{R}(\vec{w})|=\exp(\delta n)$.

We will make use of the simple, but crucial, observation from [2] that $A$ and
$k\cdot B$ have a full sumset for all $k\geq 1$.

######  Lemma 2.2 ([2, Lemma 4.2]).

The map $(\vec{a},\vec{c})\mapsto\vec{a}+\vec{c}$ from $A\times(k\cdot B)$ to
$A+k\cdot B$ is injective.

###### Proof.

Indeed, if
$\vec{a}_{1}+(\vec{b}^{(1)}_{1}+\dots+\vec{b}^{(1)}_{k})=\vec{a}_{2}+(\vec{b}^{(2)}_{1}+\dots+\vec{b}^{(2)}_{k}$),
where $\vec{a}_{i}\in A$ and $\vec{b}^{(i)}_{j}\in B$, then taking the inner
product of both sides with $\vec{w}$ and using
$\langle\vec{w},\vec{b}\rangle=\tau$ for all $b\in B$, we see that
$\langle\vec{w},\vec{a}_{1}\rangle=\langle\vec{w},\vec{a}_{2}\rangle$, which
implies that $\vec{a}_{1}=\vec{a}_{2}$ by the definition of $A$. ∎

We are now ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

Let $k\geq 2$ be a parameter which will be chosen later depending on
$\epsilon$. We may assume $\epsilon\in(0,(2C_{\ref{lem:sup-ratio}})^{-2})$ by
adjusting $C_{\ref{thm:main}}$ appropriately at the end to make larger values
trivial. By Lemma 2.2, for each $\vec{x}\in\\{0,\ldots,k+1\\}^{n}$ for which
there exist $\vec{a}\in A$ and $\vec{c}\in k\cdot B$ with
$\vec{a}+\vec{c}=\vec{x}$, there exists a unique such choice
$\vec{a}=\vec{a}(\vec{x})\in A$. (For $\vec{x}\notin A+k\cdot B$, we let
$\vec{a}(\vec{x})$ be an arbitrary element of $A$.)

Now, let $\vec{a}$ be uniform on $A$, let $\vec{b}_{1},\ldots,\vec{b}_{k}$ be
uniform on $B$, and let $\vec{v}_{1},\ldots,\vec{v}_{k}$ be uniform on
$\\{0,1\\}^{n}$. Let $C_{i}\subseteq\\{0,\ldots,k+1\\}^{n}$ be the set of
vectors with $i$ coordinates equal to $k+1$. For
$\vec{x}\in\\{0,\ldots,k+1\\}^{n}$, we let
$\vec{x}^{\ast}\in\\{0,\dots,k\\}^{n}$ denote the vector obtained by setting
every occurrence of $k+1$ in $\vec{x}$ to $k$. We have

$\displaystyle 1$
$\displaystyle=\mathbb{P}[\vec{a}+\vec{b}_{1}+\cdots+\vec{b}_{k}\in\\{0,\ldots,k+1\\}^{n}]$
$\displaystyle=\sum_{i=0}^{n}\sum_{\vec{x}\in
C_{i}}\mathbb{P}[\vec{a}+\vec{b}_{1}+\cdots+\vec{b}_{k}=\vec{x}]$
$\displaystyle\leq\sum_{i=0}^{n}\sum_{\vec{x}\in
C_{i}}\mathbb{P}[\vec{a}=\vec{a}(\vec{x})]\mathbb{P}[\vec{b}_{1}+\cdots+\vec{b}_{k}=\vec{x}-\vec{a}(\vec{x})]$
$\displaystyle\leq\frac{1}{|A|}\sum_{i=0}^{n}\sum_{\vec{x}\in
C_{i}}\bigg{(}\frac{2^{n}}{|B|}\bigg{)}^{k}\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}-\vec{a}(\vec{x})]$
$\displaystyle\leq\frac{e^{k\epsilon n}}{|A|}\sum_{i=0}^{n}\sum_{\vec{x}\in
C_{i}}\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}^{\ast}]\sup_{\vec{a}\in
A}\frac{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}-\vec{a}]}{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}^{\ast}]}$
$\displaystyle=\frac{e^{k\epsilon
n}}{|A|}\sum_{i=0}^{n}(1/2^{k})^{i}\sum_{S\in\binom{[n]}{i}}\mathbb{E}_{\vec{x}\sim\operatorname{Bin}(k)^{\otimes([n]\setminus
S)}\times\\{k+1\\}^{S}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}-\vec{a}]}{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}^{\ast}]}\bigg{]}.$

Let $A_{S}$ be the set of elements in $A\subseteq\\{0,1\\}^{n}$ whose support
contains $S$. Let

$A^{\prime}_{S}=\\{\vec{a}^{\prime}\in\\{0,1\\}^{[n]\setminus
S}:\exists\vec{a}\in A_{S}\text{ with }\vec{a}|_{[n]\setminus
S}=\vec{a}^{\prime}\\}.$

Recall that $|A|=\exp(\delta n)$. Abusing notation so that the supremum of an
empty set is $0$, we can continue the above chain of inequalities to get that

$\displaystyle 1$ $\displaystyle\leq\frac{e^{k\epsilon
n}}{|A|}\sum_{i=0}^{n}(1/2^{k})^{i}\sum_{S\in\binom{[n]}{i}}\mathbb{E}_{\vec{x}\sim\operatorname{Bin}(k)^{\otimes([n]\setminus
S)}\times\\{k+1\\}^{S}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}-\vec{a}]}{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}^{\ast}]}\bigg{]}$
$\displaystyle=\frac{e^{k\epsilon
n}}{|A|}\sum_{i=0}^{n}(1/2^{k})^{i}\sum_{S\in\binom{[n]}{i}}\mathbb{E}_{\vec{x}\sim\operatorname{Bin}(k)^{\otimes([n]\setminus
S)}}\bigg{[}\sup_{\vec{a}\in
A_{S}^{\prime}}\frac{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=(\vec{x}-\vec{a})\times\\{k\\}^{S}]}{\mathbb{P}[\vec{v}_{1}+\cdots+\vec{v}_{k}=\vec{x}\times\\{k\\}^{S}]}\bigg{]}$
$\displaystyle=\frac{e^{k\epsilon
n}}{|A|}\sum_{i=0}^{n}(1/2^{k})^{i}\sum_{S\in\binom{[n]}{i}}\mathbb{E}_{\vec{x}\sim\operatorname{Bin}(k)^{\otimes([n]\setminus
S)}}\bigg{[}\sup_{\vec{a}\in
A_{S}^{\prime}}\frac{\mathbb{P}[(\vec{v}_{1}+\cdots+\vec{v}_{k})|_{[n]\setminus
S}=\vec{x}-\vec{a}]}{\mathbb{P}[(\vec{v}_{1}+\cdots+\vec{v}_{k})|_{[n]\setminus
S}=\vec{x}]}\bigg{]}$ $\displaystyle\leq\frac{e^{k\epsilon
n}}{|A|}\left(\sum_{i=0}^{n/2}\cdot+\sum_{i=n/2}^{n}2^{-ki}\cdot
2^{n}\cdot\left(\max_{\ell}\frac{\max\Big{\\{}\binom{k}{\ell-1},\binom{k}{\ell}\Big{\\}}}{\binom{k}{\ell}}\right)^{n-i}\right)$
$\displaystyle\leq\frac{e^{k\epsilon
n}}{|A|}\left(\sum_{i=0}^{n/2}\cdot+n\cdot 2^{-kn/2}\cdot 2^{n}\cdot
k^{n}\right)$ $\displaystyle\leq\frac{e^{k\epsilon
n}}{|A|}\bigg{(}\sum_{i=0}^{n/2}\binom{n}{i}2^{-ki}\exp(C_{\ref{lem:sup-
ratio}}(k^{-1}+(2\delta)^{1/2}k^{-1/2})(n/2))+2^{-kn/4}\bigg{)}$
$\displaystyle\leq\exp(-\delta
n)\exp\left(O(k\epsilon+k^{-1}+\delta^{1/2}k^{-1/2})n\right)$

by Lemma 2.1 applied to $A_{S}$, as long as $n/2\geq k\geq C_{\ref{lem:sup-
ratio}}\geq 20$. To deduce the last line, note that
$\binom{n}{i}2^{-ki}\leq(2^{-k}en/i)^{i}$, so for $i\geq\lceil
en/2^{k-1}\rceil$ the sum of weighted binomials is bounded by a geometric
series. Additionally, for $1\leq i\leq en/2^{k}$, if this interval is
nonempty, the sum of binomials is certainly bounded by $\exp(O(k^{-1}n))$.

Hence, the above inequality yields

$\delta\leq C(k\epsilon+k^{-1}+\delta^{1/2}k^{-1/2})$

for some absolute constant $C>0$. Now letting $k=\epsilon^{-1/2}/2$ (note that
this satisfies $2C_{\ref{lem:sup-ratio}}\leq 2k=\epsilon^{-1/2}\leq n$), we
find that

$\delta=O(\epsilon^{1/2}),$

as desired. ∎

The proof of Lemma 2.1 relies on the following preliminary estimate.

######  Lemma 2.3.

If $1\leq s\leq k/(16\pi)$, then

$\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\leq\exp(10\pi
s^{2}/k)+2k^{s}(4/5)^{k}.$

###### Proof.

We let $x\sim\operatorname{Bin}(k)$ and $y=x-k/2\sim\operatorname{Bin}(k)-k/2$
throughout. We let $z\sim\mathcal{N}(0,k\pi/8)$. We have

$\displaystyle\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{[}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\bigg{]}$
$\displaystyle=\mathbb{E}_{y}\bigg{[}\bigg{(}1+\frac{2y-1}{k/2+1-y}\bigg{)}^{s}\bigg{]}$
$\displaystyle\leq\mathbb{E}_{y}\bigg{[}\bigg{(}1+\frac{2y}{k/2+1-y}\bigg{)}^{s}\mathbbm{1}_{|y|\leq
k/3}\bigg{]}+k^{s}\mathbb{P}[|y|\geq k/3]$
$\displaystyle\leq\mathbb{E}_{y}\bigg{[}\bigg{(}1+\frac{2y}{k/2+1-y}\bigg{)}^{s}\mathbbm{1}_{|y|\leq
k/3}\bigg{]}+2k^{s}(4/5)^{k}.$

Note that the probability estimate for $\mathbb{P}[\mathbbm{1}_{|y|\geq k/3}]$
follows from the sharp (entropy) version of the Chernoff-Hoeffding theorem.
Since for $|y|\leq k/3$,

$\frac{2y}{(k/2+1-y)}\leq\frac{2y}{k/2+1}+\frac{8y^{2}}{(k/2+1)^{2}},$

and using $(1+x)\leq\exp(x)$, we can continue the previous inequality as

$\displaystyle\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{[}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\bigg{]}$
$\displaystyle\leq\mathbb{E}_{y}\bigg{[}\bigg{(}1+\frac{2y}{k/2+1}+\frac{8y^{2}}{(k/2+1)^{2}}\bigg{)}^{s}\mathbbm{1}_{|y|\leq
k/3}\bigg{]}+2k^{s}(4/5)^{k}$
$\displaystyle\leq\mathbb{E}_{y}\bigg{[}\exp\bigg{(}\frac{4sy}{k+2}+\frac{32sy^{2}}{k^{2}}\bigg{)}\bigg{]}+2k^{s}(4/5)^{k}.$

Now, let $z_{1},\dots,z_{k}$ be i.i.d. $\mathcal{N}(0,1)$ random variables.
Then,

$y\sim\frac{1}{2}\left(\operatorname{sgn}{z_{1}}+\dots+\operatorname{sgn}{z_{k}}\right).$

Moreover, for any $-k\leq\ell\leq k$,

$\mathbb{E}[z_{1}+\dots+z_{k}\mid\operatorname{sgn}(z_{1})+\dots+\operatorname{sgn}(z_{k})=\ell]=\sqrt{\frac{2}{\pi}}\ell.$

In particular, under this coupling of $y,z_{1},\dots,z_{k}$, we have

$\mathbb{E}[z_{1}+\dots+z_{k}\mid y]=\sqrt{\frac{8}{\pi}}y.$

Let $z=z_{1}+\dots+z_{k}$, so that $z\sim\mathcal{N}(0,k)$. Then, by the
convexity of

$f(y)=\exp\bigg{(}\frac{4sy}{k+2}+\frac{32sy}{k^{2}}\bigg{)}$

and using Jensen’s inequality, we have

$\displaystyle\mathbb{E}_{y}f(y)$
$\displaystyle=\mathbb{E}_{y,z_{1},\dots,z_{k}}f(y)$
$\displaystyle=\mathbb{E}_{y,z_{1},\dots,z_{k}}f\left(\sqrt{\frac{\pi}{8}}\mathbb{E}[z\mid
y]\right)$ $\displaystyle\leq\mathbb{E}_{z}f(\sqrt{\pi}z/\sqrt{8})$
$\displaystyle=\mathbb{E}_{w\sim\mathcal{N}(0,1)}\exp\bigg{(}\frac{s\sqrt{2k\pi}}{k+2}w+\frac{4s\pi}{k}w^{2}\bigg{)}$
$\displaystyle=\bigg{(}1-\frac{8\pi s}{k}\bigg{)}^{-1/2}\exp\bigg{(}\frac{\pi
s^{2}k^{2}}{(k+2)^{2}(k-8\pi s)}\bigg{)}$
$\displaystyle\leq\exp\bigg{(}\frac{8\pi s}{k}+\frac{2\pi s^{2}}{k}\bigg{)}$
$\displaystyle\leq\exp(10\pi s^{2}/k).\qed$

Finally, we can prove Lemma 2.1

###### Proof of Lemma 2.1.

We may assume that $\delta\geq 2000/k$ since the statement for $\delta<2000/k$
follows from the statement for $\delta=2000/k$. Also, note that we may assume
that $\delta\leq\log 2$. For any $t\in\mathbb{R}$, we have

$\displaystyle\mathbb{P}_{\vec{x}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\geq
e^{tn}\bigg{]}$ $\displaystyle\leq|A|\sup_{\vec{a}\in
A}\mathbb{P}_{\vec{x}}\bigg{[}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\geq
e^{tn}\bigg{]}$ $\displaystyle\leq|A|\sup_{\vec{a}\in A}\inf_{s\geq
2}\exp(-stn)\mathbb{E}_{\vec{x}}\bigg{[}\bigg{(}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\bigg{)}^{s}\bigg{]}$
$\displaystyle=|A|\sup_{\vec{a}\in A}\inf_{s\geq
2}\exp(-stn)\prod_{i=1}^{n}\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{[}\bigg{(}\frac{\mathbb{P}[\operatorname{Bin}(k)=x-a_{i}]}{\mathbb{P}[\operatorname{Bin}(k)=x]}\bigg{)}^{s}\bigg{]}$
$\displaystyle\leq|A|\inf_{s\geq
2}\exp(-stn)\bigg{(}\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\bigg{)}^{n}.$

In the last line, we have used that

$\displaystyle\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{[}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\bigg{]}$
$\displaystyle\geq\bigg{(}\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{[}\frac{x^{2}}{(k+1-x)^{2}}\bigg{]}\bigg{)}^{s/2}$
$\displaystyle=\bigg{(}\sum_{\ell=0}^{k-1}\frac{\ell+1}{k-\ell}\binom{k}{\ell}2^{-k}\bigg{)}^{s/2}$
$\displaystyle=\bigg{(}\sum_{\ell=0}^{k-1}\bigg{(}\frac{k+2}{k}+\frac{4(k+1)(\ell-k/2)}{k^{2}}+\frac{(k+1)(k-2\ell)^{2}}{k^{2}(k-\ell)}\bigg{)}\binom{k}{\ell}2^{-k}\bigg{)}^{s/2}$
$\displaystyle\geq\bigg{(}\sum_{\ell=0}^{k-1}\bigg{(}\frac{k+2}{k}+\frac{4(k+1)(\ell-k/2)}{k^{2}}\bigg{)}\binom{k}{\ell}2^{-k}\bigg{)}^{s/2}$
$\displaystyle=\bigg{(}\frac{k+2}{k}-\frac{3k+4}{k}2^{-k}\bigg{)}^{s/2}$
$\displaystyle\geq 1$

if $k\geq 3$. Therefore, by Lemma 2.3, we have

$\displaystyle\mathbb{P}_{\vec{x}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\geq
e^{tn}\bigg{]}$ $\displaystyle\leq|A|\inf_{s\geq
2}\exp(-stn)\bigg{(}\mathbb{E}_{x\sim\operatorname{Bin}(k)}\bigg{(}\frac{x}{k+1-x}\bigg{)}^{s}\bigg{)}^{n}$
$\displaystyle\leq|A|\inf_{2\leq s\leq k/(16\pi)}\exp(-stn)\bigg{(}\exp(10\pi
s^{2}/k)+2k^{s}(4/5)^{k}\bigg{)}^{n}$ $\displaystyle\leq|A|\inf_{2\leq s\leq
k/(10\log k)}\exp(-stn)\bigg{(}\exp(12\pi s^{2}/k)\bigg{)}^{n}$
$\displaystyle\leq\begin{cases}|A|\exp\left(-\frac{kt^{2}n}{48\pi}\right)&\quad\text{
if }\sqrt{\frac{96\pi\delta}{k}}\leq t\leq(\log{k})^{-1}\\\
|A|\exp\left(-\frac{kn}{48\pi(\log{k})^{2}}\right)&\quad\text{ if
}(\log{k})^{-1}\leq t\leq\log{k}.\end{cases}$

Here, the second case follows by plugging in $s=k/(24\pi\log{k})$ and
simplifying (assuming $C_{\ref{lem:sup-ratio}}$ is large enough so $s\geq 2$),
and the first case follows from plugging in $s=kt/(24\pi)$ which satisfies
$2\leq s\leq k/(10\log{k})$ by the restriction on $t$ and $\delta$. Finally,
since

$0\leq\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\leq\left(\max_{\ell}\frac{\max\Big{\\{}\binom{k}{\ell-1},\binom{k}{\ell}\Big{\\}}}{\binom{k}{\ell}}\right)^{n}\leq
k^{n},$

we have

$\displaystyle\mathbb{E}_{\vec{x}}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\bigg{]}$
$\displaystyle=\int_{-\infty}^{\log k}\mathbb{P}\bigg{[}\sup_{\vec{a}\in
A}\frac{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}-\vec{a}]}{\mathbb{P}_{\vec{b}}[\vec{b}=\vec{x}]}\geq
e^{tn}\bigg{]}ne^{tn}dt$
$\displaystyle\leq\int_{1/\log{k}}^{\log{k}}\cdot+\int_{\sqrt{96\pi\delta/k}}^{1/\log{k}}\cdot+\int_{-\infty}^{\sqrt{96\pi\delta/k}}ne^{tn}dt$
$\displaystyle\leq
e^{\sqrt{96\pi\delta/k}n}+\int_{\sqrt{96\pi\delta/k}}^{1/\log
k}|A|\exp\bigg{(}-\frac{kt^{2}n}{48\pi}\bigg{)}ne^{tn}dt$
$\displaystyle\quad+\int_{1/\log k}^{\log
k}|A|\exp\bigg{(}-\frac{kn}{48\pi(\log k)^{2}}\bigg{)}ne^{tn}dt$
$\displaystyle\leq\exp\left(O(\sqrt{\delta/k})n\right)+\int_{\sqrt{96\pi\delta/k}}^{1/\log{k}}ne^{-tn}dt+1$
$\displaystyle\leq\exp\left(O(\sqrt{\delta/k})n\right).\qed$

## Acknowledgments

The authors are grateful to the anonymous reviewers for several suggestions
which helped improve the presentation of the paper.

## References

  * [1] Andreas Björklund, Thore Husfeldt, and Mikko Koivisto, _Set partitioning via inclusion-exclusion_ , SIAM Journal on Computing 39 (2009), no. 2, 546–563.
  * [2] Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, and Karol Węgrzycki, _A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics_ , pp. 1682–1701.
  * [3] Hoi Nguyen and Van Vu, _Optimal inverse Littlewood-Offord theorems_ , Adv. Math. 226 (2011), no. 6, 5298–5319. MR 2775902
  * [4] Mark Rudelson and Roman Vershynin, _The Littlewood–Offord problem and invertibility of random matrices_ , Advances in Mathematics 218 (2008), no. 2, 600–633.
  * [5] Terence Tao and Van H. Vu, _Inverse Littlewood–Offord theorems and the condition number of random discrete matrices_ , Annals of Mathematics (2009), 595–632.
  * [6] Mårten Wiman, _Improved constructions of unbalanced uniquely decodable code pairs_ , 2017, https://www.diva-portal.org/smash/get/diva2:1120593/FULLTEXT01.pdf.

[vj] Vishesh Jain
Department of Statistics, Stanford University
Stanford, California
visheshjstanfordedu
https://jainvishesh.github.io [as] Ashwin Sah
Department of Mathematics, Massachusetts Institute of Technology
Cambridge, Massachusetts
asahmitedu
http://www.mit.edu/~asah/ [ms] Mehtaab Sawhney
Department of Mathematics, Massachusetts Institute of Technology
Cambridge, Massachusetts
msawhneymitedu
http://www.mit.edu/~msawhney/