# Constructions in combinatorics via neural networks

Adam Zsolt Wagner School of Mathematical Sciences, Tel Aviv University, Tel
Aviv, Israel. Email<EMAIL_ADDRESS>
###### Abstract

We demonstrate how by using a reinforcement learning algorithm, the deep
cross-entropy method, one can find explicit constructions and counterexamples
to several open conjectures in extremal combinatorics and graph theory.
Amongst the conjectures we refute are a question of Brualdi and Cao about
maximizing permanents of pattern avoiding matrices, and several problems
related to the adjacency and distance eigenvalues of graphs.

##  1 Introduction

Computer-assisted proofs have a long history in mathematics, including
breakthrough results such as the proof of the four color theorem in 1976 by
Appel and Haken [7], and the proof of the Kepler conjecture in 1998 by Hales
[29]. Recently, significant progress has been made in the area of machine
learning algorithms, and they have have quickly become some of the most
exciting tools in a scientist’s toolbox. In particular, recent advances in the
field of reinforcement learning have led computers to reach superhuman level
play in Atari games [39] and Go [41], purely through self-play.

With these recent advances in mind, it is natural to wonder if there is any
way reinforcement learning algorithms could be used to find explicit
counterexamples to conjectures in combinatorics and graph theory, if we do not
give the algorithm any prior knowledge about the problems. Our aim is to
demonstrate that this approach could potentially be fruitful: while we did not
succeed in refuting any of the most famous conjectures in the field, we will
present counterexamples and constructions to a wide variety of lesser known
open problems.

In all applications, the agent starts the learning process with zero prior
knowledge about the problem itself. It generates a construction and receives a
feedback from a scoring function on how well it did. Repeating this process
many times, the agent eventually learns how to get a better score in this
‘game’. If this score is larger than the score of the conjectured best
construction, then we have succeeded in finding a counterexample to the
conjecture. An advantage of using reinforcement learning algorithms in this
manner is that we can use what is essentially the same exact program to try
and attack all mathematical conjectures which might have a finite
counterexample – the only thing we need to change in the code is the function
that calculates the score of a given construction.

There are several natural candidate reinforcement learning algorithms for this
task. In this work we are primarily focused on conjectures in graph theory,
and as an $n$-vertex graph can be represented by $\frac{n(n-1)}{2}$ binary
decisions, one for each edge, we will focus on algorithms that are well-suited
for problems with small action spaces. One may initially assume that the most
natural choice would be to use Deep Q-Networks and their variants, such as
Double Deep Q-Networks [49] and Dueling Deep Q-Networks [53], which have found
a lot of success in recent years. However, these methods take a long time to
train in our sparse reward setting, where we only give the agent feedback at
the very end of each session (so roughly at every $\frac{n^{2}}{2}$ steps if
we generate a graph edge-by-edge). While there are several ways to potentially
resolve this issue, such as giving some kind of artificial reward during the
sessions to guide the agent, doing so would introduce its own set of problems
and would defeat our goal of refuting conjectures without prior knowledge
about the problem.

With our limited computing resources, we have found significantly more success
with the algorithm called the _deep cross-entropy method_. While this
algorithm is not as famous than the above-mentioned Deep Q-Networks, it has
good convergence and appeared to be much less sensitive to choosing the right
hyperparameters. We will present some examples where this approach has
resulted in counterexamples and constructions that would have been difficult
to find by hand or with other programming methods. At the end of the paper we
also present two counterexamples that we found by applying LP solvers to
conjectures that can be formulated as linear programs.

The paper is organized as follows.

  * •

In Section 2 we present our results we obtained via the deep cross-entropy
method.

    * –

In §2.1 we give a short introduction to the cross-entropy method and describe
how we will use it to produce constructions to extremal combinatorics
problems.

    * –

In §2.2 we illustrate the method by finding counterexamples to a conjecture
about the sum of the largest eigenvalue and matching number of graphs, which
was proposed in [4].

    * –

In §2.3 we refute a similar conjecture of Aouchiche–Hansen [6] about the
distance spectrum and proximity of graphs.

    * –

In §2.4 we refute an old conjecture of Collins [18] by showing that the peaks
of the coefficient sequences of the adjacency and distance polynomials of
trees can be far apart.

    * –

In §2.5 we show that transmission regularity of graphs is not preserved under
cospectrality of the distance Laplacian, answering a question of Hogben and
Reinhart [31].

    * –

In §2.6 we address a problem of Brualdi and Cao [15] about maximizing the
permanent of an $n\times n$, 312-pattern avoiding binary matrix. Among others,
we find that the best possible answers for $n\leq 8$ are given by the rather
remarkable sequence

$1,\quad 2,\quad 4,\quad 8,\quad 16,\quad 32,\quad 64,\quad 120.$

  * •

In Section 3 we present two constructions obtained via LP solvers.

    * –

In §3.1 we refute a conjecture of Aaronson–Groenland–Grzesik–Kielak–Johnston
[2] about a problem of covering certain subsets of the hypercube with few
hyperplanes.

    * –

In §3.2 we answer a problem of Király–Nagy–Pálvölgyi–Visontai [32] about the
maximum size of weakly cross-intersecting set-pair systems.

##  2 Reinforcement learning and the cross-entropy method

Reinforcement learning methods have a long history of being used to tackle
complex combinatorial optimization problems. In recent years this area has
seen a myriad of new developments and scientific papers appearing. Often new
results are concerned with the following question: how is it possible to
tackle NP-hard problems, such as the traveling salesman problem, in practical
time? For a general overview we refer the reader to the numerous surveys
written in the past three years, such as [8, 27, 37, 50].

In the present paper we take a different approach. We will use reinforcement
learning methods to find explicit counterexamples to some conjectures in
combinatorics and graph theory. In this section we will present five examples
where this approach was successful. The common theme in these examples that we
chose to present is that the constructions found by the neural network are
non-trivial, and it is not clear how one could have found these by hand or by
relying only on more traditional programming methods.

There are a plethora of algorithms within reinforcement learning, here we will
focus on the so-called _deep cross-entropy method_ , which we will use in all
five applications to find the constructions. We will use a deep neural network
to approximate the policy, which determines what action we should take in a
given state. With the cross-entropy method, the neural network learns only to
predict which move is best in a given state, and does not explicitly learn a
value function for the states or state-action pairs. Given any state as an
input to the neural net, the output is a probability distribution on all the
possible moves in that state, with higher probability assigned to the moves
that the agent thinks are best.

In this work we will only give a basic description of the cross-entropy method
and focus on how we applied this method in practice to find the constructions.
For a basic introduction to neural networks, and a thorough description of the
theoretical background of the cross-entropy method and of various practical
considerations when applying it, we refer the reader to the recent book [35,
Chapter 4].

###  2.1 Applying the cross-entropy method to problems in extremal
combinatorics

Our very first step in attacking an extremal problem is to find a good way to
encode constructions as words. Given a combinatorial problem, we can often
easily translate it to a problem about generating a word of certain length
from a finite alphabet. For example, if our task is to find a large antichain
in the Boolean lattice $\\{0,1\\}^{n}$ then the answer can be represented by a
0-1 string of length $2^{n}$, where the $i$-th bit is one precisely if the
$i$-th element in some linear ordering of $\\{0,1\\}^{n}$ is included in the
antichain. Similarly, generating $n$-vertex graphs is equivalent to generating
0-1 sequences of length $\frac{n(n-1)}{2}$; trees on $n$ vertices can be
represented by their Prüfer codes as words of length $n-2$ on an alphabet of
size $n$, and so on.

We will generate constructions with the neural network as follows. We first
ask it to predict what the best first letter should be. The output is a
probability distribution on the alphabet, from which we can sample an element
randomly and feed it back into the network to ask what the best second letter
is. In general, having generated the letters $a_{1},a_{2},\ldots,a_{k-1}$, we
can feed this partial word on $k-1$ letters into the network to get a
probability distribution on the best next letter to use, conditioned on our
previous $k-1$ decisions, and sample from it randomly to obtain $a_{k}$.

Figure 1: We are generating a graph, and so far the network has included edges
1,2,3,6, and rejected edges 4,5 (dotted), corresponding to the sequence
111001. We input this into the neural network to get a probability
distribution on whether to include or reject the next edge.

Initialize a neural network;

while  _the best construction found is not a counterexample_ do

for  _$i\leftarrow 1$ to $N$_ do

$w\leftarrow$ empty string;

while  _not terminal_ do

Input $w$ into the neural net to get a probability distribution $F$ on the
next letter;

Sample next letter $x$ according to $F$;

$w\leftarrow w+x$;

end while

end for

Evaluate the score of each construction;

Sort the constructions according to their score;

