Department of Mathematics and Statistics
http://hdl.handle.net/10680/289
Fri, 06 Dec 2019 13:50:45 GMT2019-12-06T13:50:45ZBinary Words Avoiding xxRx and Strongly Unimodal Sequences
http://hdl.handle.net/10680/1758
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
Currie, James D.; Rampersad, Narad
In previous work, Currie and Rampersad showed that the growth of the number
of binary words avoiding the pattern xxxR was intermediate between polynomial and
exponential. We now show that the same result holds for the growth of the number
of binary words avoiding the pattern xxRx. Curiously, the analysis for xxRx is much
simpler than that for xxxR. We derive our results by giving a bijection between the
set of binary words avoiding xxRx and a class of sequences closely related to the class
of “strongly unimodal sequences”.
Mon, 14 Sep 2015 00:00:00 GMThttp://hdl.handle.net/10680/17582015-09-14T00:00:00ZA ternary square-free sequence avoiding factors equivalent to abcacba
http://hdl.handle.net/10680/1756
A ternary square-free sequence avoiding factors equivalent to abcacba
Currie, James D.
We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern xyzxzyx. In fact, we
-characterize all the (two-way) infinite ternary square-free words avoiding letter pattern xyzxzyx
-characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern xyzxzyx
-show that the number of ternary square-free words of length n avoiding letter pattern xyzxzyx grows exponentially with
n.
Fri, 27 May 2016 00:00:00 GMThttp://hdl.handle.net/10680/17562016-05-27T00:00:00ZA family of formulas with reversal of high avoidability index
http://hdl.handle.net/10680/1755
A family of formulas with reversal of high avoidability index
Currie, James; Mol, Lucas; Rampersad, Narad
We present an infinite family of formulas with reversal whose avoidability index is bounded between 4 and 5, and we show that several members of the family have avoidability index 5. This family is particularly interesting due to its size and the simple structure of its members. For each k ∈ {4,5}, there are several previously known avoidable formulas (without reversal) of avoidability index k, but they are small in number and they all have rather complex structure.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10680/17552017-01-01T00:00:00ZAvoidability index for binary patterns with reversal
http://hdl.handle.net/10680/1754
Avoidability index for binary patterns with reversal
Currie, James D.; Lafrance, Phillip
For every pattern p over the alphabet {x,x^R,y,y^R}, we specify the least k such that p is k-avoidable.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10680/17542017-01-01T00:00:00ZBinary words containing infinitely many overlaps
http://hdl.handle.net/10680/1753
Binary words containing infinitely many overlaps
Currie, James D.; Rampersad, Narad; Shallit, Jeffrey
We characterize the squares occurring in infinite overlap-free binary words and construct various \alpha power-free binary words containing infinitely many overlaps.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/10680/17532006-01-01T00:00:00ZAttainable lengths for circular binary words avoiding k-powers
http://hdl.handle.net/10680/1752
Attainable lengths for circular binary words avoiding k-powers
Currie, James D.; Aberkane, Ali
We show that binary circular words of length n avoiding 7/3+ powers exist
for every sufficiently large n. This is not the case for binary circular words
avoiding k+ powers with k < 7/3
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10680/17522005-01-01T00:00:00ZThe Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
http://hdl.handle.net/10680/1751
The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
Currie, James; Rampersad, Narad; Aberkane, Ali
We show that the number of ternary words of length n avoiding abelian cubes grows
faster than r^n, where r = 2^{1/24}
Sat, 19 Jun 2004 00:00:00 GMThttp://hdl.handle.net/10680/17512004-06-19T00:00:00ZThe metric dimension and metric independence of a graph
http://hdl.handle.net/10680/1746
The metric dimension and metric independence of a graph
Currie, James; Oellerman, Ortrud R.
A vertex x of a graph G resolves two vertices u and v of G if the
distance from x to u does not equal the distance from x to v. A set
S of vertices of G is a resolving set for G if every two distinct vertices
of G are resolved by some vertex of S. The minimum cardinality of a
resolving set for G is called the metric dimension of G. The problem of
nding the metric dimension of a graph is formulated as an integer pro-
gramming problem. It is shown how a relaxation of this problem leads
to a linear programming problem and hence to a fractional version of
the metric dimension of a graph. The linear programming dual of this
problem is considered and the solution to the corresponding integer
programming problem is called the metric independence of the graph.
It is shown that the problem of deciding whether, for a given graph
G, the metric dimension of G equals its metric independence is NP-
complete. Trees with equal metric dimension and metric independence
are characterized. The metric independence number is established for
various classes of graphs.
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/10680/17462001-01-01T00:00:00ZSliding Down Inclines with Fixed Descent Time: a Converse to Galileo's Law of Chords
http://hdl.handle.net/10680/1741
Sliding Down Inclines with Fixed Descent Time: a Converse to Galileo's Law of Chords
Babb, Jeff
Mon, 01 Dec 2008 00:00:00 GMThttp://hdl.handle.net/10680/17412008-12-01T00:00:00ZThe Brachistochrone Problem: Mathematics for a Broad Audience via a Large Context Problem
http://hdl.handle.net/10680/1728
The Brachistochrone Problem: Mathematics for a Broad Audience via a Large Context Problem
Babb, Jeff; Currie, James
Large context problems (LCP) are useful in teaching the history of science. In this article we consider the brachistochrone problem in a context stretching from Euclid through the Bernoullis. We highlight a variety of results understandable by students without a background in analytic geometry. By a judicious choice of methods and themes, large parts of the history of calculus can be made accessible to students in Humanities or Education.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/10680/17282008-01-01T00:00:00Z