Source author record

Jonathan Chappelon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT Discrete Mathematics math.GR math.MG

Catalog footprint

Research overview

16works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The Square Frobenius Number

Let $S=\left\langle s_1,\ldots,s_n\right\rangle$ be a numerical semigroup generated by the relatively prime positive integers $s_1,\ldots,s_n$ . Let $k\geqslant 2$ be an integer. In this paper, we consider the following $k$ -power variant of the Frobenius number of $S$ defined as ${}^{k\!}r\!\left(S\right):= \text{ the largest } k \text{-power integer not belonging to } S.$ In this paper, we investigate the case $k=2$ . We give an upper bound for ${}^{2\!}r\!\left(S_A\right)$ for an infinite family of semigroups $S_A$ generated by {\em arithmetic progressions}. The latter turns out to be the exact value of ${}^{2\!}r\!\left(\left\langle s_1,s_2\right\rangle\right)$ under certain conditions. We present an exact formula for ${}^{2\!}r\!\left(\left\langle s_1,s_1+d \right\rangle\right)$ when $d=3,4$ and $5$ , study ${}^{2\!}r\!\left(\left\langle s_1,s_1+1 \right\rangle\right)$ and ${}^{2\!}r\!\left(\left\langle s_1,s_1+2 \right\rangle\right)$ and put forward two relevant conjectures. We finally discuss some related questions.

preprint2021arXiv

Symmetric binary Steinhaus triangles and parity-regular Steinhaus graphs

A binary Steinhaus triangle is a triangle of zeroes and ones that points down and with the same local rule as the Pascal triangle modulo 2. A binary Steinhaus triangle is said to be rotationally symmetric, horizontally symmetric or dihedrally symmetric if it is invariant under the 120 degrees rotation, the horizontal reflection or both, respectively. The first part of this paper is devoted to the study of linear subspaces of rotationally symmetric, horizontally symmetric and dihedrally symmetric binary Steinhaus triangles. We obtain simple explicit bases for each of them by using elementary properties of the binomial coefficients. A Steinhaus graph is a simple graph with an adjacency matrix whose upper-triangular part is a binary Steinhaus triangle. A Steinhaus graph is said to be even or odd if all its vertex degrees are even or odd, respectively. One of the main results of this paper is the existence of an isomorphism between the linear subspace of even Steinhaus graphs and a certain linear subspace of dihedrally symmetric binary Steinhaus triangles. This permits us to give, in the second part of this paper, an explicit basis for even Steinhaus graphs and for the vector space of parity-regular Steinhaus graphs; i.e., the linear subspace of Steinhaus graphs that are even or odd. Finally, in the last part of this paper, we consider the generalized Pascal triangles, that are triangles of zeroes and ones, that point up now, and always with the same local rule as the Pascal triangle modulo 2. New simple bases for each linear subspace of symmetric generalized Pascal triangles are deduced from the results of the first part.

preprint2016arXiv

A universal sequence of integers generating balanced Steinhaus figures modulo an odd number

In this paper, we partially solve an open problem, due to J.C. Molluzzo in 1976, on the existence of balanced Steinhaus triangles modulo a positive integer $n$ , that are Steinhaus triangles containing all the elements of $\mathbb{Z}/n\mathbb{Z}$ with the same multiplicity. For every odd number $n$ , we build an orbit in $\mathbb{Z}/n\mathbb{Z}$ , by the linear cellular automaton generating the Pascal triangle modulo $n$ , which contains infinitely many balanced Steinhaus triangles. This orbit, in $\mathbb{Z}/n\mathbb{Z}$ , is obtained from an integer sequence called the universal sequence. We show that there exist balanced Steinhaus triangles for at least $2/3$ of the admissible sizes, in the case where $n$ is an odd prime power. Other balanced Steinhaus figures, such as Steinhaus trapezoids, generalized Pascal triangles, Pascal trapezoids or lozenges, also appear in the orbit of the universal sequence modulo $n$ odd. We prove the existence of balanced generalized Pascal triangles for at least $2/3$ of the admissible sizes, in the case where $n$ is an odd prime power, and the existence of balanced lozenges for all admissible sizes, in the case where $n$ is a square-free odd number.

preprint2016arXiv

Balanced simplices

