
A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is nonhamiltonian, there
exists a vertex $w$ in $G$ such that $G  w$ is nonhamiltonian, and $G  v$ is
hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J.
Graph Theory 79 (2015) 6381] for all orders for which a.h. graphs exist. Here
we solve this problem. To this end, we present a specialised algorithm which
generates complete sets of a.h. graphs for various orders. Furthermore, we show
that the smallest cubic a.h. graphs have order 26. We provide a lower bound for
the order of the smallest planar a.h. graph and improve the upper bound for the
order of the smallest planar a.h. graph containing a cubic vertex. We also
determine the smallest planar a.h. graphs of girth 5, both in the general and
cubic case. Finally, we extend a result of Steffen on snarks and improve two
bounds on longest paths and longest cycles in polyhedral graphs due to
Jooyandeh, McKay, {\"O}sterg{\aa}rd, Pettersson, and the second author.

This paper presents a short and simple proof of the FourColor Theorem that
can be utterly checkable by human mathematicians, without computer assistance.
The new key idea that has allowed it and the global structure of the proof are
presented in the Introduction.

Motivated by applications in online advertising, we consider a class of
maximization problems where the objective is a function of the sequence of
actions as well as the running duration of each action. For these problems, we
introduce the concepts of \emph{sequencesubmodularity} and
\emph{sequencemonotonicity} which extend the notions of submodularity and
monotonicity from functions defined over sets to functions defined over
sequences. We establish that if the objective function is sequencesubmodular
and sequencenondecreasing, then there exists a greedy algorithm that achieves
$11/e$ of the optimal solution. We apply our algorithm and analysis to two
applications in online advertising: online ad allocation and query rewriting.
We first show that both problems can be formulated as maximizing nondecreasing
sequencesubmodular functions. We then apply our framework to these two
problems, leading to simple greedy approaches with guaranteed performances. In
particular, for online ad allocation problem the performance of our algorithm
is $11/e$, which matches the best known existing performance, and for query
rewriting problem the performance of our algorithm is $1 1/e^{11/e}$ which
improves upon the best known existing performance in the literature.

We present a new aperiodic tile set containing 11 Wang tiles on 4 colors, and
show that this tile set is minimal in the sense that no Wang set with less than
11 tiles is aperiodic, and no Wang set with less than 4 colors is aperiodic.
This gives a final answer to a problem raised by a question asked by Wang in
1961.

We study the iteration of the process "a particle jumps to the right" in
permutations. We prove that the set of permutations obtained in this model
after a given number of iterations from the identity is a class of pattern
avoiding permutations. We characterize the elements of the basis of this class
and we enumerate these "forbidden minimal patterns" by giving their bivariate
exponential generating function: we achieve this via a catalytic variable, the
number of lefttoright maxima. We show that this generating function is a
Dfinite function satisfying a nice differential equation of order~2. We give
some congruence properties for the coefficients of this generating function,
and we show that their asymptotics involves a rather unusual algebraic exponent
(the golden ratio $(1+\sqrt 5)/2$) and some unusual closedform constants. We
end by proving a limit law: a forbidden pattern of length $n$ has typically
$(\ln n) /\sqrt{5}$ lefttoright maxima, with Gaussian fluctuations.

A special case of Myerson's classic result describes the revenueoptimal
equilibrium when a seller offers a single item to a buyer. We study a repeated
sales extension of this model: a seller offers to sell a single fresh copy of
an item to the same buyer every day via a posted price. The buyer's private
value for the item is drawn initially from a publicly known distribution $F$
and remains the same throughout. A key aspect of this game is that the seller
might try to learn the buyer's private value to extract more revenue, while the
buyer is motivated to hide it. We study the Perfect Bayesian Equilibria (PBE)
in this setting with varying levels of commitment power to the seller. We find
that the seller having the commitment power to not raise prices subsequent to a
purchase significantly improves revenue in a PBE.

Given $n$ pairwise openly disjoint triangles in 3space, their vertical depth
relation may contain cycles. We show that, for any $\varepsilon>0$, the
triangles can be cut into $O(n^{3/2+\varepsilon})$ connected semialgebraic
pieces, whose description complexity depends only on the choice of
$\varepsilon$, such that the depth relation among these pieces is now a proper
partial order. This bound is nearly tight in the worst case. We are not aware
of any previous study of this problem, in this full generality, with a
subquadratic bound on the number of pieces.
This work extends the recent study by two of the authors (Aronov,
Sharir~2018) on eliminating depth cycles among lines in 3space. Our approach
is again algebraic, and makes use of a recent variant of the polynomial
partitioning technique, due to Guth, which leads to a recursive procedure for
cutting the triangles. In contrast to the case of lines, our analysis here is
considerably more involved, due to the twodimensional nature of the objects
being cut, so additional tools, from topology and algebra, need to be brought
to bear.
Our result essentially settles a 35yearold open problem in computational
geometry, motivated by hiddensurface removal in computer graphics.

The problem of determining the number of "flooding operations" required to
make a given coloured graph monochromatic in the oneplayer combinatorial game
FloodIt has been studied extensively from an algorithmic point of view, but
basic questions about the maximum number of moves that might be required in the
worst case remain unanswered. We begin a systematic investigation of such
questions, with the goal of determining, for a given graph, the maximum number
of moves that may be required, taken over all possible colourings. We give
several upper and lower bounds on this quantity for arbitrary graphs and show
that all of the bounds are tight for trees; we also investigate how much the
upper bounds can be improved if we restrict our attention to graphs with higher
edgedensity.

The satisfiability problem is known to be $\mathbf{NP}$complete in general
and for many restricted cases. One way to restrict instances of $k$SAT is to
limit the number of times a variable can be occurred. It was shown that for an
instance of 4SAT with the property that every variable appears in exactly 4
clauses (2 times negated and 2 times not negated), determining whether there is
an assignment for variables such that every clause contains exactly two true
variables and two false variables is $\mathbf{NP}$complete. In this work, we
show that deciding the satisfiability of 3SAT with the property that every
variable appears in exactly four clauses (two times negated and two times not
negated), and each clause contains at least two distinct variables is $
\mathbf{NP} $complete. We call this problem $(2/2/3)$SAT. For an $r$regular
graph $G = (V,E)$ with $r\geq 3$, it was asked in [Discrete Appl. Math.,
160(15):21422146, 2012] to determine whether for a given independent set $T $
there is an independent dominating set $D$ that dominates $T$ such that $ T
\cap D =\varnothing $? As an application of $(2/2/3)$SAT problem we show that
for every $r\geq 3$, this problem is $ \mathbf{NP} $complete. Among other
results, we study the relationship between 1perfect codes and the incidence
coloring of graphs and as another application of our complexity results, we
prove that for a given cubic graph $G$ deciding whether $G$ is 4incidence
colorable is $ \mathbf{NP} $complete.

We prove that certain classes of metrically homogeneous graphs omitting
triangles of odd short perimeter as well as triangles of long perimeter have
the extension property for partial automorphisms and we describe their Ramsey
expansions.

Slimness of a graph measures the local deviation of its metric from a tree
metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with
$x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest
paths connecting these vertices. A geodesic triangle $\bigtriangleup(x,y,z)$ is
called $\delta$slim if for any vertex $u\in V$ on any side $P(x,y)$ the
distance from $u$ to $P(x,z) \cup P(y,z)$ is at most $\delta$, i.e. each path
is contained in the union of the $\delta$neighborhoods of two others. A graph
$G$ is called $\delta$slim, if all geodesic triangles in $G$ are
$\delta$slim. The smallest value $\delta$ for which $G$ is $\delta$slim is
called the slimness of $G$. In this paper, using the layering partition
technique, we obtain sharp bounds on slimness of such families of graphs as (1)
graphs with clusterdiameter $\Delta(G)$ of a layering partition of $G$, (2)
graphs with treelength $\lambda$, (3) graphs with treebreadth $\rho$, (4)
$k$chordal graphs, ATfree graphs and HHDfree graphs. Additionally, we show
that the slimness of every 4chordal graph is at most 2 and characterize those
4chordal graphs for which the slimness of every of its induced subgraph is at
most 1.

We show that the Radon number characterizes the existence of weak nets in
separable convexity spaces (an abstraction of the euclidean notion of
convexity). The construction of weak nets when the Radon number is finite is
based on Helly's property and on metric properties of VC classes. The lower
bound on the size of weak nets when the Radon number is large relies on the
chromatic number of the Kneser graph. As an application, we prove a
boostingtype result for weak $\epsilon$nets.

We study spatial discretizations of dynamical systems: is it possible to
recover some dynamical features of a system from numerical simulations? Here,
we tackle this issue for the simplest algorithm possible: we compute long
segments of orbits with a fixed number of digits. We show that for every $r\ge
1$, the dynamics of the discretizations of a $C^r$ generic conservative
diffeomorphism of the torus is very different from that observed in the $C^0$
regularity. The proof of our results involves in particular a localglobal
formula for discretizations, as well as a study of the corresponding linear
case, which uses ideas from the theory of quasicrystals.

We give two graph theoretical characterizations of tope graphs of (complexes
of) oriented matroids. The first is in terms of excluded partial cube minors,
the second is that all antipodal subgraphs are gated. A direct consequence is a
third characterization in terms of zone graphs of tope graphs.
Further corollaries include a characterization of topes of oriented matroids
due to da Silva, another one of Handa, a characterization of lopsided systems
due to Lawrence, and an intrinsic characterization of tope graphs of affine
oriented matroids. Furthermore, we obtain polynomial time recognition
algorithms for tope graphs of the above and a finite list of excluded partial
cube minors for the bounded rank case. In particular, this answers a relatively
longstanding open question in oriented matroids. Another consequence is that
all finite Pasch graphs are tope graphs of complexes of oriented matroids,
which confirms a conjecture of Chepoi and the two authors.

Let $n$ be any positive integer and $\mathcal{F}$ be a family of subsets of
$[n]$.
A family $\mathcal{F}'$ is said to be $D$\emph{secting} for $\mathcal{F}$ if
for every $A \in \mathcal{F}$, there exists a subset $A' \in \mathcal{F}'$ such
that $A \cap A'  A \cap ([n] \setminus A')=i$, where $i \in D$, $D
\subseteq \{n,n+1,\ldots,0,\ldots,n\}$.
A $D$\emph{secting} family $\mathcal{F}'$ of $\mathcal{F}$, where
$D=\{1,0,1\}$, is a \emph{bisecting} family ensuring the existence of a subset
$A' \in \mathcal{F}'$ such that $A \cap A' \in \{\lceil
\frac{A}{2}\rceil,\lfloor \frac{A}{2}\rfloor\}$, for each $A \in
\mathcal{F}$.
In this paper, we study $D$secting families for $\mathcal{F}$ with
restrictions on $D$, and the cardinalities of $\mathcal{F}$ and the subsets of
$\mathcal{F}$.

