A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, there exists a vertex $w$ in $G$ such that $G - w$ is non-hamiltonian, and $G - v$ is hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J. Graph Theory 79 (2015) 63--81] 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 Four-Color 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{sequence-submodularity} and \emph{sequence-monotonicity} 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 sequence-submodular and sequence-non-decreasing, then there exists a greedy algorithm that achieves $1-1/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 non-decreasing sequence-submodular 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 $1-1/e$, which matches the best known existing performance, and for query rewriting problem the performance of our algorithm is $1- 1/e^{1-1/e}$ which improves upon the best known existing performance in the literature.

We present a new aperiodic tileset containing 11 Wang tiles on 4 colors, and we show that this tileset is minimal, in the sense that no Wang set with either fewer than 11 tiles or fewer than 4 colors is aperiodic. This gives a definitive answer to the problem raised 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 left-to-right maxima. We show that this generating function is a D-finite 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 closed-form constants. We end by proving a limit law: a forbidden pattern of length $n$ has typically $(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations.

A special case of Myerson's classic result describes the revenue-optimal 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 3-space, 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 semi-algebraic 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 3-space. 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 two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

The problem of determining the number of "flooding operations" required to make a given coloured graph monochromatic in the one-player combinatorial game Flood-It 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 edge-density.

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 4-SAT 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 3-SAT 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):2142--2146, 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 1-perfect 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 4-incidence 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 cluster-diameter $\Delta(G)$ of a layering partition of $G$, (2) graphs with tree-length $\lambda$, (3) graphs with tree-breadth $\rho$, (4) $k$-chordal graphs, AT-free graphs and HHD-free graphs. Additionally, we show that the slimness of every 4-chordal graph is at most 2 and characterize those 4-chordal 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 boosting-type 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 local-global 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 long-standing 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 edge-weighted 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 cost-optimal 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 off-line and on-line 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 on-line setting, we give the $2$-competitive algorithm and prove the lower bound of $3/2$ for the competitive ratio for any on-line strategy. For every strategy for trees in the on-line setting, we prove the competitive ratio to be no less than $2$, which can be achieved by the $DFS$ algorithm.

Given a partially-ordered 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 finite-state 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 polynomial-time algorithm to distinguish the two cases, and to compute the order of polynomial growth, with the language specified as an NFA. For context-free 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 five-cycle, 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 Lin--Kernighan heuristic which yields fast convergence. The Lin--Kernighan 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 Lin--Kernighan 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 city-to-city variables-based, 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 time-dependent 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 one-to-one 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 time-dependent traveling salesman problem (TDTSP) as well as the quadratic assignment problem (QAP) are straightforward. The reasons for the non-applicability 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 NP-complete 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 triangle-free 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 cross-intersecting 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}s--Ko--Rado and the Hilton--Milner 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 0-1 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 hard-core 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 higher-order 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, higher-order 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 higher-order 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.