Search

The critical exponent E ( u ) E(\mathbf u) of an infinite sequence u \mathbf u over a finite alphabet expresses the maximal repetition of a factor in u \mathbf u . By the famous Dejean’s theorem, E ( u ) ≥ 1 + 1 d − 1 E(\mathbf u) \geq 1+\frac 1{d-1} for every d d -ary sequence u \mathbf u . We define the asymptotic critical exponent E ∗ ( u ) E^*(\mathbf u) as the upper limit of the maximal repetition of factors of length n n . We show that for any d > 1 d>1 there exists a d d -ary sequence u \mathbf u having E ∗ ( u ) E^*(\mathbf u) arbitrarily close to 1 1 . Then we focus on the class of d d -ary balanced sequences. In this class, the values E ∗ ( u ) E^*(\mathbf u) are bounded from below by a threshold strictly bigger than 1. We provide a method which enables us to find a d d -ary balanced sequence with the least asymptotic critical exponent for 2 ≤ d ≤ 10 2\leq d\leq 10 .

In 2007, Grytczuk conjectured that for any sequence ( ℓ i ) i ≥ 1 (\ell _i)_{i\ge 1} of alphabets of size 3 3 there exists a square-free infinite word w w such that for all i i , the i i -th letter of w w belongs to ℓ i \ell _i . The result of Thue from 1906 implies that there is an infinite square-free word if all the ℓ i \ell _i are identical. On the other hand, Grytczuk, Przybyło and Zhu showed in 2011 that it also holds if the ℓ i \ell _i are of size 4 4 instead of 3 3 . In this article, we first show that if the lists are of size 4 4 , the number of square-free words is at least 2.45 n 2.45^n (the previous similar bound was 2 n 2^n ). We then show our main result: we can construct such a square-free word if the lists are subsets of size 3 3 of the same alphabet of size 4 4 . Our proof also implies that there are at least 1.25 n 1.25^n square-free words of length n n for any such list assignment. This proof relies on the existence of a set of coefficients verified with a computer. We suspect that the full conjecture could be resolved by this method with a much more powerful computer (but we might need to wait a few decades for such a computer to be available).

A small polygon is a polygon of unit diameter. The maximal width of an equilateral small polygon with n = 2 s n=2^s vertices is not known when s ≥ 3 s \ge 3 . This paper solves the first open case and finds the optimal equilateral small octagon. Its width is approximately 3.24 3.24% larger than the width of the regular octagon: cos ⁡ ( π / 8 ) \cos (\pi /8) . In addition, the paper proposes a family of equilateral small n n -gons, for n = 2 s n=2^s with s ≥ 4 s\ge 4 , whose widths are within O ( 1 / n 4 ) O(1/n^4) of the maximal width.

In 1971, Tutte wrote in an article that "it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian". Motivated by this remark, Horton constructed a counterexample on 96 vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts -- even if they have girth 6 -- it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs. In 1969, Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette's conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4., 19 pages; to appear in Mathematics of Computation

In this paper Butson-type complex Hadamard matrices $\mathrm{BH}(n,q)$ of order $n$ and complexity $q$ are classified for small parameters by computer-aided methods. Our main results include the enumeration of $\mathrm{BH}(21,3)$, $\mathrm{BH}(16,4)$, and $\mathrm{BH}(14,6)$ matrices. There are exactly $72$, 1786763, and $167776$ such matrices, up to monomial equivalence. Additionally, we show an example of a $\mathrm{BH}(14,10)$ matrix for the first time, and show the nonexistence of $\mathrm{BH}(8,15)$, $\mathrm{BH}(11,q)$ for $q\in\{10,12,14,15\}$, and $\mathrm{BH}(13,10)$ matrices., 15 pages, preprint

We investigate Mahonian and Eulerian probability distributions given by inversions and descents in general finite Coxeter groups. We provide uniform formulas for the means and variances in terms of Coxeter group data in both cases. We also provide uniform formulas for the double-Eulerian probability distribution of the sum of descents and inverse descents. We finally establish necessary and sufficient conditions for general sequences of Coxeter groups of increasing rank under which Mahonian and Eulerian probability distributions satisfy central and local limit theorems., Comment: 26 pages incl. appendix. v2: added further computational data, Remark 6.6 about mod-Gaussian convergence. v3: uniform proof of Theorem 4.1 and a uniform double coset count in Corollary 5.4, completely revised Section 6, v4: final version with corrected Proposition 6.4