Throw away all but the top $y$ percentage of the constructions;

for  _all remaining constructions_ do

for  _all (observation, issued action) pairs in the construction_ do

Adjust the weights of the neural net slightly to minimize the cross-entropy
loss between issued action and the corresponding predicted action probability;

end for

end for

Keep the top $x$ percentage of constructions for the next iteration, throw
away the rest;

end while

Algorithm 1 The deep cross-entropy method

The network receives feedback only when a session finishes, i.e. when we have
created the entire word. The feedback is given by a reward function that the
neural network has no knowledge about and treats as a black box. This reward
function is unique to every problem. When trying to create large antichains
the reward might be the number of elements in the family minus the number of
comparable pairs in it; when aiming to create a graph with a large third
eigenvalue it might simply be the third eigenvalue, etc. This reward at the
end of each session is the only feedback the network receives: at no point
does it have any knowledge on what problem it is trying to solve and how the
reward is calculated.

In every iteration we generate a large number of random sessions
(constructions) following the above method. We calculate the reward for each,
and throw away all but the top $y$ percentile. Next we let the neural network
learn from the remaining sessions, meaning that we adjust the weights of the
neural network a little bit to make it more likely to output moves that were
used in the best performing sessions. The idea of this is to reinforce our
neural network to carry out those actions that have led to good rewards.

Note that in most implementations of the cross-entropy method found online, at
the end of each iteration either all sessions are discarded, or the top few
sessions are kept alive for a few more iterations. In some cases we had better
success by letting the top few sessions survive indefinitely, until they are
outperformed by other sessions. This change was implicitly suggested in [46],
where they recommend a similar modification when the number of successful
sessions is small.

The implementation of the input is as follows. When generating $n$-vertex
graphs the input is two vectors of length $\frac{n(n-1)}{2}$. The first vector
has a 1 in all positions that correspond to edges that the agent has decided
to take, and it has a 0 in all the places that the agent has rejected, or not
considered yet. The second vector has a 0 in every position, except for the
one position that corresponds to the edge that is currently being considered,
where it has a 1. The purpose of the second vector is so that the agent can
figure out which edge it is currently making a verdict on. In all applications
where we generate a binary string, the neural network has three hidden layers
with 128, 64 and 4 neurons respectively. The learning rate is chosen
experimentally to strike a balance between the speed of convergence and
avoiding getting stuck in suboptimal constructions.

This representation of the input as two one-dimensional vectors and the use of
a sequential network of dense layers makes this a simple, multi-purpose setup
to use. For specific problems, for example when the task is to construct
graphs with certain properties, other input formats and networks architecture
such as graph neural networks could be considered. See [17] and the book [30]
for an overview of the recent applications of graph neural networks for
combinatorial optimization problems. For the related problem of having to
generate a graph that looks similar to a fixed target collection of graphs,
other generative models are discussed in the survey [54]. In particular,
Generative Adversarial Networks were used in [10] where the graphs were
constructed via random walks, and in [20] where the authors predict the
adjacency matrix at once, and utilize a permutation-invariant discriminator
for the vertex set.

The full Python code used in Sections 2.2 and 2.3 is available here: [51].

###  2.2 Example: the sum of matching number and largest eigenvalue of graphs

We will use the following conjecture appearing in [4] to illustrate our
method.

######  Conjecture 2.1 ([4]).

Let $G$ be a connected graph on $n\geq 3$ vertices, with largest eigenvalue
$\lambda_{1}$ and matching number $\mu$. Then

$\lambda_{1}+\mu\geq\sqrt{n-1}+1.$

Conjecture 2.1 was originally obtained using AutoGraphiX [16], a software that
can be used to find conjectures about relations between various graph
parameters in an automated way. After we have found a counterexample with our
method, we have learned that Conjecture 2.1 has already been disproved by
Stevanović [44]. Nevertheless, we can use this conjecture to demonstrate how
simple it can be to find constructions with the cross-entropy method. The
counterexample given in [44] has $n=600$ vertices, but we can use our methods
to find a smaller explicit counterexample.

We used the cross-entropy method with $n=19$, where the reward function we use
is simply $\lambda_{1}+\mu$, which we will try to minimize. Figure 2 shows how
the average reward of the top 10% of sessions of each iteration evolves over
time.

Figure 2: The average value of $\lambda_{1}+\mu$ of the best 10% of the
sessions in each iteration decreases over time. After 5000 iterations it goes
slightly below the conjectured threshold of $\sqrt{19-1}+1$, meaning we have
found a counterexample to Conjecture 2.1.

Figure 3: The evolution of the best construction over time. The network
quickly realizes that sparse graphs are best, and eventually the “balanced
double star” structure emerges.

What is remarkable about Conjecture 2.1 is that it appears to be true for
$n\leq 18$ – the smallest counterexample we could find is for $n=19$, depicted
in Figure 4. It has largest eigenvalue $\sqrt{10}$ and matching number 2, so
$\lambda_{1}+\mu\approx 5.16<5.24\approx\sqrt{19-1}+1.$ Figure 3 shows how the
best sessions evolved as the number of iterations increased. While there is a
significant run-to-run variation, it typically takes a few hours on an average
PC for the program to find the counterexample.

Figure 4: A graph on 19 vertices satisfying $\lambda_{1}+\mu<\sqrt{n-1}+1$.

It is easy to see that trees are the best counterexample candidates for
Conjecture 2.1. Indeed, given a graph $G$ with largest matching $M$, we can
repeatedly delete edges from $E(G)\setminus M$ without disconnecting the
graph. Doing so does not change $\mu(G)$ but decreases the largest eigenvalue.
Interestingly, as seen in Figure 3, the network also quickly figures out that
trees are best, after which it starts decreasing the diameter and converges to
the graph in Figure 4.

###  2.3 A conjecture about the proximity and distance eigenvalues of graphs

Let $G$ be an $n$-vertex graph. Given an ordering of $V(G)$ as
$\\{v_{1},v_{2},\ldots,v_{n}\\}$, the _distance matrix_ $D(G)$ of $G$ is the
$n\times n$ matrix which has $(i,j)$ entry equal to $d(v_{i},v_{j})$, where
$d(v,w)$ denotes the length of the shortest path between $v$ and $w$ in $G$.
The _distance eigenvalues_ of $G$ are the eigenvalues
$\partial_{1}\geq\ldots\geq\partial_{n}$ of $D(G)$.

The study of the spectral properties of the distance matrix has a long
history, reaching back to at least the 70s. Graham and Pollack [26] studied
the connections between the distance eigenvalues of graphs and a problem in
data communication systems and proved, among others, that the determinant of
the distance matrix of a tree only depends on the order of the tree.

######  Theorem 2.2 (Graham-Pollack [26]).

If $T$ is a tree on $n$ vertices with distance matrix $D(T)$, then

$\mathrm{det}(D(T))=(-1)^{n-1}(n-1)2^{n-2}.$

We will talk more about the spectral properties of the distance matrix of
trees in Section 2.4. Motivated by our success in the previous subsection, we
will try to disprove a conjecture that is of a very similar flavor to
Conjecture 2.1. Given a connected graph $G$ with $n$ vertices, define its
_proximity_ $\pi$ as

$\pi=\frac{1}{n-1}\cdot\min_{v\in V(G)}\sum_{w\in V(G)}d(v,w).$

Note that $\pi\geq 1$. Merris [38] showed that for every connected graph with
diameter $D$ we have
$\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{D}{2}}\right\rfloor}>-1$
and hence

$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{D}{2}}\right\rfloor}>0.$

We will use our methods to refute the following conjecture by Aouchiche and
Hansen [6], that would have been a strengthening of the above result:

######  Conjecture 2.3 (Auchiche–Hansen [6]).

Let $G$ be a connected graph on $n\geq 4$ vertices with diameter $D$,
proximity $\pi$ and distance spectrum
$\partial_{1}\geq\ldots\geq\partial_{n}$. Then

$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor}>0.$

Our strategy for refuting Conjecture 2.3 will be the exact same as with
Conjecture 2.1. The only change will be the reward function: we change
$\lambda_{1}+\mu$ to
$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor}$.
Running the algorithm with $n=30$, after a few days the neural network finds
the graph depicted in Figure 5.

Figure 5: The graph on 30 vertices with smallest value of
$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor}$
found by the network. It has
$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor}\approx
0.4$ so it is not quite a counterexample to Conjecture 2.3, but it tells us
very clearly what counterexamples could look like.

The graph in Figure 5 is likely not optimal for $n=30$: the best graph was
still changing when we aborted the algorithm. The reason we chose to terminate
the learning process is because we noticed that at this stage, every single
graph in the top 10% of an iteration had essentially the same structure: a
long path with a star near its middle, whose neighborhood is partitioned into
disjoint cliques. The only thing that varied was the size of these cliques,
and having cliques of sizes 2 and 3 for example was ever so slightly better
than having some cliques of size 1.

