Math Subject Classifications: Combinatorics (05-XX), Number Theory (11-XX),
Computer Science (68-XX), Geometry (51-XX), Convex and Discrete Geometry (52-XX), Linear and multilinear algebra; matrix theory (15-XX),
History and biography (01-XX)
Abstract: For integers \(k\), \(n\) with \(k\), \(n \geq 1\), the \(n\)-color weak Schur number
\(WS_{k}(n)\) is defined as the least integer \(N\), such that for every \(n\)-coloring of the integer
interval \([1,N]\), there exists a monochromatic solution \(x_{1},\dots, x_{k}, x_{k+1}\) in that interval to the equation:
\(x_{1}+x_{2}+\dots+x_{k} =x_{k+1},\) with \(x_{i} \neq x_{j}\), when \(i\neq j.\)
In this paper, we obtain the exact values of \(WS_{6}(2)=166\), \(WS_{7}(2)=253\), \(WS_{3}(3)=94\) and \(WS_{4}(3)=259\)
and we show lower bounds on \(n\)-color weak Schur number \(WS_{k}(n)\) for \(n=2,3\).
Abstract: We introduce self-similar algebras and groupsclosely related to the Thue–Morse sequence, and begin their
investigation by describing a character on them, the "spread" character.
Abstract: A doubly stochastic matrix is a square matrix \(A=\left(a_{ij}\right)\) of non-negative
real numbers such that \(\sum_{i}a_{ij}=\sum_{j}a_{ij}=1\). The Chebyshev polynomial of the first kind
is defined by the recurrence relation \(T_0(x)=1, T_1(x)=x\), and \(T_{n+1}(x)=2xT_n(x)-T_{n-1}(x).\)
In this paper, we show a \(2^k\times 2^k\) (for each integer \(k\geq 1\))
doubly stochastic matrix whose characteristic polynomial is \(x^2-1\)
times a product of irreducible Chebyshev polynomials of the first kind (upto rescaling by rational numbers).
Abstract: Let \(p\) be a prime and let \(\varphi\in {\mathbb Z}_p[x_1, x_2, \ldots, x_p]\)
be a symmetric polynomial, where \({\mathbb Z}_p\) is the field of \(p\) elements.
A sequence \(T\) in \({\mathbb Z}_p\) of length \(p\) is called a \(\varphi\)-zero sequence
if \(\varphi(T)=0\); a sequence in \({\mathbb Z}_p\) is called \(\varphi\)-zero free if it does not contain any \(\varphi\)-zero
subsequence. Motivated by the EGZ theorem for the prime \(p\), we define a symmetric polynomial
\(\varphi\in {\mathbb Z}_p[x_1, x_2, \ldots, x_p]\) to be an EGZ polynomial if it satisfies the following two conditions:
\((i)\) every sequence in \({\mathbb Z}_p\) of length \(2p-1\) contains a \(\varphi\)-zero subsequence and
\((ii)\) the \(\varphi\)-zero free sequences of length \(2p-2\) are the sequences which contain exactly any two
residues where each residue appears \(p-1\) times. For a positive integer \(k\) and a prime \(p\),
a power-sum polynomial over \({\mathbb Z}_p\) is defined as \(s_{k,p}=\sum_{j=1}^px_j^k\). In this paper we answer the question of whether there are EGZ polynomials among the power-sum polynomials.
Indeed, \(s_{k,p}\) is an EGZ polynomial if and only if \(\gcd(k, p-1)=1\) and these polynomials can
be derived from \(s_{1,p}\) and a permutation polynomial. Next, we introduce a definition of rational number, \(r(s_{k,p}, \mathbb{Z}_p)\in (0,1]\),
which measures the deviation of a power-sum polynomial from being an EGZ polynomial.
Among some other results we determine \(r(s_{k,p}, \mathbb{Z}_p)\) for every prime \(p\) and positive integer \(k\).
Abstract: Let \({\mathcal L}(t)\) represent the equation \(x_1+x_2+\cdots+x_{t-1}=x_t\).
For \(k\geq 1\), \(0\leq i\leq k-1\), and \(t_i\geq 3\), the generalized Schur number \(S(k;t_0,t_1,\ldots,t_{k-1})\) is the
least positive integer \(m\) such that for every \(k\)-colouring of \(\left\{1,2,\ldots,m\right\}\), there exists an \(i\in\set{0,1,\ldots,k-1}\)
such that there exists a solution to \({\mathcal L}(t_i)\) that is monochromatic in colour \(i\). In this paper,
we report twenty-six previously unknown values of \(S(k; t_0, t_1, \ldots,t_{k-1})\)
and conjecture that for \(4\leq t_0\leq t_1\leq t_2\), \(S(3;t_0,t_1,t_2)=t_2t_1t_0-t_2t_1-t_2-1\).
Abstract: A \(t\)-AP is a sequence of the form \(a,a+d,\ldots,a+(t-1)d\),
where \(a,d\in \mathbb{Z}\). Given a finite set \(X\) and positive integers \(d, t, a_1,a_2,\ldots,a_{t-1}\), define
\(\nu(X,d)\) as \(|\set{(x,y):x,y\in{X},y>x, y-x=d}|\) and
\((a_1,a_2,\ldots,a_{t-1};d)\) as a collection \(X\) s.t. \(\nu(X,d\cdot{i})\geq a_i\) for \(1\leq i\leq t-1\).
In this paper, we investigate
the structure of sets with bounded number of pairs with certain gaps.
Let \((t-1,t-2,\ldots,1; d)\) be called a \(t\)-AP distance-set of size at least \(t\).
A \(k\)-colouring of integers \(1,2,\ldots, n\) is a mapping \(\set{1,2,\ldots,n}\rightarrow \set{0,1,\ldots,k-1}\) where
\(0,1,\ldots,k-1\) are colours.
Let \(ww(k,t)\) denote the
smallest positive integer \(n\) such that every \(k\)-colouring of \(1,2,\ldots,n\)
contains a monochromatic \(t\)-AP distance-set for some \(d>0\).
We conjecture that \(ww(2,t)\geq t^2\) and prove the lower bound for most cases.
We also generalize the notion of \(ww(k,t)\) and prove several lower bounds.
Abstract: In this note, we investigate a problem on maximum planar distance sets by Erdos and Fishburn (1996), and
prove a recent conjecture presented by Ahmed and Snevily (2013) on distance sets in the triangular lattice.
We also enumerate the number of distinct distances in a hexagonal array in the traingular lattice.
Abstract: In this paper
we present results and conjectures on the ordinary van der Waerden numbers \(vdw(2; 3, t)\) and on the new palindromic van der Waerden numbers
\(vdwpd(2; 3, t)\).
We have computed the exact value of the previously unknown number \(vdw(2; 3, 19) = 349\), and we provide new lower bounds for \(20 \leq t \leq 39\),
where for \(20 \leq t \leq 30\) we conjecture these bounds to be exact.
The lower bounds for \(vdw(2; 3, t)\) with \(24 \leq t \leq 30\) refute the conjecture that \(vdw(2; 3, t)\leq t^2\) as suggested in {blr2008}.
Based on the known values of \(vdw(2; 3, t)\), we investigate regularities to better understand the lower bounds of \(vdw(2; 3, t)\).
Motivated by such regularities, we introduce palindromic van der Waerden numbers \(vdwpd(k; t_0,\dots,t_{k-1})\),
which are defined as the ordinary numbers \(vdw(k;t_0,\dots,t_{k-1})\), but where only palindromic solutions are considered,
reading the same from both ends. Different from the situation for ordinary van der Waerden numbers, these ``numbers''
need actually to be pairs of numbers.
We compute \(vdwpd(2;3,t)\) for \(3 \leq t \leq 27\), and we provide bounds for \(t \leq 39\), which we believe to be exact for \(t \leq 35\).
All computations are based on SAT solving, and we discuss the various relations between SAT solving and Ramsey theory. Especially we introduce a novel (open-source) SAT solver, the \(tawSolver\), which performs best on the SAT instances studied here, and which is actually the original DLL-solver, but with an efficient implementation and a modern heuristic typical for look-ahead solvers (applying the theory developed in K2007).
Abstract: We investigate the claim that for every tree \(T\) (with \(m\) edges),
there exists an \(\alpha\)-labeling of \(T\), or else
there exists a graph \(H_T\) with an \(\alpha\)-labeling such that
\(H_T\) can be decomposed into two edge-disjoint copies of \(T\).
We prove that the above claim is true for comets \({\mathcal C}_{m,2}\).
This is particularly noteworthy since comets \({\mathcal C}_{m,2}\) are known to have
arbitrarily large \(\alpha\)-deficits.
Abstract: A planar point-set \(X\) in Euclidean plane is called a \(k\)-distance set
if there are exactly \(k\) different distances among the points in \(X\).
The function \(g(k)\) denotes the maximum number of points in the Euclidean plane that
is a \(k\)-distance set.
In 1996, Erdos and Fishburn conjectured that for \(k\geq 7\), every
\(g(k)\)-point subset of the plane that determines \(k\) different distances is similar to a subset of the
triangular lattice.
We believe that if \(g(k)\) is an increasing function of \(k\),
then the conjecture is false.
We present data supporting our claim
and a method of construction that unifies known optimal point configurations for \(k\geq 3\).
Abstract: In this paper, we are concerned with calculating \(r(k,n)\),
the length of the longest \(k\)-AP free subsequences in \(1,2,\ldots,n\).
We prove the basic inequality \(r(k,n) \leq n- \lfloor{m/2}\rfloor\),
where \(n=m(k-1) + r\) and \( r < k-1 \). We also discuss a generalization of a famous conjecture of Szekeres (as appears in Erdos and Turan)
and desecribe a simple greedy algorithm that appears to give an optimal \(k\)-AP free sequence
infinitely often. We provide many exact values of \(r(k,n)\) in the Appendix.
Abstract: A Roller Coaster permutation is a permutation, along with all of its subsequences,
that changes from increasing to decreasing (and vice versa) a maximum number of times.
We offer a few conjectures (enumerative as well as structural) along with data describing some
surprising properties of these permutations.
Abstract: Let \(S(h,k)\) be the least positive integer such that any \(2\)-coloring of the interval \([1,S(h,k)]\) must admit either
[(i)] a monochromatic solution to \(x_1+\ldots+x_{h-1}=x_h\) with \(x_1 < x_2 < \ldots < x_h\) or
[(ii)] a monochromatic solution to \(x_1+\ldots+x_{k-1}=x_k\) with \(x_1 < x_2 < \ldots < x_k\).
We prove \(S(3,3)=9\), \(S(3,4)=16\), and for all \(k\geq 5\),
\(S(3,k)=
\left\{
\begin{array}{ll}
3k^2/2-7k/2+3 & \text{if $k\equiv 0,1\pmod{4}$},\\
3k^2/2-7k/2+4 & \text{if $k\equiv 2,3\pmod{4}$}.\\
\end{array}
\right.
\)
Abstract: The van der Waerden number \(w(k; t_0, t_1,\ldots,t_{k-1})\) is the smallest positive integer
\(n\) such that every \(k\)-coloring of the sequence \({1,2,\ldots,n}\) yields a monochromatic
arithmetic progression of length \(t_i\) for some color \(i\in\set{0,1,\ldots,k-1}\).
In this paper, we propose a problem-specific backtracking algorithm for computing
van der Waerden numbers \(w(k;t_0,t_1,\ldots,t_{k-1})\)
with \(t_0=t_1=\cdots=t_{j-1}=2\), where \(k\geq j+2\), and \(t_i\geq 3\) for \(i\geq j\).
We report some previously unknown van der Waerden numbers using this method.
We also report the exact value of the previously unknown van der Waerden number \(w(2;5,7)\).
Abstract: The van der Waerden number \(w(k;t_0,t_1,\ldots,t_{k-1})\)
is the smallest integer \(m\) such that every partition \(P_0\cup P_1\cup \cdots P_{k-1}\)
of the integers \(\{1,2,\ldots,m\}\), there is always a block \(P_j\) that contains an
arithmetic progression of length \(t_j\). In this paper, we report the exact value
of the previously unknown van der Waerden number \(w(2;4,9)\), some lower bounds of \(w(2;5,t)\),
and polynomial upper-bound conjectures for \(w(2;4,t)\) and \(w(2;5,t)\). We also present
an efficient SAT-encoding of \(w(k;t_0,t_1,\ldots,t_{k-1})\) for \(k\geqslant 3\) using which
we have computed the exact value of \(w(3;3,3,6)\) and some lower bounds of \(w(3;t_0,t_1,t_2)\).
Abstract: The van der Waerden number \(w(r; k_1, k_2, \ldots, k_r)\) is the least integer \(m\) such that
for every partition \(P_1\cup P_2\cup\cdots\cup P_r\) of the set \(\{1,2,\ldots,m\}\),
there is an index \(j\) in \(\{1,2,\ldots,r\}\) such that \(P_j\) contains an arithmetic progression of \(k_j\) terms.
We have computed exact values of the previously unknown van der Waerden numbers \(w(2; 3, 17)\)
and \(w(2; 3, 18)\).
Abstract: The van der Waerden number \(w(r; k_1, k_2, \cdots, k_r)\) is the least \(m\) such that
given any partition \(\{1,2,\cdots,m\}=P_1\cup P_2\cup\cdots\cup P_r\),
there is an index \(j\in\{1,2,\cdots,r\}\) such that \(P_j\) contains an arithmetic progression of length \(k_j\).
We have computed exact values of some (30) previously unkown van der Waerden numbers
and also computed lower bounds of others.
Let \(w_d(r; k_1, k_2, \cdots, k_r)\) be the least \(m\) such that
given any partition \(\{1,2,\cdots,m\}=P_1\cup P_2\cup\cdots\cup P_r\),
there is an index \(j\in\{1,2,\cdots,r-1\}\) such that \(P_j\) contains an arithmetic progression of length \(k_j\), or
\(P_r\) contains an arithmetic progression of length \(k_r\) with common difference at most \(d\).
A table of observed values of \(w_d(r; k_1, k_2, \cdots, k_r)\) for \(d=1,2,\cdots,\lfloor{m-1\over{k_r-1}}\rfloor\) is given.
022. On the \(3\)-color off-diagonal generalized Schur numbers \(S(3; 2, k_1, k_2)\)
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz, Submitted to a journal.
021. On the \(3\)-color off-diagonal generalized Schur numbers \(S(3; 2,2,k)\)
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz, Submitted to a journal.
020. Growth of Rational Languages related to Self-Similar Algebras
José M. R. Caballero and Tanbir Ahmed, submitted to a journal.
019. Lower bounds and exact values of the \(2\)-color off-diagonal generalized weak Schur numbers \(WS(2; k_1, k_2)\)
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz, Procedia Computer Science, 223 (2023), 403-405.
XII LAGOS, 2023
018. Exact values and lower bounds on the \(n\)-color weak Schur numbers for \(n = 2, 3\).
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz,
The Ramanujan Journal, 62 (2) (2023), 347-363.
, Open access, (2023).
017. Thue-Morse substitution and self similar groups and algebras
Laurent Bartholdi, José M. R. Caballero, and Tanbir Ahmed, Algebra and Discrete Mathematics, 34 (1) (2022), 1-14.
016. A Family of doubly stochastic matrices involving Chebyshev polynomials.
Tanbir Ahmed and José M. R. Caballero, Algebra and Discrete Mathematics, 27 (2) (2019), 155-164.
MR3982300.
015. Power Sum Polynomials as Relaxed EGZ Polynomials.
Tanbir Ahmed, Arie Bialostocki, Thang Pham, and Le Anh Vinh,
Integers19 (2019),
A49.
MR4017190.
014. On Generalized Schur Numbers
Tanbir Ahmed and Daniel Schaal,
Experimental Mathematics, 25 (2) (2016), 213-218.
MR3463569.
(PDF)
013. On Colouring Integers without t-AP distance sets
Tanbir Ahmed, Algebra and Discrete Mathematics, 22 (1) (2016), 1-10.
MR3573541.
(PDF)
012. On Distance Sets in the Triangular Lattice
Tanbir Ahmed and David Wildstrom,
Bull. Inst. Combin. Appl. 75 (2015), 118-127.
MR3444619.
(PDF)
011. Remembering Hunter Snevily
Tanbir Ahmed, André Kézdy, and Douglas B. West,
Bull. Inst. Combin. Appl., 73 (2015), 7-17.
MR3331369.
(PDF)
010. On the van der Waerden numbers \(w(2; 3, t)\)
Tanbir Ahmed, Oliver Kullmann, and Hunter Snevily,
Discrete Applied Mathematics, 174 (2014), 27-51.
MR3215454.
--- Recently (2022), Ben Green
in New Lower Bounds for van der Waerden Numbers,
disproved the much-speculated conjecture \(w(2; 3, k)=\cal{O}(k^2)\) (originally formulated by Ron Graham in around 2004, and subsequently supported with data by others and ourselves)
by constructing a red-blue coloring of \(1,2,\ldots,N\) with no blue arithmetic progression of length 3 and no red arithmetic
progression of length \(e^{C(\log N)^{3/4}(\log\log N)^{1/4}}\), and consequently
showing that \(w(2; 3, k)\) is bounded from below by \(k^{b(k)}\) where \(b(k) = c\left({\log{k}\over\log\log{k}}\right)^{1/3}\).
See Erica Klarreich's
Quanta Magazine article
Mathematician Hurls Structure and Disorder Into Century-Old Problem.
--- (See D. E. Knuth's
Volume 4, Fascicle 6: Chapter on Satisfiability)
--- (See Wikipedia entry of
Van der Waerden numbers for my contributions in that list)
009. The α-labeling number of comets is 2
Tanbir Ahmed and Hunter Snevily,
Bull. Inst. Combin. Appl., 72 (2014), 25-40.
(PDF)
MR3362514.
--- (See Joseph A. Gallian's A Dynamic Survey of Graph Labeling)
008. Sparse Distance Sets in the Triangular Lattice
Tanbir Ahmed and Hunter Snevily, Electronic Journal of Combinatorics,
20 (4) (2013), P33.
MR3158272.
007. Unique Sequences Containing No k-Term Arithmetic Progressions
Tanbir Ahmed, Janusz Dybizbański, and Hunter Snevily,
Electronic Journal of Combinatorics,
20 (4) (2013), P29.
MR3158268.
006. Some properties of Roller Coaster Permutations
Tanbir Ahmed and Hunter Snevily,
Bull. Inst. Combin. Appl., 68 (2013), 55-69.
(PDF)
MR3136863.
--- (See Biedl et al., Rollercoasters: long sequences without short runs., SIAM J. Discrete Math. 33, No. 2, 845-861 (2019).
--- (See two conjectures
in the Open Problems Garden)
--- (See William Adamczak
A Note on the Structure of Roller Coaster Permutations, preprint, May 2016)
--- (See William Adamczak, Jacob Boni
Roller Coaster Permutations and Partition Numbers, preprint, March 2017)
005. Strict Schur Numbers
Tanbir Ahmed, Michael G. Eldredge, Jonathan J. Marler, and Hunter Snevily,
Integers, 13 (2013).
A22.
MR3083484.
004. Some more van der Waerden numbers
Tanbir Ahmed, Journal of Integer Sequences,
16 (2013), Article 13.4.4.MR3056628.
003. On computation of exact van der Waerden numbers
Tanbir Ahmed, Integers, 12 (3) (2012), 417-425.
Online version: 11 (2011), A71.
MR2955523.
002. Two new van der Waerden numbers: w(2; 3, 17) and w(2; 3, 18)
Tanbir Ahmed, Integers,
10 (2010), 369-377, A32.
MR2684128.
-- First applied DIVIDE-AND-CONQUER Distributed SAT-Solving to compute these numbers in around 2009.
001. Some new van der Waerden numbers and some van der Waerden-type numbers
Tanbir Ahmed, Integers,
9 (2009), 65-76, A06
MR2506138.
--- (See tawSolver 1.0:
an efficient implementation of the DPLL Algorithm.)
Some Results in Extremal Combinatorics
[PDF]
Ph.D. Thesis, 2013, Concordia University.
Advisor: Prof. Clement LamAn Implementation of the DPLL Algorithm
[PDF]
M. Comp. Sci. Thesis, 2009, Concordia University.
Advisor: Prof. Vašek Chvátal