We show that the commonly held assumption that walks can be used to infer properties of digraphs is highly problematic. Since in particular closed walks are describable from combinations of simple cycles, we study the trace monoid formed by these cycles on a digraph under the rule that two such cycles commute if and only if they are vertex disjoint. We show that most graph properties can be lost while maintaining the monoidal structure of cycles and thus cannot be inferred from it, including vertex-transitivity, regularity, planarity, Hamiltonicity, graph spectra, degree distribution and more. Conversely we find that even allowing for multidigraphs, many arrangements of simple cycles are not possible at all. The problem of determining whether a certain arrangement of simple cycles is realizable is highly non-trivial. We show at least that it is decidable and equivalent to the existence of integer solutions to systems of polynomial equations.

et $T \colon \mathbb{N}\to \mathbb{N}$ denote the $3x+1$ function, where $T(n)=n/2$ if $n$ is even, $T(n)=(3n+1)/2$ if $n$ is odd. As an accelerated version of $T$, we define a \emph{jump} at $n \ge 1$ by $\textrm{jp}(n) = T^{(\ell)}(n)$, where $\ell$ is the number of digits of $n$ in base 2. We present computational and heuristic evidence leading to surprising conjectures. The boldest one, inspired by the study of $2^{\ell}-1$ for $\ell \le 500\,000$, states that for any $n \ge 2^{500}$, at most four jumps starting from $n$ are needed to fall below $n$, a strong form of the Collatz conjecture.

We introduce an algorithmic framework to investigate spherical and geodesic growth series of braid groups relatively to the Artin's or Birman-Ko-Lee's generators. We present our experimentations in the case of three and four strands and conjecture rational expressions for the spherical growth series with respect to the Birman-Ko-Lee's generators.

A gapset is the complement of a numerical semigroup in $\mathbb{N}$. In this paper, we characterize all gapsets of multiplicity $m \le 4$. As a corollary, we provide a new simpler proof that the number of gapsets of genus $g$ and fixed multiplicity $m \le 4$ is a nondecreasing function of $g$.

For $g \ge 0$, let $n_g$ denote the number of numerical semigroups of genus $g$. A conjecture by Maria Bras-Amoréoacute;s in 2008 states that the inequality $n_{g} \ge n_{g-1}+n_{g-2}$ should hold for all $g \ge 2$. Here we show that such an inequality holds for the very large subtree of numerical semigroups satisfying $c \le 3m$, where $c$ and $m$ are the conductor and multiplicity, respectively. Our proof is given in the more flexible setting of gapsets, i.e. complements in $\mathbb{N}$ of numerical semigroups.

Defined on Birman-Ko-Lee monoids, the rotating normal form has strong connections with the Dehornoy's braid ordering. It can be seen as a process for selecting between all the representative words of a Birman-Ko-Lee braid a particular one, called rotating word. In this paper we construct, for all $n\geq 2$, a finite-state automaton which recognizes rotating words on $n$ strands, proving that the rotating normal form is regular. As a consequence we obtain the regularity of a $\sigma$-definite normal form defined on the whole braid group.

A Pythagorean triple is a triple of positive integers $a,b,c \in {\mathbb N}_+$ satisfying $a^2+b^2=c^2$. Is it true that, for any finite coloring of ${\mathbb N}_+$, at least one Pythagorean triple must be monochromatic? In other words, is the Diophantine equation $X^2+Y^2=Z^2$ regular? This problem, recently solved for 2-colorings by massive SAT computations Heule et al., 2016, remains widely open for $k$-colorings with $k \ge 3$. In this paper, we introduce morphic colorings of ${\mathbb N}_+$, which are special colorings in finite groups with partly multiplicative properties. We show that, for many morphic colorings in $2$ and $3$ colors, monochromatic Pythagorean triples are unavoidable in rather small integer intervals.