Hence, even though the graph in Figure 5 is not quite a counterexample to
Conjecture 2.3, it gives us a very clear indication on what the structure of
graphs minimizing
$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor}$
potentially looks like. Given this information, we can simply increase the
number of vertices and vary the clique sizes in this construction until we
eventually find a counterexample, seen in Figure 6.

190 leaves Figure 6: A counterexample to Conjecture 2.3.

This counterexample is constructed by taking a path on 13 vertices, and
attaching $n$ pendant vertices to a vertex adjacent to its midpoint. This
graph has diameter 12, and it can be verified by a computer that as soon as
$n\geq 190$, this graph satisfies $\pi+\partial_{8}<0$. We note that this type
of graph has already appeared in [6] and [5], where they were called _double-
tailed comets_ , and were shown to minimize the proximity over the class of
trees with a given order and diameter, and used as examples to show that
$\pi+\partial_{\mathopen{}\mathclose{{}\left\lfloor\frac{2D}{3}}\right\rfloor+1}$
need not always be positive. From our limited computer experiments it seems
plausible that our graph on 203 vertices is in fact (close to being) the
smallest counterexample to Conjecture 2.3.

###  2.4 The peaks of distance and adjacency polynomials of trees can be far
apart

Given a tree $T$ on vertex set $\\{1,2,\ldots,n\\}$, denote its adjacency
matrix by $A(T)$. Its distance matrix $D(T)$ has $(i,j)$ entry equal to the
graph-theoretic distance of vertices $i$ and $j$. Consider $CPD(T)$, the
characteristic polynomial of the distance matrix:

$CPD(T)=\det(D(T)-xI)=\sum_{k=0}^{n}\delta_{k}x^{k}.$

In [1], the coefficients $d_{k}=\frac{2^{k}}{2^{n-2}}|\delta_{k}|$ are called
the _normalized coefficients_ of the characteristic polynomial of the distance
matrix of $T$. Graham and Lovász [25] conjectured that for any tree $T$, the
sequence of normalized coefficients $d_{0}(T),\ldots,d_{n-2}(T)$ is unimodal
and the peak (i.e. maximum) occurs precisely at index
$\lfloor\frac{n}{2}\rfloor$.

The conjecture regarding the location of the peak was disproved by Collins
[18] who showed that for paths the peak is at index approximately
$\mathopen{}\mathclose{{}\left(1-\frac{1}{\sqrt{5}}}\right)n$. In [1] the
authors confirmed the other part of the Graham-Lovász conjecture by proving
that the sequence of normalized coefficients $d_{0}(T),\ldots,d_{n-2}(T)$ is
indeed always unimodal – in fact, they proved the stronger statement that this
sequence is _log-concave_.

Collins [18] considered the characteristic polynomial $CPA(T)$ of the
adjacency matrix of trees. By ignoring the terms with zero coefficients,
$CPA(T)$ can be written in the form $CPA(T)=\sum_{i=0}^{m}a_{i}x^{\alpha_{i}}$
where $\alpha_{0}<\alpha_{1}<\ldots<\alpha_{m}$ and $a_{i}\neq 0$ for all $i$.
Collins observed that for the path, $CPA(T)$ has
$m=\lfloor\frac{n}{2}\rfloor+1$ non-zero coefficients whose absolute values
form a unimodal sequence with peak at around index $i=\frac{1}{2\sqrt{5}}n$.
So the ratio of the position of the peak index to the number of terms in the
sequence is also $1/\sqrt{5}$, just like for the distance matrix!

Given a tree $T$, denote by $p_{A}(T)$ the position of the peak index of the
absolute values of the non-zero coefficients of $CPA(T)$, and denote by
$p_{D}(T)$ the index of the peak of the normalized coefficients of $CPD(T)$.
Let $m(T)$ denote the number of non-zero coefficients of $CPA(T)$ and $n(T)$
the number of terms in $CPD(T)$ (which is just the number of vertices of $T$
plus one). What the above results say precisely, is that for the path $P_{n}$
we have

$\lim_{n\rightarrow\infty}\frac{p_{D}(P_{n})}{n(P_{n})}=\lim_{n\rightarrow\infty}\mathopen{}\mathclose{{}\left(1-\frac{p_{T}(P_{n})}{m(P_{n})}}\right)=1-\frac{1}{\sqrt{5}}.$

That is, the two peaks in the case of the path are in the “same” place (when
counting the location of the peak from opposite ends of the two sequences of
coefficients). Motivated by this, and that this equality holds for the star as
well, Collins [18] made the following conjecture:

######  Conjecture 2.4 (Collins [18]).

The sequence of absolute values of the non-zero coefficients of $CPA(T)$ form
a unimodal sequence, and its peak is at the same place as the peak of the
normalized coefficients of $CPD(T)$.

We shall only focus on the conjecture regarding the location of the peaks, and
disprove it in a strong sense. We represent trees using their Prüfer codes as
words of length $n-2$ from an alphabet of size $n$. By optimizing the reward
function
$f(T)=\bigg{|}\frac{p_{A}(T)}{m(T)}-\mathopen{}\mathclose{{}\left(1-\frac{p_{D}(T)}{n(T)}}\right)\bigg{|}$
using the cross-entropy method, we find that the tree on $48$ vertices in
Figure 7 has $\frac{p_{D}(T)}{n(T)}=\frac{1}{2}$ and
$\frac{p_{A}(T)}{m(T)}=\frac{1}{7}$.

Figure 7: The tree $T$ on $48$ vertices found by the network, where the two
peaks of the polynomials are furthest apart. It has
$\frac{p_{A}(T)}{m(T)}=\frac{1}{7}$ and $\frac{p_{D}(T)}{n(T)}=\frac{1}{2}$.
Observe that it has six high degree vertices, and every edge in the tree is
adjacent to at least one of these six vertices.

Once we know what the extremal examples approximately look like, the following
theorem is much easier to prove. It refutes Collins’s conjecture in a strong
sense.

######  Theorem 2.5.

There exists an infinite sequence of trees $(T_{k})_{k\in\mathbb{N}}$
satisfying

$\lim_{k\rightarrow\infty}n(T_{k})=\lim_{k\rightarrow\infty}m(T_{k})=\infty,$

such that $f(T_{k})\geq 0.3$ for all $k\in\mathbb{N}$.

Theorem 2.5 shows that even if we assume that the two sequences have lots of
non-zero entries, the two peaks can be very far apart. This avoids issues
about when $m(T)$ is small, and it is somewhat ambiguous what one means with
the ratio of the peak index. Note that for example when $T$ is a star, then
$CPA(T)$ only has two non-zero entries [18].

Let $n,d\geq 3$ be integers such that $d|n$. Let $T_{n,d}$ be obtained by
first taking a path on $d$ vertices, and attaching $\frac{n-d}{d}$ leaves to
each vertex. We show that if $d$ is an arbitrary constant and $n$ is
sufficiently large compared to $d$, then the non-zero coefficients of
$CPA(T_{n,d})$ form a monotone sequence, so their peak is as far from the
halfway point as possible.

######  Proposition 2.6.

If $n\geq d^{2}$ then $\frac{p_{A}(T_{n,d})}{m(T_{n,d})}=\frac{1}{d+1}$.

###### Proof.

Recall the fact (see e.g [19]) that we can describe the characteristic
polynomial of the adjacency matrix of a tree in terms of the number of
different-sized matchings in the tree:

$a_{n-k}=\begin{cases}(-1)^{n+k/2}\cdot N_{\frac{1}{2}k}(T)&\mbox{if }k\text{
even,}\\\ 0&\mbox{otherwise.}\end{cases}$

Here $N_{i}(T)$ denotes the number of matchings of size $i$ in $T$. Observe
that the largest matching in $T_{n,d}$ has size $d$, and so $CPA(T_{n,d})$ has
$d+1$ non-zero coefficients, one of them corresponding to the empty matching.
For every $0\leq k\leq d$ we have the following easy bounds on the
coefficients:

$\binom{d}{k}\mathopen{}\mathclose{{}\left(\frac{n-d}{d}}\right)^{k}\leq|a_{n-2k}|\leq\binom{d}{k}\mathopen{}\mathclose{{}\left(\frac{n-d}{d}+2}\right)^{k}.$

The lower bound comes from only counting those $k$-matchings where every edge
of the matching meets the path we used when constructing $T_{n,d}$ in
precisely one of its $d$ vertices. For the upper bound, observe that every
edge in the tree is adjacent to the path on $d$ vertices used in the
construction, and every vertex on this path has at most $\frac{n-d}{d}+2$
edges.