For $e$ a positive integer, we find restrictions modulo $2^e$ on the coefficients of the characteristic polynomial $\chi_S(x)$ of a Seidel matrix $S$. We show that, for a Seidel matrix of order $n$ even (resp. odd), there are at most $2^{\binom{e-2}{2}}$ (resp. $2^{\binom{e-2}{2}+1}$) possibilities for the congruence class of $\chi_S(x)$ modulo $2^e\mathbb Z[x]$. As an application of these results, we obtain an improvement to the upper bound for the number of equiangular lines in $\mathbb R^{17}$, that is, we reduce the known upper bound from $50$ to $49$., Comment: 21 pages, fixed typo in Lemma 2.1

We present a new algorithmic approach that can be used to determine whether a given quadruple $(f_0,f_1,f_2,f_3)$ is the f-vector of any convex 4-dimensional polytope. By implementing this approach, we classify the f-vectors of 4-polytopes in the range $f_0+f_3\le22$. In particular, we thus prove that there are f-vectors of cellular 3-spheres with the intersection property that are not f-vectors of any convex 4-polytopes, thus answering a question that may be traced back to the works of Steinitz (1906/1922). In the range $f_0+f_3\le22$, there are exactly three such f-vectors with $f_0\le f_3$, namely $(10,32,33,11)$, $(10,33,35,12)$, and $(11,35,35,11)$., 19 pages, several figures and tables

For the elements of a numerical semigroup which are larger than the Frobenius number, we introduce the definition of, seed, by broadening the notion of generator. This new concept allows us to explore the semigroup tree in an alternative efficient way, since the seeds of each descendant can be easily obtained from the seeds of its parent. The paper is devoted to presenting the results which are related to this approach, leading to a new algorithm for computing and counting the semigroups of a given genus.

Given a set $\Pi$ of permutation patterns of length at most $k$, we present an algorithm for building $S_{\le n}(\Pi)$, the set of permutations of length at most $n$ avoiding the patterns in $\Pi$, in time $O(|S_{\le n - 1}(\Pi)| \cdot k + |S_{n}(\Pi)|)$. Additionally, we present an $O(n!k)$-time algorithm for counting the number of copies of patterns from $\Pi$ in each permutation in $S_n$. Surprisingly, when $|\Pi| = 1$, this runtime can be improved to $O(n!)$, spending only constant time per permutation. Whereas the previous best algorithms, based on generate-and-check, take exponential time per permutation analyzed, all of our algorithms take time at most polynomial per outputted permutation. If we want to solve only the enumerative variant of each problem, computing $|S_{\le n}(\Pi)|$ or tallying permutations according to $\Pi$-patterns, rather than to store information about every permutation, then all of our algorithms can be implemented in $O(n^{k+1}k)$ space. Using our algorithms, we generated $|S_5(\Pi)|, \ldots, |S_{16}(\Pi)|$ for each $\Pi \subseteq S_4$ with $|\Pi| > 4$, and analyzed OEIS matches. We obtained a number of potentially novel pattern-avoidance conjectures. Our algorithms extend to considering permutations in any set closed under standardization of subsequences. Our algorithms also partially adapt to considering vincular patterns.

We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete., 28 pages, 12 figures

A new ordering, extending the notion of universal cycles of Chung {\em et al.} (1992), is proposed for the blocks of $k$-uniform set systems. Existence of minimum coverings of pairs by triples that possess such an ordering is established for all orders. Application to the construction of short 2-radius sequences is given, with some new 2-radius sequences found through computer search., Comment: 18 pages, to appear in Mathematics of Computation

Chu has recently shown that the Abel lemma on summations by parts can serve as the underlying relation for Bailey's ${}_6\psi_6$ bilateral summation formula. In other words, the Abel lemma spells out the telescoping nature of the ${}_6\psi_6$ sum. We present a systematic approach to compute Abel pairs for bilateral and unilateral basic hypergeometric summation formulas by using the $q$-Gosper algorithm. It is demonstrated that Abel pairs can be derived from Gosper pairs. This approach applies to many classical summation formulas., Comment: 17 pages

We describe an algorithm for computing boundary slopes of 2-bridge links. As an example, we work out the slopes of the links obtained by 1/k surgery on one component of the Borromean rings. A table of all boundary slopes of all 2-bridge links with 10 or less crossings is also included., Comment: 26 pages, 10 figures

Constructive and nonconstructive techniques are employed to enumerate Latin squares and related objects. It is established that there are (i) 2036029552582883134196099 main classes of Latin squares of order 11; (ii) 6108088657705958932053657 isomorphism classes of one-factorizations of $K_{11,11}$; (iii) 12216177315369229261482540 isotopy classes of Latin squares of order 11; (iv) 1478157455158044452849321016 isomorphism classes of loops of order 11; and (v) 19464657391668924966791023043937578299025 isomorphism classes of quasigroups of order 11. The enumeration is constructive for the 1151666641 main classes with an autoparatopy group of order at least 3., Comment: Minor revision; to appear in Mathematics of Computation