An additive cellular automaton is a linear map on the set of infinite multidimensional arrays of elements in a finite cyclic group $\mathbb{Z}/m\mathbb{Z}$ . In this paper, we consider simplices appearing in the orbits generated from arithmetic arrays by additive cellular automata. We prove that they are a source of balanced simplices, that are simplices containing all the elements of $\mathbb{Z}/m\mathbb{Z}$ with the same multiplicity. For any additive cellular automaton of dimension $1$ or higher, the existence of infinitely many balanced simplices of $\mathbb{Z}/m\mathbb{Z}$ appearing in such orbits is shown, and this, for an infinite number of values $m$ . The special case of the Pascal cellular automata, the cellular automata generating the Pascal simplices, that are a generalization of the Pascal triangle into arbitrary dimension, is studied in detail.

preprint2016arXiv

Complete Kneser Transversals

Let $k,d,λ\geqslant1$ be integers with $d\geqslantλ$ . Let $m(k,d,λ)$ be the maximum positive integer $n$ such that every set of $n$ points (not necessarily in general position) in $\mathbb{R}^{d}$ has the property that the convex hulls of all $k$ -sets have a common transversal $(d-λ)$ -plane. It turns out that $m(k, d,λ)$ is strongly connected with other interesting problems, for instance, the chromatic number of Kneser hypergraphs and a discrete version of Rado's centerpoint theorem. In the same spirit, we introduce a natural discrete version $m^*$ of $m$ by considering the existence of complete Kneser transversals. We study the relation between them and give a number of lower and upper bounds of $m^*$ as well as the exact value in some cases. The main ingredient for the proofs are Radon's partition theorem as well as oriented matroids tools. By studying the alternating oriented matroid we obtain the asymptotic behavior of the function $m^*$ for the family of cyclic polytopes.

preprint2016arXiv

Möbius function of semigroup posets through Hilbert series

In this paper, we investigate the M{ö}bius function $μ\_{\mathcal{S}}$ associated to a (locally finite) poset arising from a semigroup $\mathcal{S}$ of $\mathbb{Z}^m$ . We introduce and develop a new approach to study $μ\_{\mathcal{S}}$ by using the Hilbert series of $\mathcal{S}$ . The latter enables us to provide formulas for $μ\_{\mathcal{S}}$ when $\mathcal{S}$ belongs to certain families of semigroups. Finally, a characterization for a locally finite poset to be isomorphic to a semigroup poset is given.

preprint2016arXiv

On generalized Frame-Stewart numbers

For the multi-peg Tower of Hanoi problem with $k \geqslant 4$ pegs, so far the best solution is obtained by the Stewart's algorithm based on the the following recurrence relation: $\mathrm{S}\_k(n)=\min\_{1 \leqslant t \leqslant n} \left\{2 \cdot \mathrm{S}\_k(n-t) + \mathrm{S}\_{k-1}(t)\right\}$ , $\mathrm{S}\_3(n) = 2^n -- 1$ . In this paper, we generalize this recurrence relation to $\mathrm{G}\_k(n) = \min\_{1\leqslant t\leqslant n}\left\{ p\_k\cdot \mathrm{G}\_k(n-t) + q\_k\cdot \mathrm{G}\_{k-1}(t) \right\}$ , $\mathrm{G}\_3(n) = p\_3\cdot \mathrm{G}\_3(n-1) + q\_3$ , for two sequences of arbitrary positive integers $\left(p\_i\right)\_{i \geqslant 3}$ and $\left(q\_i\right)\_{i \geqslant 3}$ and we show that the sequence of differences $\left(\mathrm{G}\_k(n)- \mathrm{G}\_k(n-1)\right)\_{n \geqslant 1}$ consists of numbers of the form $\left(\prod\_{i=3}^{k}q\_i\right) \cdot \left(\prod\_{i=3}^{k}{p\_i}^{α\_i}\right)$ , with $α\_i\geqslant 0$ for all $i$ , arranged in nondecreasing order. We also apply this result to analyze recurrence relations for the Tower of Hanoi problems on several graphs.

preprint2016arXiv

On Ramsey numbers of complete graphs with dropped stars