It follows that if $n\geq d^{2}-d+1$ then the sequence of absolute values of
coefficients is strictly decreasing. Thus the peak is at very first index,
i.e. $a_{n-2d}$, and we have
$\frac{p_{A}(T_{n,d})}{m(T_{n,d})}=\frac{1}{d+1}$. ∎

It remains to bound the peak of the distance coefficients. While the
coefficients of the adjacency polynomial only depend on the number of
matchings of certain sizes in the tree, calculating the coefficients of the
distance polynomial is significantly more involved (see [25]). It seems that
when $n$ is large enough compared to $d$, we always have
$\frac{p_{D}(T_{n,d})}{n(T_{n,d})}=\frac{\lfloor
n/2\rfloor}{n}\approx\frac{1}{2}$. We do not know how to prove this. Instead
we will use a result from [1], which states that
$p_{D}(T)\leq\lceil\frac{2}{3}n(T)\rceil$ for every tree $T$.

###### Proof of Theorem 2.5.

Consider the sequence of trees $T_{d^{2},d}$ with $d=31,32,\ldots$. By
Proposition 2.6, for each of these trees we have
$\frac{p_{A}(T_{d^{2},d})}{m(T_{d^{2},d})}=\frac{1}{d+1}$. By the sentence
preceding this proof, we have
$\frac{p_{D}(T_{d^{2},d})}{n(T_{d^{2},d})}\leq\frac{2}{3}+\frac{1}{n(T_{d^{2},d})}$.
As $n(T_{d^{2},d})=d^{2}+1$ and as seen in the proof of Proposition 2.6 we
also have $m(T_{d^{2},d})=d+1$, both $n(T_{d^{2},d})$ and $m(T_{d^{2},d})$ go
to infinity as $d$ increases, as required. The distance between the peaks
satisfies

$f\mathopen{}\mathclose{{}\left(T_{d^{2},d}}\right)\geq
1-\frac{1}{d+1}-\frac{2}{3}-\frac{1}{d^{2}+1}\geq 0.3$

for all $d\geq 31.$ ∎

Note that it is not necessarily the case that the trees $T_{n,d}$ maximize the
distance of the peaks, for a given number of vertices. One counterexample to
this is at $n=30$. The tree in Figure 8 has $f(T)=\frac{1}{3}$, which is
strictly larger than $f(T_{30,d})$ for any $d$. The reason is that the tree on
the left has more 5-matchings (4705) than 4-matchings (4601), whereas this is
not the case for e.g. $T_{30,5}$ (where the corresponding numbers are 3125 and
3625).

Figure 8: The tree $T$ on the left has $f(T)=\frac{1}{3}$. For $T_{30,5}$ on
the right, we have $f(T_{30,5})=\frac{1}{6}$.

There are many things that are still not known about the location of the peaks
of various tree polynomials. We mention only one open conjecture in the area,
attributed to Peter Shor. Note that the lower bound corresponds to the star
and the upper bound to the path.

######  Conjecture 2.7 (Shor [18]).

For any tree on $n$ vertices, the peak $p_{D}(T)$ satisfies

$\Big{\lfloor}\frac{n}{2}\Big{\rfloor}\leq
p_{D}(T)\leq\Bigg{\lceil}n\mathopen{}\mathclose{{}\left(1-\frac{1}{\sqrt{5}}}\right)\Bigg{\rceil}.$

###  2.5 Transmission regularity and the distance Laplacian

We continue our study of the spectrum of various graph matrices associated to
graphs. We will consider the following question: what information about the
graph can be recovered from the spectrum of such a matrix? Here we will focus
on the _distance Laplacian_ of $G$, denoted by $\mathcal{D}^{L}(G)$.

Given a connected graph $G$ with vertex set $V(G)=\\{v_{1},\ldots,v_{n}\\}$,
we denote by $t(v_{i})=\sum_{u\in V(G)}d(v_{i},u)$ the _transmission of vertex
$v_{i}$_, i.e. the sum of distances from $v_{i}$ to all other vertices in $G$.
We say that $G$ is _transmission regular_ if $t(v_{i})=t(v_{j})$ for all
$i,j$. Let $T(G)$ be the diagonal matrix with entries
$\\{t(v_{i}):i\in[n]\\}$, and let $D(G)$ be the distance matrix of $G$ with
$i,j$-entry equal to $d(v_{i},v_{j})$. The distance Laplacian is then defined
as $\mathcal{D}^{L}(G)=T(G)-D(G)$. Denote the spectrum of
$\mathcal{D}^{L}(G)$, i.e. the multiset of its eigenvalues, by
$\text{spec}_{\mathcal{D}^{L}}(G)$.

Given a graph property $\mathcal{P}$ , we say $\mathcal{P}$ is preserved by
$\mathcal{D}^{L}$-cospectrality if
$\text{spec}_{\mathcal{D}^{L}}(G)=\text{spec}_{\mathcal{D}^{L}}(H)$ implies
$\mathcal{P}(G)=\mathcal{P}(H)$. A natural question to ask is which graph
properties are preserved by $\mathcal{D}^{L}$-cospectrality?

This question has a long history, for an overview on the extensive research on
this topic we refer the reader to the recent survey [31] and the references
therein, in particular [14]. Hogben–Reinhart [31] put a lot of emphasis on the
spectral properties of transmission regular graphs – indeed, as shown in Table
7.2 in their survey, it is the last of the natural graph properties considered
in [31] for which is not known whether it is preserved by
$\mathcal{D}^{L}$-cospectrality.

Our main result in this section is to fill in this gap, by showing that
transmission regularity is not preserved by $\mathcal{D}^{L}$-cospectrality.
That is, there exist graphs $G,H$ such that $G$ is transmission regular, $H$
is not transmission regular, and
$\text{spec}_{\mathcal{D}^{L}}(G)=\text{spec}_{\mathcal{D}^{L}}(H)$. Such two
graphs can be seen in Figure 9. The characteristic polynomials of their
distance Laplacians are the same, they are given by
$x^{12}-216x^{11}+21188x^{10}-1245904x^{9}+48797440x^{8}-1336652544x^{7}+26129121472x^{6}-364516883456x^{5}+3556516628224x^{4}-23113129559040x^{3}+90045806284800x^{2}-159318669312000x$.

Figure 9: The graph on the left is transmission regular, whereas the graph on
the right is not. The characteristic polynomials of their distance Laplacians
are the same, so they are $\mathcal{D}^{L}$-cospectral.

The construction is not unique. There are many different ways one can design a
reward function to use with the cross-entropy method in order to try to
produce a cospectral pair of graphs as in Figure 9. None of the reward
functions we tried performed particularly well, in the end it seemed more of a
coincidence that some of the runs of the algorithm stumbled upon a
construction. It is likely that other algorithms are much better suited for
this problem.

###  2.6 The permanent of 312-pattern avoiding 0-1 matrices

Pattern avoidance, and permutation avoidance in particular, is a central topic
in combinatorics. In recent decades the study of permutation patterns has
become a discipline in its own right, with hundreds of published papers. For
an overview, we refer the reader to the books [12, 33], surveys [42, 43], and
the many applications in Tenner’s database [45].

Given a positive integer $n$, denote by $S_{n}$ the set of permutations of
$[n]=\\{1,2,\ldots,n\\}$. Let $\sigma\in S_{n}$ and $\tau\in S_{k}$ for some
integers $k\leq n$. We say the permutation $\sigma$ _contains the pattern_
$\tau$ if there exist integers $1\leq x_{1}\leq x_{2}\leq\ldots\leq x_{k}\leq
n$ such that for $1\leq i,j\leq k$ we have

$\sigma(x_{i})<\sigma(x_{j})\text{ if and only if }\tau(i)<\tau(j);$

otherwise, we say $\sigma$ _avoids_ $\tau$. Denote by $S_{n}(\tau)$ the set of
$\sigma\in S_{n}$ that avoid $\tau$.

The above definition can be extended to 0-1 matrices as well. Let $A$ and $P$
be 0-1 matrices. We say that $A$ _contains_ the $k\times\ell$ matrix
$P=(p_{ij})$ if there exists a $k\times\ell$ submatrix $D=(d_{ij})$ of $A$
with $d_{ij}\geq p_{ij}$ for all $i,j$; otherwise we say that $A$ _avoids_
$P$.

To any permutation $\sigma\in S_{n}$ we can associate a permutation matrix,
which is the $n\times n$ 0-1 matrix with ones precisely in positions
$(i,\sigma(i))$ for $i=1,2,\ldots,n$. We say a matrix $A$ _avoids_ $\sigma$ if
$A$ avoids the permutation matrix associated with $\sigma$.

