Septoku is a Sudoku variant invented by Bruce Oberg, played on a hexagonal grid of 37 cells. We show that up to rotations, reflections, and symbol permutations, there are only six valid Septoku boards. In order to have a unique solution, we show that the minimum number of given values is six. We generalize the puzzle to other board shapes, and devise a puzzle on a star-shaped board with 73 cells with six givens which has a unique solution. We show how this puzzle relates to the unsolved Hadwiger-Nelson problem in combinatorial geometry.
In this paper, we present a new linear programming (LP) formulation of the Traveling Salesman Problem (TSP). The proposed model has O(n^8) variables and O(n^7) constraints, where n is the number of cities. Our numerical experimentation shows that computational times for the proposed linear program are several orders of magnitude smaller than those for the existing model [3].
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lovasz Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.
This paper studies new properties of the front and back ends of a sorting network, and illustrates the utility of these in the search for new bounds on optimal sorting networks. Search focuses first on the outsides of the network and then on the inner part. All previous works focus only on properties of the front end of networks and on how to apply these to break symmetries in the search. The new, out-side-in, properties help shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimal sorting networks. We present new parallel sorting networks for 17 to 20 inputs. For 17, 19, and 20 inputs these networks are faster than the previously known best networks. For 17 inputs, the new sorting network is shown optimal in the sense that no sorting network using less layers exists.
Asymptotic properties of finitely generated subgroups of free groups, and of finite group presentations, can be considered in several fashions, depending on the way these objects are represented and on the distribution assumed on these representations: here we assume that they are represented by tuples of reduced words (generators of a subgroup) or of cyclically reduced words (relators). Classical models consider fixed size tuples of words (e.g. the few-generator model) or exponential size tuples (e.g. Gromovs density model), and they usually consider that equal length words are equally likely. We generalize both the few-generator and the density models with probabilistic schemes that also allow variability in the size of tuples and non-uniform distributions on words of a given length.Our first results rely on a relatively mild prefix-heaviness hypothesis on the distributions, which states essentially that the probability of a word decreases exponentially fast as its length grows. Under this hypothesis, we generalize several classical results: exponentially generically a randomly chosen tuple is a basis of the subgroup it generates, this subgroup is malnormal and the tuple satisfies a small cancellation property, even for exponential size tuples. In the special case of the uniform distribution on words of a given length, we give a phase transition theorem for the central tree property, a combinatorial property closely linked to the fact that a tuple freely generates a subgroup. We then further refine our results when the distribution is specified by a Markovian scheme, and in particular we give a phase transition theorem which generalizes the classical results on the densities up to which a tuple of cyclically reduced words chosen uniformly at random exponentially generically satisfies a small cancellation property, and beyond which it presents a trivial group.
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovasz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $varepsilon$-regular partition with the number of parts bounded by a polynomial in $varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $varepsilon$-regular partition of $W$ is at least exponential in $varepsilon^{-2}/2^{5log^*varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
We investigate a new oriented variant of the Firefighter Problem. In the traditional Firefighter Problem, a fire breaks out at a given vertex of a graph, and at each time interval spreads to neighbouring vertices that have not been protected, while a constant number of vertices are protected at each time interval. In the version of the problem considered here, the firefighters are able to orient the edges of the graph before the fire breaks out, but the fire could start at any vertex. We consider this problem when played on a graph in one of several graph classes, and give upper and lower bounds on the number of vertices that can be saved. In particular, when one firefighter is available at each time interval, and the given graph is a complete graph, or a complete bipartite graph, we present firefighting strategies that are provably optimal. We also provide lower bounds on the number of vertices that can be saved as a function of the chromatic number, of the maximum degree, and of the treewidth of a graph. For a subcubic graph, we show that the firefighters can save all but two vertices, and this is best possible.
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.
In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of numbers $0<a_1,a_2,ldots,a_nle 1$ such that $sum_{j=1}^n a_j/(1-log a_j)ge C$ for some constant $C>0$, it is possible to find a roughly balanced Boolean function $f$ such that $textrm{Inf}_j[f] < a_j$ for every $1 le j le n$.