Let $S \subseteq \mathbb{N}$ be a numerical semigroup with multiplicity $m$, conductor $c$ and minimal generating set $P$. Let $L=S \cap [0,c-1]$ and $W(S)=|P||L|-c$. In 1978, Herbert Wilf asked whether $W(S) \ge 0$ always holds, a question known as Wilf's conjecture and open since then. A related number $W_0(S)$, satisfying $W_0(S) \le W(S)$, has recently been introduced. We say that $S$ is a near-miss in Wilf's conjecture if $W_0(S)<0$. Near-misses are very rare. Here we construct infinite families of them, with $c=4m$ and $W_0(S)$ arbitrarily small, and we show that the members of these families still satisfy Wilf's conjecture.

For any positive integer $r$, we exhibit a prime knot $K_r$ with $(20\cdot 2^{r-1}+1)$ crossings whose Jones polynomial $V(K_r)$ is equal to $1$ modulo $2^r$. Our construction rests on a certain $20$-crossing prime tangle $T_{20}$ which is undetectable by the Kauffman bracket polynomial pair mod $2$.

For every finite Coxeter group $\Gamma$, each positive braid in the corresponding braid group admits a unique decomposition as a finite sequence of elements of $\Gamma$, the so-called Garside-normal form. The study of the associated adjacency matrix $\text{Adj}(\Gamma)$ allows to count the number of Garside-normal form of a given length. In this paper we prove that the characteristic polynomial of $\text{Adj}(B_n)$ divides the one of $\text{Adj}(B_{n+1})$. The key point is the use of a Hopf algebra based on signed permutations. A similar result was already known for the type $A$. We observe that this does not hold for type $D$. The other Coxeter types ($I$, $E$, $F$ and $H$) are also studied.

In this paper we describe an algorithm visiting all numerical semigroups up to a given genus using a well suited representation. The interest of this algorithm is that it fits particularly well the architecture of modern computers allowing very large optimizations: we obtain the number of numerical semigroups of genus $g\leq 67$ and we confirm the Wilf conjecture for $g\leq 60$.

Nested Monte-Carlo Search (NMC) and Nested Rollout Policy Adaptation (NRPA) are Monte-Carlo tree search algorithms that have proved their efficiency at solving one-player game problems, such as morpion solitaire or sudoku 16x16, showing that these heuristics could potentially be applied to constraint problems. In the field of Ramsey theory, the weak Schur number $WS(k)$ is the largest integer $n$ for which their exists a partition into $k$ subsets of the integers $[1, n]$ such that there is no $x < y < z$ all in the same subset with $x + y = z$. Several studies have tackled the search for better lower bounds for the Weak Schur numbers $WS(k)$, $k\geq 4$. In this paper we investigate this problem using NMC and NRPA, and obtain a new lower bound for $WS(6)$, namely $WS(6) \geq 582$.

We describe a new algorithm which for each braid returns a quasi-geodesic $\sigma$-definite word representative, defined as a braid word in which the generator $\sigma_i$ with maximal index $i$ appears either only positively or only negatively.

A result by Dehornoy (1992) says that every nontrivial braid admits a $\sigma$-definite word representative, defined as a braid word in which the generator $\sigma_i$ with maximal index $i$ appears with exponents that are all positive, or all negative. This is the ground result for ordering braids. In this paper, we enhance this result and prove that every braid admits a $\sigma$-definite word representative that, in addition, is quasi-geodesic. This establishes a longstanding conjecture. Our proof uses the dual braid monoid and a new normal form called the rotating normal form.

We describe the restriction of the Dehornoy ordering of braids to the dual braid monoids introduced by Birman, Ko and Lee: we give an inductive characterization of the ordering of the dual braid monoids and compute the corresponding ordinal type. The proof consists in introducing a new ordering on the dual braid monoid using the rotating normal form of arXiv:math.GR/0811.3902, and then proving that this new ordering coincides with the standard ordering of braids.

Let $B_n^{+\ast}$ denote the dual braid monoid on n strands, i.e., the submonoid of the braid group consisting of the braids that can be expressed as positive words in the Birman–Ko–Lee generators. We introduce a new normal form on $B_n^{+\ast}$, which is based on expressing every braid of $B_n^{+\ast}$ in terms of a certain finite sequence of braids of $B_{n-1}^{+\ast}$. We deduce an inductive characterization of the Dehornoy ordering of dual braid monoids, and explicitly compute the associated order types.