Figure 10: The pattern 312

For a 0-1 matrix $P$ let $f(n,P)$ be the maximum number of $1$-entries in an
$n\times n$ 0-1 matrix avoiding $P$. Füredi and Hajnal conjectured [24] that
for all permutation matrices $P$ we have $f(n,P)=O(n)$. A cornerstone result
of Marcus and Tardos [36] is that the Füredi–Hajnal conjecture is true. By a
result of Klazar [34], this also implied the celebrated Stanley-Wilf
conjecture, which states that for all permutations $\tau$ there exists a
constant $c_{\tau}$ such that $|S_{n}(\tau)|\leq c_{\tau}^{n}$. A breakthrough
result by Fox [22] shows that $c_{\tau}=2^{k^{\theta(1)}}$ for almost all
$\tau\in S_{k}$.

The _permanent_ of an $n\times n$ matrix $A$ is defined as

$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}a_{i,\sigma(i)}.$

Observe that if $J_{n}$ is the $n\times n$ matrix with all 1 entries and we
restrict the sum to $S_{n}(\tau)$ then the resulting permanent is equal to
$|S_{n}(\tau)|$. Perhaps motivated by this observation, Brualdi and Cao asked
the following beautiful question. Let $M_{n}(\sigma)$ denote the set of
$n\times n$ 0-1 matrices that avoid $\sigma$.

######  Question 2.8 (Brualdi–Cao [15]).

Given an integer $n$ and a permutation $\sigma$, what is the value of

$f_{\sigma}(n)=\max\\{\text{per}(A):A\in M_{n}(\sigma)\\}?$

Brualdi and Cao observed that this question is already interesting when
$\sigma\in S_{3}$ is a permutation on 3 elements. They guessed that the answer
to Question 2.8 when $\sigma=312$ is given by the following matrix,
illustrated here for $n=5$:

$\begin{bmatrix}1&1&1&0&0\\\ 1&1&1&1&0\\\ 1&0&1&1&1\\\ 1&0&0&1&1\\\
1&0&0&0&1\\\ \end{bmatrix}$

For $n=5$ this matrix has permanent 12, and in general the permanent is given
by the $(n+2)$-th Fibonacci number minus one.

By using the cross-entropy method together with some ad hoc methods we managed
to find better constructions giving improved lower bounds for $f_{312}(n)$,
disproving the above guess of Brualdi–Cao. These constructions can be seen in
Figure 11. We believe these are optimal up to at least $n=10$, but we only
have a computer-assisted proof showing their optimality for $n\leq 8$. This
proves that the sequence $f_{312}(n)$ has the unexpected initial segment

$1,\quad 2,\quad 4,\quad 8,\quad 16,\quad 32,\quad 64,\quad 120.$

These constructions are, for most values of $n$, not unique. The neural
network-based approach performed well by itself for about $n\leq 10$, but for
larger $n$ the numerous calculations of matrix permanents inherent to the
cross-entropy method proved too expensive. For $n=11,12$ we used ad hoc
methods to improve the constructions given by the algorithm. The construction
for $n=13$ was found under the very strong assumption that it should look
similar to the previous matrices, and it is likely not optimal. It is
generally believed that the permanent cannot be computed in polynomial time,
as a seminal result of Valiant [48] shows that computing the permanent of 0-1
matrices is #P-complete. We do not know if there is a fast algorithm for
computing the permanent if the 0-1 matrix is assumed to be 312-avoiding.

$\text{per}\mathopen{}\mathclose{{}\left(A_{1}}\right)=1$

$\text{per}\mathopen{}\mathclose{{}\left(A_{2}}\right)=2$

$\text{per}\mathopen{}\mathclose{{}\left(A_{3}}\right)=4$

$\text{per}\mathopen{}\mathclose{{}\left(A_{4}}\right)=8$

$\text{per}\mathopen{}\mathclose{{}\left(A_{5}}\right)=16$

$\text{per}\mathopen{}\mathclose{{}\left(A_{6}}\right)=32$

$\text{per}\mathopen{}\mathclose{{}\left(A_{7}}\right)=64$

$\text{per}\mathopen{}\mathclose{{}\left(A_{8}}\right)=120$

$\text{per}\mathopen{}\mathclose{{}\left(A_{9}}\right)=225$

$\text{per}\mathopen{}\mathclose{{}\left(A_{10}}\right)=424$

$\text{per}\mathopen{}\mathclose{{}\left(A_{11}}\right)=795$

$\text{per}\mathopen{}\mathclose{{}\left(A_{12}}\right)=1484$

$\text{per}\mathopen{}\mathclose{{}\left(A_{13}}\right)=2809$

Figure 11: The best constructions we found for Question 2.8, with
$\sigma=312$. Dark squares denote ones and light squares denote zeros.

It is clear that the matrices in Figure 11 have some kind of pattern – a large
main branch going diagonally with some smaller branches coming out of it in
the other direction – but it is not at all clear what this pattern exactly is
and what the limiting shape is as $n$ grows to infinity.

Given two 0-1 square matrices $A$ and $B$, we define $A\ast B$ and $A\circ B$
to be the the matrices obtained from the direct sum of $A$ and $B$, by turning
four zeros into ones as in Figure 12. It is easy to verify that if $A$ and $B$
are 312-avoiding, then so are $A\ast B$ and $A\circ B$. Note that it is not
the case that every matrix in Figure 11 can be obtained by starting from the
$1\times 1$ identity matrix, and applying these two operations repeatedly in
some order; the first instance of this is at $n=10$, where the largest
permanent one can obtain this way has value 394. We can use these operations
(or in fact just the matrix direct sum operation) to give a simple lower bound
on $f_{312}(n)$:

$A$$B$$A\ast B=$

$A$$B$$A\circ B=$

Figure 12: The definition of $A\ast B$ and $A\circ B$. They are both formed
from the direct sum of $A$ and $B$, by turning the four zeros indicated by the
dark squares into ones.

######  Proposition 2.9.

$2^{0.89n}\leq f_{312}(n)\leq 24^{n/4}\approx 2^{1.15n}$

###### Proof.

For the upper bound we can use the Brègman–Minc theorem [13], which states
that the permanent of an $n\times n$ 0-1 matrix $A=(a_{ij})$ with row sums
$r_{i}=a_{i1}+\ldots+a_{in}$ for $i=1,\ldots,n$ can be estimated by

$\text{per}(A)\leq\prod_{i=1}^{n}(r_{i}!)^{1/r_{i}}.$

An $n\times n$ binary matrix without a 312 pattern can have at most $4n-4$
ones, see e.g. [15]. The above formula is maximized when all $r_{i}$-s are as
equal as possible, this yields the bound in the proposition as $4!=24$.

For the lower bound, observe that for $A_{8}$ as in Figure 11, we have
$\text{per}\mathopen{}\mathclose{{}\left(A_{13}}\right)=2809>2^{0.88\cdot
13}$. As $\text{per}(A\ast B)\geq\text{per}(A)\cdot\text{per}(B)$ for any
$A,B$, this implies that $f_{312}(n+m)\geq f_{312}(n)\cdot f_{312}(m)$ for any
integers $m,n\geq 1$. Hence $g(n):=\log_{2}(f_{312}(n))$ is a superadditive
sequence. By Fekete’s lemma [21] the limit
$\lim_{n\rightarrow\infty}\frac{g(n)}{n}$ exists and is equal to
$\sup\frac{g(n)}{n}$ which is at least $\frac{g(13)}{13}\geq 0.88$. The better
bound of $0.89$ comes from the calculation $\text{per}(A_{13}\circ
A_{11})=5113196>2^{0.89\cdot 25}$. ∎

It would be interesting to determine the constant $c$ such that
$f_{312}(n)=c^{n(1+o(1))}$, and the shape of the optimal constructions as
$n\rightarrow\infty$.

##  3 Finding constructions with LP solvers

Many problems in extremal combinatorics can be phrased as linear programs.
When this is the case, LP solvers can outperform more general machine learning
algorithms, hence LP solvers can be extremely useful for quickly checking
conjectures for the existence of small counterexamples. In this section we
will present two counterexamples we have obtained this way. The first one is
an interesting covering problem in the hypercube, where the authors made the
very natural conjecture that embedding the problem in more dimensions cannot
make it easier. The second one concerns a conjecture that is closely related
to the classical set-pair system inequality of Bollobás.

Throughout this section we will use the methods of [52] to set up the problems
as linear programs, and the LP solver Gurobi [28].

###  3.1 An exact covering problem in the hypercube

A vector $a\in\mathbb{R}^{n}$ and a scalar $b\in\mathbb{R}$ determine the
hyperplane