Let $r(G,H)$ be the smallest integer $N$ such that for any $2$ -coloring (say, red and blue) of the edges of $K\_n$ , $n\geqslant N$ , there is either a red copy of $G$ or a blue copy of $H$ . Let $K\_n-K\_{1,s}$ be the complete graph on $n$ vertices from which the edges of $K\_{1,s}$ are dropped. In this note we present exact values for $r(K\_m-K\_{1,1},K\_n-K\_{1,s})$ and new upper bounds for $r(K\_m,K\_n-K\_{1,s})$ in numerous cases. We also present some results for the Ramsey number of Wheels versus $K\_n-K\_{1,s}$ .

preprint2016arXiv

On the Möbius function of the locally finite poset associated with a numerical semigroup

Let $S$ be a numerical semigroup and let $\left(\mathbb{Z},\leqslant\_S\right)$ be the (locally finite) poset induced by $S$ on the set of integers $\mathbb{Z}$ defined by $x \leqslant\_S y$ if and only if $y-x\in S$ for all integers $x$ and $y$ . In this paper, we investigate the M{ö}bius function associated to $\left(\mathbb{Z},\leqslant\_S\right)$ when $S$ is an arithmetic semigroup.

preprint2016arXiv

On the multiplicative order of $a^n$ modulo $n$

Let $n$ be a positive integer and $α_n$ be the arithmetic function which assigns the multiplicative order of $a^n$ modulo $n$ to every integer $a$ coprime to $n$ and vanishes elsewhere. Similarly, let $β_n$ assign the projective multiplicative order of $a^n$ modulo $n$ to every integer $a$ coprime to $n$ and vanishes elsewhere. In this paper, we present a study of these two arithmetic functions. In particular, we prove that for positive integers $n_1$ and $n_2$ with the same square-free part, there exists an exact relationship between the functions $α_{n_1}$ and $α_{n_2}$ and between the functions $β_{n_1}$ and $β_{n_2}$ . This allows us to reduce the determination of $α_n$ and $β_n$ to the case where $n$ is square-free. These arithmetic functions recently appeared in the context of an old problem of Molluzzo, and more precisely in the study of which arithmetic progressions yield a balanced Steinhaus triangle in $\mathbb{Z}/n\mathbb{Z}$ for $n$ odd.

preprint2016arXiv

On the problem of Molluzzo for the modulus 4

We solve the currently smallest open case in the 1976 problem of Molluzzo on $\mathbb{Z}/m\mathbb{Z}$ , namely the case $m=4$ . This amounts to constructing, for all positive integer $n$ congruent to $0$ or $7 \bmod{8}$ , a sequence of integers modulo $4$ of length $n$ generating, by Pascal's rule, a Steinhaus triangle containing $0,1,2,3$ with equal multiplicities.

preprint2015arXiv

Connected covering numbers

A connected covering is a design system in which the corresponding {\em block graph} is connected. The minimum size of such coverings are called {\em connected coverings numbers}. In this paper, we present various formulas and bounds for several parameter settings for these numbers. We also investigate results in connection with {\em Turán systems}. Finally, a new general upper bound, improving an earlier result, is given. The latter is used to improve upper bounds on a question concerning oriented matroid due to Las Vergnas.

preprint2014arXiv

Ramsey for complete graphs with dropped cliques

Let $K\_{[k,t]}$ be the complete graph on $k$ vertices from which a set of edges, induced by a clique of order $t$ , has been dropped. In this note we give two explicit upper bounds for $R(K\_{[k\_1,t\_1]},\dots, K\_{[k\_r,t\_r]})$ (the smallest integer $n$ such that for any $r$ -edge coloring of $K\_n$ there always occurs a monochromatic $K\_{[k\_i,t\_i]}$ for some $i$ ). Our first upper bound contains a classical one in the case when $k\_1=\cdots =k\_r$ and $t\_i=1$ for all $i$ . The second one is obtained by introducing a new edge coloring called {\em $χ\_r$ -colorings}. We finally discuss a conjecture claiming, in particular, that our second upper bound improves the classical one in infinitely many cases.

preprint2013arXiv

Modular Schur numbers

For any positive integers l and m, a set of integers is said to be (weakly) l-sum-free modulo m if it contains no (pairwise distinct) elements $x_1,x_2,...,x_l,y$ satisfying the congruence $x_1+\...+x_l\equiv y\bmod{m}$ . It is proved that, for any positive integers k and l, there exists a largest integer $n$ for which the set of the first $n$ positive integers $\{1,2,\...,n\}$ admits a partition into k (weakly) l-sum-free sets modulo m. This number is called the generalized (weak) Schur number modulo $m$ , associated with k and l. In this paper, for all positive integers k and l, the exact value of these modular Schur numbers are determined for m=1, 2 and 3.