A group of mobile agents is given a task to explore an edgeweighted graph
$G$, i.e., every vertex of $G$ has to be visited by at least one agent. There
is no centralized unit to coordinate their actions, but they can freely
communicate with each other. The goal is to construct a deterministic strategy
which allows agents to complete their task optimally. In this paper we are
interested in a costoptimal strategy, where the cost is understood as the
total distance traversed by agents coupled with the cost of invoking them. Two
graph classes are analyzed, rings and trees, in the offline and online
setting, i.e., when a structure of a graph is known and not known to agents in
advance. We present algorithms that compute the optimal solutions for a given
ring and tree of order $n$, in $O(n)$ time units. For rings in the online
setting, we give the $2$competitive algorithm and prove the lower bound of
$3/2$ for the competitive ratio for any online strategy. For every strategy
for trees in the online setting, we prove the competitive ratio to be no less
than $2$, which can be achieved by the $DFS$ algorithm.

Given a partiallyordered finite alphabet $\Sigma$ and a language $L\subseteq
\Sigma^*$, how large can an antichain in $L$ be (where $L$ is given the
lexicographic ordering)? More precisely, since $L$ will in general be infinite,
we should ask about the rate of growth of maximum antichains consisting of
words of length $n$. This fundamental property of partial orders is known as
the width, and in a companion work we show that the problem of computing the
information leakage permitted by a deterministic interactive system modeled as
a finitestate transducer can be reduced to the problem of computing the width
of a certain regular language. In this paper, we show that if $L$ is regular
then there is a dichotomy between polynomial and exponential antichain growth.
We give a polynomialtime algorithm to distinguish the two cases, and to
compute the order of polynomial growth, with the language specified as an NFA.
For contextfree languages we show that there is a similar dichotomy, but now
the problem of distinguishing the two cases is undecidable. Finally, we
generalise the lexicographic order to tree languages, and show that for regular
tree languages there is a trichotomy between polynomial, exponential and doubly
exponential antichain growth.

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$free if it
contains no subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ and $C_s$ be the
path on $t$ vertices and the cycle on $s$ vertices, respectively. In this paper
we show that for any $(P_6,C_4)$free graph $G$ it holds that $\chi(G)\le
\frac{3}{2}\omega(G)$, where $\chi(G)$ and $\omega(G)$ are the chromatic number
and clique number of $G$, respectively. %Our bound is attained by $C_5$ and the
Petersen graph. Our bound is attained by several graphs, for instance, the
fivecycle, the Petersen graph, the Petersen graph with an additional universal
vertex, and all $4$critical $(P_6,C_4)$free graphs other than $K_4$ (see
\cite{HH17}). The new result unifies previously known results on the existence
of linear $\chi$binding functions for several graph classes. Our proof is
based on a novel structure theorem on $(P_6,C_4)$free graphs that do not
contain clique cutsets. Using this structure theorem we also design a
polynomial time $3/2$approximation algorithm for coloring $(P_6,C_4)$free
graphs. Our algorithm computes a coloring with $\frac{3}{2}\omega(G)$ colors
for any $(P_6,C_4)$free graph $G$ in $O(n^2m)$ time.