$\\{x\in\mathbb{R}^{n}:\langle a,x\rangle=a_{1}x_{1}+\ldots+a_{n}x_{n}=b\\}.$

A classical result of Alon and Füredi [3] states that the number of
hyperplanes required to cover precisely $2^{n}-1$ vertices of the hypercube
$\\{0,1\\}^{n}$, without covering the last vertex, is $n$. This is tight: we
can cover $\\{0,1\\}^{n}\setminus\textbf{0}$, where 0 denotes the all zero
vector, with the $n$ hyperplanes $\\{x:x_{i}=1\\}$, where
$i\in\\{1,2,\ldots,n\\}$. Several variations of this result have been studied
in the literature, see e.g. the three papers [2, 9, 40] from this year.

For a set $B\subset\\{0,1\\}^{n}$ denote by $\text{ec}(B)$ the _exact cover
number_ of $B$, i.e. the minimum number of hyperplanes whose union intersects
$\\{0,1\\}^{n}$ in precisely $B$. Note that the result of Alon and Füredi says
that $\text{ec}(\\{0,1\\}^{n}\setminus\textbf{0})=n$.

Aaronson, Groenland, Grzesik, Kielak, and Johnston [2] raised the following
question. Given a set $B\subset\\{0,1\\}^{k}$ and integer $n\geq k$, observe
that we have the inequality

$\text{ec}(\\{0,1\\}^{n}\setminus(B\times\\{0\\}^{n-k}))\leq
n-k+\text{ec}(\\{0,1\\}^{k}\setminus B).$

Indeed, we can cover $\\{0,1\\}^{n}\setminus(B\times\\{0\\}^{n-k})$ by using
the hyperplanes used to cover $\\{0,1\\}^{k}\setminus B$, together with the
$n-k$ hyperplanes $\\{x:x_{i}=1\\}$, where $i=k+1,\ldots,n$. Intuitively, it
seems plausible that this inequality is in fact always sharp: it is not clear
how it could help to place the ‘same subset’ in a space with more dimensions.

######  Conjecture 3.1 (Aaronson–Groenland–Grzesik–Kielak–Johnston [2]).

For any $B\subset\\{0,1\\}^{k}$ and $n\in\mathbb{N}$ with $n\geq k$, we have

$\text{ec}(\\{0,1\\}^{n}\setminus(B\times\\{0\\}^{n-k}))=n-k+\text{ec}(\\{0,1\\}^{k}\setminus
B).$

Once we have fixed a set $B$ and integers $n$ and $k$, finding the relevant
exact cover numbers can be phrased as an integer program, with indicator
variables for all possible intersections of $\\{0,1\\}^{n}$ with a hyperplane.
By sampling the set $B$ according to some ad hoc heuristics and solving the
resulting linear programs, we were eventually able to find the following
counterexample to Conjecture 3.1.

Let $n=6,k=4$, and $B=\\{1000,1111,1001,1011,0110,0001,0010,0111\\}$. It is
straightforward to check via a case analysis that $\\{0,1\\}^{4}\setminus B$
cannot be covered with two hyperplanes, so that
$\text{ec}(\\{0,1\\}^{4}\setminus B)\geq 3$. On the other hand, surprisingly
we can cover $\\{0,1\\}^{6}\setminus(B\times\\{0\\}^{2})$ with four
hyperplanes:

$\begin{split}\qquad-x_{2}~{}\qquad~{}~{}~{}\qquad+x_{5}+x_{6}&=1\\\ \qquad
x_{2}-~{}x_{3}~{}~{}~{}\qquad\qquad+x_{6}&=1\\\
x_{1}+x_{2}\qquad\quad-~{}x_{4}+x_{5}+x_{6}&=2\\\
2x_{1}-x_{2}-2x_{3}+2x_{4}+x_{5}-x_{6}&=0\\\ \end{split}$

See Figure 13 for an illustration of this example.

0000000000010000100000110001000001010001100001110010000010010010100010110011000011010011100011110100000100010100100100110101000101010101100101110110000110010110100110110111000111010111100111111000001000011000101000111001001001011001101001111010001010011010101010111011001011011011101011111100001100011100101100111101001101011101101101111110001110011110101110111111001111011111101111114121,212342,32,43,42,3,4121,2121134114232342,32,43,42,3,41242131,3232,33121,2241231,21,32,31,2,31231,21,32,31,2,3131,32121,21232,34131,3131,34113232,342123232,31324121,22342,32,43,42,3,43121,2

Figure 13: Covering $\\{0,1\\}^{6}\setminus(B\times\\{0\\}^{2})$ with four
hyperplanes. The circles represent the points of $\\{0,1\\}^{6}$. Black disks
are elements of $B$, otherwise the numbers in a circle represent which of the
four hyperplanes contain that point.

###  3.2 Weakly cross-intersecting $(a,b)$-set systems

Let $\mathcal{F}$ be a family of pairs subsets
$(A_{1},B_{1}),(A_{2},B_{2}),\ldots$ of $\mathbb{N}$. We say that
$\mathcal{F}$ is an $(a,b)$_-set system_ if for every set-pair $(A_{i},B_{i})$
in $\mathcal{F}$, we have that $|A_{i}|=a$, $|B_{i}|=b$, and $A_{i}\cap
B_{i}=\varnothing$. We say that $\mathcal{F}$ has the _cross-intersecting
property_ if for any two pairs $(A_{i},B_{i})$ and $(A_{j},B_{j})$ in
$\mathcal{F}$ with $i\neq j$, we have that $A_{i}\cap B_{j}\neq\varnothing$
and $A_{j}\cap B_{i}\neq\varnothing$. A classical result of Bollobás [11]
states that if $\mathcal{F}$ is an $(a,b)$-set system with the cross-
intersecting property, then $|\mathcal{F}|\leq\binom{a+b}{b}$, independently
of the size of the ground set. As shown by Frankl [23], the same conclusion
also holds if we relax the cross-intersecting property, and only require that
$A_{i}\cap B_{j}\neq\varnothing$ when $i<j$.

Király, Nagy, Pálvölgyi and Visontai [32] considered what happens when we
further relax the cross-intersecting condition. They called an $(a,b)$-set
system _weakly cross-intersecting_ if for any $i\neq j$, we have that at most
one of the two sets $A_{i}\cap B_{j}$ and $A_{j}\cap B_{i}$ is empty. They
denoted by $g(a,b)$ the maximum size of a weakly cross-intersecting
$(a,b)$-set system. They showed that if $a+b\rightarrow\infty$, we have
$g(a,b)\geq(2-o(1))\binom{a+b}{b}$. Among others, they raised the following
problem:

######  Problem 3.2 (Király–Nagy–Pálvölgyi–Visontai [32]).

Is $g(a,b)<2\binom{a+b}{b}$?

We have found a $(4,4)$-set system of size $146>140=2\cdot\binom{8}{4}$, which
shows that the answer to Problem 3.2 is in general “no”. It is given in the
appendix. It would be interesting to see how one can generalize this
construction, and what the right order of magnitude of $g(a,b)$ is. A result
of Tuza [47] implies $g(a,a)\leq 2^{2a}$, but even the answer to the following
problem is not known.

######  Problem 3.3 (Király–Nagy–Pálvölgyi–Visontai [32]).

Is $g(a,a)=o\mathopen{}\mathclose{{}\left(2^{2a}}\right)$?

##  4 Concluding remarks

The main contribution of the present work is that we have demonstrated some
success with applying reinforcement learning methods to find explicit
constructions and counterexamples to problems in combinatorics. All examples
presented in Section 2 used the cross-entropy method. According to [35], the
main advantages of the cross-entropy method are that it is a very simple
algorithm that has good convergence and works well in simple environments that
do not require us to learn complex, multistep policies. This makes it an ideal
baseline method to try.

While the cross-entropy method works well in general, there exist a plethora
of more sophisticated reinforcement learning algorithms that could potentially
perform much better for some problems. It would be extremely interesting to
see some success with refuting conjectures in combinatorics, graph theory, or
other areas of mathematics, by finding explicit counterexamples using other
reinforcement learning algorithms.

######  Problem 4.1.

Use a different reinforcement learning algorithm to find an explicit
counterexample to an open conjecture in mathematics.

Acknowledgment: The author is very grateful to Bálint Varga for help with
various programming-related questions.

