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.
023. A Note on the Rado numbers \(R_k(3,c)\)
Tanbir Ahmed, Robert Malo, Daniel Schaal, Submitted to a journal. Ramsey Theory on the Integers022. 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. Ramsey Theory on the IntegersSAT-Solving021. 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. Ramsey Theory on the IntegersSAT-Solving020. Establishing 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, Submitted to a journal. Ramsey Theory on the IntegersSAT-Solving019. Lower bounds and exact values of the \(2\)-color off-diagonal generalized weak Schur numbers \(WS(2; k_1, k_2)\)conference
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz, Procedia Computer Science, 223 (2023), 403-405.
XII LAGOS, 2023. Ramsey Theory on the IntegersSAT-Solving018. Exact values and lower bounds on the \(n\)-color weak Schur numbers for \(n = 2, 3\).journal
Tanbir Ahmed, Luis Boza, Maria P. Revuelta, and Maria I. Sanz,
The Ramanujan Journal, 62 (2) (2023), 347-363.
, Open access, (2023). Ramsey Theory on the IntegersSAT-Solving017. Thue-Morse substitution and self similar groups and algebrasjournal
Laurent Bartholdi, José M. R. Caballero, and Tanbir Ahmed, Algebra and Discrete Mathematics, 34 (1) (2022), 1-14. Self-Similar Algebra016. A Family of doubly stochastic matrices involving Chebyshev polynomials.journal
Tanbir Ahmed and José M. R. Caballero, Algebra and Discrete Mathematics, 27 (2) (2019), 155-164.
MR3982300. Self-Similar Algebra015. Power Sum Polynomials as Relaxed EGZ Polynomials.journal
Tanbir Ahmed, Arie Bialostocki, Thang Pham, and Le Anh Vinh,
Integers19 (2019),
A49.
MR4017190. Zero-Sum Ramsey Theory014. On Generalized Schur Numbersjournal
Tanbir Ahmed and Daniel Schaal,
Experimental Mathematics, 25 (2) (2016), 213-218.
MR3463569.
(PDF) Ramsey Theory on the IntegersSAT-Solving013. On Colouring Integers without t-AP distance setsjournal
Tanbir Ahmed, Algebra and Discrete Mathematics, 22 (1) (2016), 1-10.
MR3573541.
(PDF) Ramsey Theory on the IntegersSAT-Solving012. On Distance Sets in the Triangular Latticejournal
Tanbir Ahmed and David Wildstrom,
Bull. Inst. Combin. Appl. 75 (2015), 118-127.
MR3444619.
(PDF) Combinatorial Geometry011. Remembering Hunter Snevilyjournal
Tanbir Ahmed, André Kézdy, and Douglas B. West,
Bull. Inst. Combin. Appl., 73 (2015), 7-17.
MR3331369.
(PDF) Research Memoir010. On the van der Waerden numbers \(w(2; 3, t)\)journal
Tanbir Ahmed, Oliver Kullmann, and Hunter Snevily,
Discrete Applied Mathematics, 174 (2014), 27-51.
MR3215454. Ramsey Theory on the IntegersSAT-Solving
--- The paper got a citation in 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
--- 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.
009. The α-labeling number of comets is 2journal
Tanbir Ahmed and Hunter Snevily,
Bull. Inst. Combin. Appl., 72 (2014), 25-40.
(PDF)
MR3362514. Graph Labeling
--- (See Joseph A. Gallian's A Dynamic Survey of Graph Labeling)
008. Sparse Distance Sets in the Triangular Latticejournal
Tanbir Ahmed and Hunter Snevily, Electronic Journal of Combinatorics,
20 (4) (2013), P33.
MR3158272. Combinatorial Geometry007. Unique Sequences Containing No k-Term Arithmetic Progressionsjournal
Tanbir Ahmed, Janusz Dybizbański, and Hunter Snevily,
Electronic Journal of Combinatorics,
20 (4) (2013), P29.
MR3158268. Combinatorics006. Some properties of Roller Coaster Permutationsjournal
Tanbir Ahmed and Hunter Snevily,
Bull. Inst. Combin. Appl., 68 (2013), 55-69.
(PDF)
MR3136863. Combinatorics
--- (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 Numbersjournal
Tanbir Ahmed, Michael G. Eldredge, Jonathan J. Marler, and Hunter Snevily,
Integers, 13 (2013).
A22.
MR3083484. Ramsey Theory on the Integers004. Some more van der Waerden numbersjournal
Tanbir Ahmed, Journal of Integer Sequences,
16 (2013), Article 13.4.4.MR3056628. Ramsey Theory on the IntegersSAT-Solving003. On computation of exact van der Waerden numbersjournal
Tanbir Ahmed, Integers, 12 (3) (2012), 417-425.
Online version: 11 (2011), A71.
MR2955523. Ramsey Theory on the IntegersSAT-Solving002. Two new van der Waerden numbers: w(2; 3, 17) and w(2; 3, 18)journal
Tanbir Ahmed, Integers,
10 (2010), 369-377, A32.
MR2684128. Ramsey Theory on the IntegersSAT-Solving
-- 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 numbersjournal
Tanbir Ahmed, Integers,
9 (2009), 65-76, A06
MR2506138. Ramsey Theory on the IntegersSAT-Solving
--- (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