preprint2009arXiv

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size $n$ which is symmetric, with diagonal of zeros, and whose upper-triangular coefficients satisfy $a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$ for all $2\leq i<j\leq n$ . Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices $K_2$ is the only regular Steinhaus graph of odd degree. Using Dymacek's theorem, we prove that if $(a_{i,j})_{1\leq i,j\leq n}$ is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix $(a_{i,j})_{2\leq i,j\leq n-1}$ is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size $n$ whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on $\lceil \frac{n}{24}\rceil$ parameters for all even numbers $n$ , and on $\lceil \frac{n}{30}\rceil$ parameters in the odd case. This result permits us to verify the Dymacek's conjecture up to 1500 vertices in the odd case.

preprint2008arXiv

On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups

Let $X$ be a finite sequence of length $m\geq 1$ in $\mathbb{Z}/n\mathbb{Z}$ . The \textit{derived sequence} $\partial X$ of $X$ is the sequence of length $m-1$ obtained by pairwise adding consecutive terms of $X$ . The collection of iterated derived sequences of $X$ , until length 1 is reached, determines a triangle, the \textit{Steinhaus triangle $ΔX$ generated by the sequence $X$ }. We say that $X$ is \textit{balanced} if its Steinhaus triangle $ΔX$ contains each element of $\mathbb{Z}/n\mathbb{Z}$ with the same multiplicity. An obvious necessary condition for $m$ to be the length of a balanced sequence in $\mathbb{Z}/n\mathbb{Z}$ is that $n$ divides the binomial coefficient $\binom{m+1}{2}$ . It is an open problem to determine whether this condition on $m$ is also sufficient. This problem was posed by Hugo Steinhaus in 1963 for $n=2$ and generalized by John C. Molluzzo in 1976 for $n\geq3$ . So far, only the case $n=2$ has been solved, by Heiko Harborth in 1972. In this paper, we answer positively Molluzzo's problem in the case $n=3^k$ for all $k\geq1$ . Moreover, for every odd integer $n\geq3$ , we construct infinitely many balanced sequences in $\mathbb{Z}/n\mathbb{Z}$ . This is achieved by analysing the Steinhaus triangles generated by arithmetic progressions. In contrast, for any $n$ even with $n\geq4$ , it is not known whether there exist infinitely many balanced sequences in $\mathbb{Z}/n\mathbb{Z}$ . As for arithmetic progressions, still for $n$ even, we show that they are never balanced, except for exactly 8 cases occurring at $n=2$ and $n=6$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jonathan Chappelon

Research overview

Is this your work?

16 publications

The Square Frobenius Number

Symmetric binary Steinhaus triangles and parity-regular Steinhaus graphs

A universal sequence of integers generating balanced Steinhaus figures modulo an odd number

Balanced simplices

Complete Kneser Transversals

Möbius function of semigroup posets through Hilbert series

On generalized Frame-Stewart numbers

On Ramsey numbers of complete graphs with dropped stars

On the Möbius function of the locally finite poset associated with a numerical semigroup

On the multiplicative order of $a^n$ modulo $n$

On the problem of Molluzzo for the modulus 4

Connected covering numbers

Ramsey for complete graphs with dropped cliques

Modular Schur numbers

Regular Steinhaus graphs of odd degree

On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups

See the researcher in context

Building this map preview

Jonathan Chappelon

Research overview

Is this your work?

16 publications

The Square Frobenius Number

Symmetric binary Steinhaus triangles and parity-regular Steinhaus graphs

A universal sequence of integers generating balanced Steinhaus figures modulo an odd number

Balanced simplices

Complete Kneser Transversals

Möbius function of semigroup posets through Hilbert series

On generalized Frame-Stewart numbers

On Ramsey numbers of complete graphs with dropped stars

On the Möbius function of the locally finite poset associated with a numerical semigroup

On the multiplicative order of ana^nan modulo nnn

On the problem of Molluzzo for the modulus 4

Connected covering numbers

Ramsey for complete graphs with dropped cliques

Modular Schur numbers

Regular Steinhaus graphs of odd degree

On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups

See the researcher in context

Building this map preview

On the multiplicative order of $a^n$ modulo $n$