## References

  * [1] G. Aalipour, A. Abiad, Z. Berikkyzy, L. Hogben, F. Kenter, J. C.-H. Lin, and M. Tait.  Proof of a conjecture of Graham and Lovász concerning unimodality of coefficients of the distance characteristic polynomial of a tree.  The Electronic Journal of Linear Algebra, 34:373–380, 2018.
  * [2] J. Aaronson, C. Groenland, A. Grzesik, B. Kielak, and T. Johnston.  Exact hyperplane covers for subsets of the hypercube.  arXiv preprint arXiv:2010.00315, 2020.
  * [3] N. Alon and Z. Füredi.  Covering the cube by affine hyperplanes.  European journal of combinatorics, 14(2):79–83, 1993.
  * [4] M. Aouchiche and P. Hansen.  A survey of automated conjectures in spectral graph theory.  Linear algebra and its applications, 432(9):2293–2322, 2010.
  * [5] M. Aouchiche and P. Hansen.  Proximity and remoteness in graphs: results and conjectures.  Networks, 58(2):95–102, 2011.
  * [6] M. Aouchiche and P. Hansen.  Proximity, remoteness and distance eigenvalues of a graph.  Discrete Applied Mathematics, 213:17–25, 2016.
  * [7] K. Appel and W. Haken.  The solution of the four-color-map problem.  Scientific American, 237(4):108–121, 1977.
  * [8] Y. Bengio, A. Lodi, and A. Prouvost.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  European Journal of Operational Research, 2020.
  * [9] A. Bishnoi, S. Boyadzhiyska, S. Das, and T. Mészáros.  Subspace coverings with multiplicities.  arXiv preprint arXiv:2101.11947, 2021.
  * [10] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann.  Netgan: Generating graphs via random walks.  In International Conference on Machine Learning, pages 610–619. PMLR, 2018.
  * [11] B. Bollobás.  On generalized graphs.  Acta Mathematica Hungarica, 16(3-4):447–452, 1965.
  * [12] M. Bóna.  Combinatorics of permutations.  CRC Press, 2012.
  * [13] L. M. Brègman.  Some properties of nonnegative matrices and their permanents.  In Doklady Akademii Nauk, volume 211/1, pages 27–30. Russian Academy of Sciences, 1973.
  * [14] B. Brimkov, K. Duna, L. Hogben, K. Lorenzen, C. Reinhart, S.-Y. Song, and M. Yarrow.  Graphs that are cospectral for the distance laplacian.  arXiv preprint arXiv:1812.05734, 2018.
  * [15] R. A. Brualdi and L. Cao.  Pattern-avoiding (0, 1)-matrices.  arXiv preprint arXiv:2005.00379, 2020.
  * [16] G. Caporossi and P. Hansen.  Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system.  Discrete Mathematics, 212(1-2):29–44, 2000.
  * [17] Q. Cappart, D. Chételat, E. Khalil, A. Lodi, C. Morris, and P. Veličković.  Combinatorial optimization and reasoning with graph neural networks.  arXiv preprint arXiv:2102.09544, 2021.
  * [18] K. L. Collins.  On a conjecture of Graham and Lovász about distance matrices.  Discrete applied mathematics, 25(1-2):27–35, 1989.
  * [19] D. M. Cvetković, M. Doob, and H. Sachs.  Spectra of graphs: Theory and application.  Pure and Applied Mathematics, 1980.
  * [20] N. De Cao and T. Kipf.  Molgan: An implicit generative model for small molecular graphs.  arXiv preprint arXiv:1805.11973, 2018.
  * [21] M. Fekete.  Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten.  Mathematische Zeitschrift, 17(1):228–249, 1923.
  * [22] J. Fox.  Stanley-Wilf limits are typically exponential.  arXiv preprint arXiv:1310.8378, 2013.
  * [23] P. Frankl.  An extremal problem for two families of sets.  European Journal of Combinatorics, 3(2):125–127, 1982.
  * [24] Z. Füredi and P. Hajnal.  Davenport-Schinzel theory of matrices.  Discrete Mathematics, 103(3):233–251, 1992.
  * [25] R. L. Graham and L. Lovász.  Distance matrix polynomials of trees.  Advances in Mathematics, 29(1):60–88, 1978.
  * [26] R. L. Graham and H. O. Pollak.  On the addressing problem for loop switching.  The Bell system technical journal, 50(8):2495–2519, 1971.
  * [27] T. Guo, C. Han, S. Tang, and M. Ding.  Solving combinatorial problems with machine learning methods.  In Nonlinear Combinatorial Optimization, pages 207–229. Springer, 2019.
  * [28] L. Gurobi Optimization.  Gurobi optimizer reference manual, 2021.
  * [29] T. C. Hales.  A proof of the Kepler conjecture.  Annals of mathematics, pages 1065–1185, 2005.
  * [30] W. L. Hamilton.  Graph representation learning.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1–159, 2020.
  * [31] L. Hogben and C. Reinhart.  Spectra of variants of distance matrices of graphs and digraphs: a survey.  arXiv preprint arXiv:2103.00647, 2021.
  * [32] Z. Király, Z. L. Nagy, D. Pálvölgyi, and M. Visontai.  On families of weakly cross-intersecting set-pairs.  Fundamenta Informaticae, 117(1-4):189–198, 2012.
  * [33] S. Kitaev.  Patterns in permutations and words.  Springer Science & Business Media, 2011.
  * [34] M. Klazar.  The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture.  In Formal power series and algebraic combinatorics, pages 250–255. Springer, 2000.
  * [35] M. Lapan.  Deep Reinforcement Learning Hands-On: Apply Modern RL Methods to Practical Problems of Chatbots, Robotics, Discrete Optimization, Web Automation, and More, 2nd Edition.  Expert insight. Packt Publishing, Limited, 2020.
  * [36] A. Marcus and G. Tardos.  Excluded permutation matrices and the Stanley-Wilf conjecture.  Journal of Combinatorial Theory, Series A, 107(1):153–160, 2004\.
  * [37] N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev.  Reinforcement learning for combinatorial optimization: A survey.  arXiv preprint arXiv:2003.03600, 2020.
  * [38] R. Merris.  The distance spectrum of a tree.  Journal of graph theory, 14(3):365–369, 1990.
  * [39] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.  Human-level control through deep reinforcement learning.  nature, 518(7540):529–533, 2015.
  * [40] L. Sauermann and Y. Wigderson.  Polynomials that vanish to high order on most of the hypercube.  arXiv preprint arXiv:2010.00077, 2020.
  * [41] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al.  Mastering the game of go without human knowledge.  nature, 550(7676):354–359, 2017.
  * [42] R. P. Stanley.  Increasing and decreasing subsequences and their variants.  In International Congress of Mathematicians, volume 1, pages 545–579, 2007.
  * [43] E. Steingrímsson.  Some open problems on permutation patterns.  Surveys in combinatorics, 409:239–263, 2013.
  * [44] D. Stevanović.  Resolution of AutoGraphiX conjectures relating the index and matching number of graphs.  Linear algebra and its applications, 433(8-10):1674–1677, 2010\.
  * [45] B. E. Tenner.  Database of permutation pattern avoidance.  http://math.depaul.edu/bridget/patterns.html.
  * [46] J. Torres.  https://towardsdatascience.com/solving-a-reinforcement-learning-problem-using-cross-entropy-method-23d9726a737.
  * [47] Z. Tuza.  Inequalities for two set systems with prescribed intersections.  Graphs and Combinatorics, 3(1):75–80, 1987.
  * [48] L. G. Valiant.  The complexity of computing the permanent.  Theoretical computer science, 8(2):189–201, 1979.
  * [49] H. Van Hasselt, A. Guez, and D. Silver.  Deep reinforcement learning with double q-learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
  * [50] N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman.  Learning combinatorial optimization on graphs: A survey with applications to networking.  IEEE Access, 8:120388–120416, 2020.
  * [51] A. Z. Wagner.  https://github.com/zawagner22/cross-entropy-for-combinatorics.
  * [52] A. Z. Wagner.  Refuting conjectures in extremal combinatorics via linear programming.  Journal of Combinatorial Theory, Series A, 169:105130, 2020.
  * [53] Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas.  Dueling network architectures for deep reinforcement learning.  In International conference on machine learning, pages 1995–2003. PMLR, 2016.
  * [54] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun.  Graph neural networks: A review of methods and applications.  arXiv preprint arXiv:1812.08434, 2018.

##  Appendix A The construction for Problem 3.2

The $(4,4)$-set system in $\\{1,2,\ldots,11\\}$ of size 146 is as follows.