In this work, we aim to explore connections between dynamical systems
techniques and combinatorial optimization problems. In particular, we construct
heuristic approaches for the traveling salesman problem (TSP) based on
embedding the relaxed discrete optimization problem into appropriate manifolds.
We explore multiple embedding techniques  namely, the construction of new
dynamical systems on the manifold of orthogonal matrices and associated
Procrustes approximations of the TSP cost function. Using these dynamical
systems, we analyze the local neighborhood around the optimal TSP solutions
(which are equilibria) using computations to approximate the associated
\emph{stable manifolds}. We find that these flows frequently converge to
undesirable equilibria. However, the solutions of the dynamical systems and the
associated Procrustes approximation provide an interesting biasing approach for
the popular LinKernighan heuristic which yields fast convergence. The
LinKernighan heuristic is typically based on the computation of edges that
have a `high probability' of being in the shortest tour, thereby effectively
pruning the search space. Our new approach, instead, relies on a natural
relaxation of the combinatorial optimization problem to the manifold of
orthogonal matrices and the subsequent use of this solution to bias the
LinKernighan heuristic. Although the initial cost of computing these edges
using the Procrustes solution is higher than existing methods, we find that the
Procrustes solution, when coupled with a homotopy computation, contains
valuable information regarding the optimal edges. We explore the Procrustes
based approach on several TSP instances and find that our approach often
requires fewer $k$opt moves than existing approaches. Broadly, we hope that
this work initiates more work in the intersection of dynamical systems theory
and combinatorial optimization.

We present an O(n^6 ) linear programming model for the traveling salesman
(TSP) and quadratic assignment (QAP) problems. The basic model is developed
within the framework of the TSP. It does not involve the citytocity
variablesbased, traditional TSP polytope referred to in the literature as "the
TSP polytope." We do not model explicit Hamiltonian cycles of the cities.
Instead, we use a timedependent abstraction of TSP tours and develop a direct
extended formulation of the linear assignment problem (LAP) polytope. The model
is exact in the sense that it has integral extreme points which are in
onetoone correspondence with TSP tours. It can be solved optimally using any
linear programming (LP) solver, hence offering a new (incidental) proof of the
equality of the computational complexity classes "P" and "NP." The extensions
of the model to the timedependent traveling salesman problem (TDTSP) as well
as the quadratic assignment problem (QAP) are straightforward. The reasons for
the nonapplicability of existing negative extended formulations results for
"the TSP polytope" to the model in this paper as well as our software
implementation and the computational experimentation we conducted are briefly
discussed.

Multilevel partitioning methods that are inspired by principles of
multiscaling are the most powerful practical hypergraph partitioning solvers.
Hypergraph partitioning has many applications in disciplines ranging from
scientific computing to data science. In this paper we introduce the concept of
algebraic distance on hypergraphs and demonstrate its use as an algorithmic
component in the coarsening stage of multilevel hypergraph partitioning
solvers. The algebraic distance is a vertex distance measure that extends
hyperedge weights for capturing the local connectivity of vertices which is
critical for hypergraph coarsening schemes. The practical effectiveness of the
proposed measure and corresponding coarsening scheme is demonstrated through
extensive computational experiments on a diverse set of problems. Finally, we
propose a benchmark of hypergraph partitioning problems to compare the quality
of other solvers.

A colouring of a graph $G=(V,E)$ is a function $c: V\rightarrow\{1,2,\ldots
\}$ such that $c(u)\neq c(v)$ for every $uv\in E$. A $k$regular list
assignment of $G$ is a function $L$ with domain $V$ such that for every $u\in
V$, $L(u)$ is a subset of $\{1, 2, \dots\}$ of size $k$. A colouring $c$ of $G$
respects a $k$regular list assignment $L$ of $G$ if $c(u)\in L(u)$ for every
$u\in V$. A graph $G$ is $k$choosable if for every $k$regular list assignment
$L$ of $G$, there exists a colouring of $G$ that respects $L$. We may also ask
if for a given $k$regular list assignment $L$ of a given graph $G$, there
exists a colouring of $G$ that respects $L$. This yields the $k$Regular List
Colouring problem. For $k\in \{3,4\}$ we determine a family of classes ${\cal
G}$ of planar graphs, such that either $k$Regular List Colouring is
NPcomplete for instances $(G,L)$ with $G\in {\cal G}$, or every $G\in {\cal
G}$ is $k$choosable. By using known examples of non$3$choosable and
non$4$choosable graphs, this enables us to classify the complexity of
$k$Regular List Colouring restricted to planar graphs, planar bipartite
graphs, planar trianglefree graphs and to planar graphs with no $4$cycles and
no $5$cycles. We also classify the complexity of $k$Regular List Colouring
and a number of related colouring problems for graphs with bounded maximum
degree.

We say that a family of $k$subsets of an $n$element set is intersecting, if
any two of its sets intersect. In this paper we study different extremal
properties of intersecting families, as well as the structure of large
intersecting families. We also give some results on $k$uniform families
without $s$ pairwise disjoint sets, related to the Erd\H{o}s Matching
Conjecture. We prove a conclusive version of Frankl's theorem on intersecting
families with bounded maximal degree. This theorem, along with its
generalizations to crossintersecting families, implies many results on the
topic, obtained by Frankl, Frankl and Tokushige, Kupavskii and Zakharov and
others. We study the structure of large intersecting families, obtaining some
general structural theorems which generalize the results of Han and Kohayakawa,
as well as Kostochka and Mubayi. We give degree and subset degree version of
the Erd\H{o}sKoRado and the HiltonMilner theorems, extending the results
of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in
which the degree version of the Erd\H{o}s Matching conjecture holds.

Given complex numbers $w_1, \ldots, w_n$, we define the weight $w(X)$ of a
set $X$ of 01 vectors as the sum of $w_1^{x_1} \cdots w_n^{x_n}$ over all
vectors $(x_1, \ldots, x_n)$ in $X$. We present an algorithm, which for a set
$X$ defined by a system of homogeneous linear equations with at most $r$
variables per equation and at most $c$ equations per variable, computes $w(X)$
within relative error $\epsilon >0$ in $(rc)^{O(\ln n\ln \epsilon)}$ time
provided $w_j \leq \beta (r \sqrt{c})^{1}$ for an absolute constant $\beta
>0$ and all $j=1, \ldots, n$. A similar algorithm is constructed for computing
the weight of a linear code over ${\Bbb F}_p$. Applications include counting
weighted perfect matchings in hypergraphs, counting weighted graph
homomorphisms, computing weight enumerators of linear codes with sparse code
generating matrices, and computing the partition functions of the ferromagnetic
Potts model at low temperatures and of the hardcore model at high fugacity on
biregular bipartite graphs.

As a generalization of the use of graphs to describe pairwise interactions,
simplicial complexes can be used to model higherorder interactions between
three or more objects in complex systems. There has been a recent surge in
activity for the development of data analysis methods applicable to simplicial
complexes, including techniques based on computational topology, higherorder
random processes, generalized Cheeger inequalities, isoperimetric inequalities,
and spectral methods. In particular, spectral learning methods (e.g. label
propagation and clustering) that directly operate on simplicial complexes
represent a new direction for analyzing such complex datasets.
To apply spectral learning methods to massive datasets modeled as simplicial
complexes, we develop a method for sparsifying simplicial complexes that
preserves the spectrum of the associated Laplacian matrices. We show that the
theory of Spielman and Srivastava for the sparsification of graphs extends to
simplicial complexes via the up Laplacian. In particular, we introduce a
generalized effective resistance for simplices, provide an algorithm for
sparsifying simplicial complexes at a fixed dimension, and give a specific
version of the generalized Cheeger inequality for weighted simplicial
complexes. Finally, we introduce higherorder generalizations of spectral
clustering and label propagation for simplicial complexes and demonstrate via
experiments the utility of the proposed spectral sparsification method for
these applications.