(1, 2, 3, 7 — 5, 6, 9, 10), (1, 2, 3, 9 — 5, 8, 10, 11), (1, 2, 4, 6 — 5, 8,
9, 11), (1, 2, 4, 7 — 3, 5, 6, 11),
(1, 2, 4, 8 — 5, 7, 9, 11), (1, 2, 4, 11 — 3, 5, 8, 9), (1, 2, 5, 6 — 7, 9,
10, 11), (1, 2, 5, 7 — 6, 8, 9, 11),
(1, 2, 5, 9 — 4, 6, 8, 11), (1, 2, 5, 10 — 6, 7, 8, 9), (1, 2, 6, 7 — 4, 9,
10, 11), (1, 2, 6, 10 — 4, 8, 9, 11),
(1, 2, 7, 10 — 4, 5, 6, 8), (1, 2, 8, 11 — 3, 5, 6, 10), (1, 2, 9, 11 — 3, 4,
8, 10), (1, 3, 4, 8 — 2, 5, 6, 11),
(1, 3, 4, 9 — 2, 5, 6, 8), (1, 3, 4, 10 — 5, 6, 8, 9), (1, 3, 5, 8 — 6, 9, 10,
11), (1, 3, 5, 9 — 2, 6, 7, 10),
(1, 3, 5, 10 — 2, 6, 7, 11), (1, 3, 6, 8 — 4, 5, 7, 9), (1, 3, 6, 10 — 2, 4,
8, 9), (1, 3, 7, 10 — 2, 4, 6, 9),
(1, 3, 7, 11 — 2, 5, 9, 10), (1, 3, 8, 11 — 5, 6, 7, 10), (1, 4, 5, 6 — 2, 9,
10, 11), (1, 4, 5, 8 — 3, 6, 7, 11),
(1, 4, 5, 11 — 6, 8, 9, 10), (1, 4, 6, 11 — 2, 5, 7, 8), (1, 4, 7, 8 — 2, 3,
6, 9), (1, 4, 7, 9 — 2, 3, 5, 11),
(1, 4, 8, 9 — 3, 5, 7, 11), (1, 4, 9, 10 — 3, 6, 7, 8), (1, 5, 6, 9 — 7, 8,
10, 11), (1, 5, 6, 11 — 3, 4, 7, 9),
(1, 5, 7, 9 — 2, 6, 10, 11), (1, 5, 7, 11 — 2, 4, 6, 10), (1, 5, 8, 9 — 3, 4,
6, 7), (1, 5, 8, 11 — 6, 7, 9, 10),
(1, 5, 10, 11 — 2, 6, 7, 9), (1, 6, 7, 8 — 2, 5, 9, 11), (1, 6, 7, 9 — 2, 4,
5, 11), (1, 6, 7, 11 — 2, 3, 9, 10),
(1, 6, 10, 11 — 2, 3, 4, 5), (1, 7, 8, 9 — 4, 5, 6, 11), (1, 7, 9, 10 — 2, 4,
6, 8), (1, 7, 9, 11 — 2, 3, 5, 10),
(1, 8, 9, 10 — 4, 5, 7, 11), (1, 8, 10, 11 — 5, 6, 7, 9), (1, 9, 10, 11 — 4,
5, 6, 7), (2, 3, 4, 6 — 1, 5, 10, 11),
(2, 3, 4, 7 — 1, 5, 6, 10), (2, 3, 5, 7 — 1, 4, 10, 11), (2, 3, 5, 10 — 1, 7,
8, 11), (2, 3, 5, 11 — 1, 6, 7, 10),
(2, 3, 6, 11 — 5, 8, 9, 10), (2, 3, 7, 9 — 1, 4, 5, 10), (2, 3, 7, 10 — 1, 5,
6, 11), (2, 3, 8, 9 — 6, 7, 10, 11),
(2, 3, 8, 10 — 1, 5, 7, 9), (2, 3, 8, 11 — 1, 5, 7, 10), (2, 3, 9, 10 — 5, 7,
8, 11), (2, 3, 9, 11 — 5, 7, 8, 10),
(2, 3, 10, 11 — 1, 6, 8, 9), (2, 4, 5, 7 — 1, 8, 9, 10), (2, 4, 5, 8 — 1, 3,
7, 10), (2, 4, 5, 9 — 6, 8, 10, 11),
(2, 4, 6, 9 — 3, 5, 7, 8), (2, 4, 6, 10 — 1, 5, 8, 9), (2, 4, 7, 8 — 1, 3, 10,
11), (2, 4, 8, 9 — 1, 3, 5, 7),
(2, 4, 8, 10 — 1, 3, 9, 11), (2, 4, 9, 11 — 3, 6, 8, 10), (2, 4, 10, 11 — 1,
3, 6, 9), (2, 5, 6, 9 — 1, 7, 8, 10),
(2, 5, 6, 11 — 1, 4, 7, 9), (2, 5, 7, 8 — 3, 4, 6, 10), (2, 5, 7, 10 — 1, 8,
9, 11), (2, 5, 7, 11 — 4, 8, 9, 10),
(2, 5, 8, 10 — 4, 6, 7, 9), (2, 6, 7, 9 — 3, 8, 10, 11), (2, 6, 7, 11 — 3, 4,
5, 9), (2, 6, 8, 9 — 3, 4, 10, 11),
(2, 6, 8, 11 — 3, 5, 7, 9), (2, 6, 9, 10 — 3, 4, 8, 11), (2, 6, 10, 11 — 4, 5,
7, 8), (2, 7, 8, 10 — 3, 4, 9, 11),
(2, 7, 9, 10 — 1, 3, 6, 11), (2, 8, 9, 11 — 1, 3, 4, 7), (2, 9, 10, 11 — 1, 5,
6, 8), (3, 4, 5, 8 — 1, 7, 9, 11),
(3, 4, 5, 9 — 1, 2, 7, 11), (3, 4, 5, 11 — 1, 2, 6, 10), (3, 4, 6, 8 — 2, 5,
7, 11), (3, 4, 6, 9 — 2, 5, 8, 11),
(3, 4, 6, 10 — 2, 8, 9, 11), (3, 4, 7, 8 — 1, 2, 9, 11), (3, 4, 7, 11 — 1, 2,
5, 9), (3, 4, 9, 11 — 1, 2, 5, 10),
(3, 5, 6, 7 — 2, 4, 8, 10), (3, 5, 6, 8 — 2, 4, 9, 10), (3, 5, 7, 10 — 1, 2,
4, 11), (3, 5, 10, 11 — 1, 2, 8, 9),
(3, 6, 7, 8 — 1, 4, 5, 9), (3, 6, 7, 10 — 1, 4, 5, 8), (3, 6, 8, 9 — 4, 7, 10,
11), (3, 6, 9, 11 — 2, 4, 5, 7),
(3, 7, 8, 9 — 1, 2, 10, 11), (3, 7, 8, 11 — 1, 4, 6, 9), (3, 7, 9, 10 — 1, 2,
5, 6), (3, 7, 9, 11 — 2, 4, 5, 10),
(3, 8, 9, 10 — 1, 5, 6, 7), (3, 8, 10, 11 — 1, 2, 7, 9), (4, 5, 6, 7 — 1, 2,
8, 10), (4, 5, 6, 10 — 3, 7, 8, 9),
(4, 5, 6, 11 — 7, 8, 9, 10), (4, 5, 7, 8 — 1, 2, 3, 11), (4, 5, 7, 10 — 2, 6,
8, 11), (4, 5, 9, 10 — 1, 3, 7, 11),
(4, 5, 9, 11 — 2, 3, 6, 10), (4, 6, 7, 10 — 2, 3, 8, 9), (4, 6, 8, 10 — 2, 3,
7, 9), (4, 6, 8, 11 — 2, 7, 9, 10),
(4, 7, 8, 10 — 1, 2, 3, 5), (4, 7, 8, 11 — 1, 3, 9, 10), (4, 7, 10, 11 — 2, 3,
6, 8), (4, 8, 9, 11 — 2, 3, 5, 7),
(4, 9, 10, 11 — 1, 2, 7, 8), (5, 6, 7, 9 — 2, 3, 4, 10), (5, 6, 7, 10 — 2, 3,
4, 8), (5, 6, 8, 9 — 2, 3, 7, 10),
(5, 6, 8, 10 — 4, 7, 9, 11), (5, 6, 9, 10 — 2, 4, 7, 8), (5, 6, 9, 11 — 2, 7,
8, 10), (5, 7, 8, 10 — 2, 3, 4, 11),
(5, 7, 9, 11 — 1, 4, 6, 8), (5, 7, 10, 11 — 3, 4, 6, 9), (5, 8, 9, 10 — 1, 4,
7, 11), (5, 8, 9, 11 — 1, 2, 4, 6),
(5, 9, 10, 11 — 4, 6, 7, 8), (6, 7, 9, 11 — 1, 3, 5, 8), (6, 8, 9, 10 — 1, 4,
5, 11), (6, 8, 10, 11 — 1, 2, 3, 4),
(7, 8, 9, 11 — 1, 3, 5, 10), (7, 8, 10, 11 — 3, 4, 5, 6)