Division of Science

Programs

General

External

Contact

Department of Mathematics
The City College of New York
160 Convent Avenue
New York, NY 10031

Phone: (212) 650-5346
Fax: (212) 650-6294
math@ccny.cuny.edu

Sean Cleary's Publications

  • Sean Cleary and Roland Maio: Edge conflicts do not determine geodesics in the associahedron, SIAM Journal on Discrete Mathematics, Vol. 32 (2018), no. 2, 1003-1015.

    There are no known efficient algorithms to calculate distance in the one-skeleta of associahedra, a problem that is equivalent to finding rotation distance between rooted binary trees or the flip distance between polygonal triangulations. One measure of the difference between trees is the number of conflicting edge pairs, and a natural way of trying to find short paths is to minimize successively this number of conflicting edge pairs using flip operations in the corresponding triangulations. We describe examples that show that the number of such conflicts does not always decrease along geodesics. Thus, a greedy algorithm that always chooses a transformation that reduces conflicts will not produce a geodesic in all cases. Further, for any specified amount, there are examples of pairs of all large sizes showing that the number of conflicts can increase by that amount along any geodesic between the pairs.

  • Sean Cleary: Thompson's Group, Office hours with a geometric group theorist, Princeton University Press, 2017.

    Book chapter covering the important example of Thompson's group F and its metric properties.

  • Jose Burillo, Sean Cleary, and Claas E. Röver: Obstructions for subgroups of Thompson's group V, Geometric and cohomological group theory, London Math. Soc. Lecture Note Ser., 444, Cambridge Univ. Press, 2018.

    Thompson's group V has a rich variety of subgroups, containing all finite groups, all finitely generated free groups and all finitely generated abelian groups, the finitary permutation group of a countable set, as well as many wreath products and other families of groups. Here, we describe some obstructions for a given group to be a subgroup of V.

  • Sean Cleary and Roland Maio: Edge conflicts can increase along minimal rotation-distance paths, Proceedings of the 27th Annual Fall Workshop on Computational Geometry, Stony Brook University, (2017).

    Rotation distance between binary trees measures differences in tree shape by counting the minimal number of rotations needed to transform one tree to another. There are no known polynomial-time algorithms for calculating rotation distance. The number of conflicts between edges is a rough measure of tree distance and has been useful in comparing trees for the extent of similarity. Here we show that the number of conflicts can rise along minimal length paths for rotation distance, which precludes finding such paths by examining edge conflicts alone.

  • Jose Burillo, Sean Cleary, Armando Martino, and Claas Roever: Commensurations and Metric Properties of Houghton's Groups, Pacific Journal of Mathematics, Vol. 285 (2016), No. 2, 289-301..

    We describe the automorphism groups and the abstract commensurators of Houghton's groups. Then we give sharp estimates for the word metric of these groups and deduce that the commensurators embed into the corresponding quasi-isometry groups. As a further consequence, we obtain that the Houghton group on two rays is at least quadratically distorted in those with three or more rays.

  • Sean Cleary and Conchita Martinez-Perez: Undistorted embeddings of metabelian groups of finite Prüfer rank, New York Journal of Mathematics, 21 (2015) 1027-1054.

    General arguments of Baumslag and Bieri guarantee that any metabelian group of finite Pr\"ufer rank can be embedded in a metabelian constructible group. Here, we consider the metric behavior of a rich class of examples and analyze the distortions of specific embeddings.

  • Timothy Chu and Sean Cleary: Expected maximum vertex valence in pairs of polygonal triangulations, Involve, a journal of mathematics Vol. 8 (2015), No. 5, 763–770.

    Edge-flip distance between triangulations of polygons is equivalent to rotation distance between rooted binary trees. Both distances measure the extent of similarity of configurations. There are no known polynomial-time algorithms for computing edge-flip distance. The best known exact universal upper bounds on rotation distance arise from measuring the maximum total va- lence of a vertex in the corresponding triangulation pair obtained by a duality construction. Here we describe some properties of the distribution of maximum vertex valences of pairs of triangulations related to such upper bounds.

  • Sean Cleary, Andrew Rechnitzer, and Thomas Wong: Common Edges in Rooted Trees and Polygonal Triangulations, Electronic Journal of Combinatorics, Volume 20, Issue 1 (2013).

    Rotation distance between rooted binary trees measures the degree of similarity of two trees with ordered leaves and is equivalent to edge-flip distance between triangular subdivisions of regular polygons. There are no known polynomial-time algorithms for computing rotation distance. Existence of common edges makes computing rotation distance more manageable by breaking the problem into smaller subproblems. Here we describe the distribution of common edges between randomly-selected triangulations and measure the sizes of the remaining pieces into which the common edges separate the polygons. We find that asymptotically there is a large component remaining after sectioning off numerous small polygons which gives some insight into the distribution of such distances and the difficulty of such distance computations, and we analyze the distributions of the sizes of the largest and smaller resulting polygons.

  • Sean Cleary, John Passaro and Yasser Toruno: Average reductions between random tree pairs, Involve, a journal of mathematics (2015) #8-1.

    There are a number of measures of degrees of similarity between rooted binary trees. Many of these ignore sections of the trees which are in complete agreement. We use computational experiments to investigate the statistical characteristics of such a measure of tree similarity for ordered, rooted, binary trees. We generate the trees used in the experiments iteratively, using the Yule process modeled upon speciation.

  • Jose Burillo, Sean Cleary and Claas Roever: Addendum to ‘Commensurations and finite index subgroups of Thompson’s group F.’, Geometry & Topology 17 (2013) 1199–1203.

    We show that the abstract commensurator of Thompson's group F is composed of four building blocks: two isomorphism types of simple groups, the multiplicative group of the positive rationals and a cyclic group of order two. The main result establishes the simplicity of a certain group of piecewise linear homeomorphisms of the real line.

  • José Burillo and Sean Cleary: The automorphism group of Thompson's group F: subgroups and metric properties, Revista Matemática Iberoamericana, Vol. 29, #3 (2013), 809--828..

    We describe some of the geometric properties of the automorphism group Aut(F) of Thompson's group F. We give realizations of Aut(F) geometrically via periodic tree pair diagrams, which lead to natural presentations and give effective methods for estimating the word length of elements. We study some natural subgroups of Aut(F) and their metric properties. In particular, we show that the subgroup of inner automorphisms of F is at least quadratically distorted in Aut(F), whereas other subgroups of Aut(F) isomorphic to F are undistorted.

  • Timothy Chu and Sean Cleary: Expected conflicts in pairs of rooted binary trees, Involve, a journal of mathematics #6 (2013).

    Rotation distance between rooted binary trees measures the extent of similarity of two trees with ordered leaves. There are no known polynomial-time algorithms for computing rotation distance. If there are common edges or immediately changeable edges between a pair of trees, the rotation distance problem breaks into smaller subproblems. The number of crossings or conflicts of a tree pair also gives some measure of the extent of similarity of two trees. Here we describe the distribution of common edges and immediately changeable edges between randomly-selected pairs of trees via computer experiments, and examine the distribution of the amount of conflicts between such pairs.

  • Sean Cleary, Susan Hermiller, Melanie Stein, and Jennifer Taback: Tame combing and almost convexity conditions, Math. Zeit., 269 (2011), no. 3-4, 879–915.

    We give the first examples of groups which admit a tame combing with linear radial tameness function with respect to any choice of finite presentation, but which are not minimally almost convex on a standard generating set. Namely, we explicitly construct such combings for Thompson's group F and the Baumslag-Solitar groups BS(1, p) with p \ge 3. In order to make this construction for Thompson's group F, we significantly expand the understanding of the Cayley complex of this group with respect to the standard finite presentation. In particular we describe a quasigeodesic set of normal forms and combinatorially classify the arrangements of 2-cells adjacent to edges that do not lie on normal form paths.

  • Sean Cleary and Katherine St. John: A Linear-Time Approximation Algorithm for Rotation Distance, Journal of Graph Algorithms and Applications, 2010, Vol. 14, no. 2.

    Rotation distance between rooted binary trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. We give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees. .

  • Jose Burillo and Sean Cleary: Metric properties of higher dimensional Thompson's groups, Pacific Journal of Mathematics, 248, #1 (2010).

    Higher-dimensional Thompson's groups nV are finitely presented groups described by Brin which generalize dyadic self-maps of the unit interval to dyadic self-maps of n-dimensional unit cubes. We describe some of the metric properties of higher-dimensional Thompson's groups. We give descriptions of elements based upon tree-pair diagrams and give upper and lower bounds for word length in terms of the size of the diagrams. Though these upper and lower bounds are somewhat separated, we show that there are elements realizing the lower bounds and that the fraction of elements which are close to the upper bound converges to 1, showing that the bounds are optimal and that the upper bound is generically achieved.

  • Sean Cleary, Murray Elder, Andrew Rechnitzer, and Jennifer Taback: Random subgroups of Thompson's group , Groups, Geometry and Dynamics, Vol 4, #1, 2010..

    We consider random subgroups of Thompson's group $F$ with respect to two natural stratifications of the set of all $k$ generator subgroups of this group. We find that the isomorphism classes of subgroups which occur with positive density vary greatly between the two stratifications. We give the first known examples of {\em persistent} subgroups, whose isomorphism classes occur with positive density within the set of $k$-generator subgroups, for all $k$ greater than some $k_0$. Additionally, Thompson's group provides the first example of a group without a generic isomorphism class of subgroup. In $F$, there are many isomorphism classes of subgroups with positive density less than one. Elements of $F$ are represented uniquely by reduced pairs of finite rooted binary trees. We compute the asymptotic growth rate and a generating function for the number of reduced pairs of trees, which we show is D-finite and not algebraic.

  • Sean Cleary and Katherine St. John: Rotation distance is fixed-parameter tractable., Inform. Process. Lett. 109 (2009), no. 16, 918--922.

    Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernalization of the initial trees to trees with size bounded by 5k.

  • Blake Fordham and Sean Cleary: Minimal length elements of Thompson's groups F(p), Geom. Dedicata 141 (2009), 163--180..

    We describe a method for determining the minimal length of elements in the generalized Thompson's groups F(p). We compute the length of an element by constructing a tree pair diagram for the element, classifying the nodes of the tree and summing associated weights from the pairs of node classi¯cations. We use this method to e®ectively ¯nd minimal length representatives of an element.

  • Jose Burillo and Sean Cleary: Metric properties of braided Thompson's groups, Indiana Univ. Math. J. 58 (2009), no. 2, 605--615.

    Braided Thompson's groups are finitely presented groups introduced by Brin and Dehornoy which contain the ordinary braid groups $Bn$, the finitary braid group $B{\infty}$ and Thompson's group $F$ as subgroups. We describe some of the metric properties of braided Thompson's groups and give upper and lower bounds for word length in terms of the number of strands and the number of crossings in the diagrams used to represent elements.

  • Jose Burillo, Sean Cleary, Melanie Stein and Jennifer Taback: Combinatorial and metric properties of Thompson's group T, Transactions of the American Mathematical Society, #361 ,2009, pp. 631--652. .

    e discuss metric and combinatorial properties of Thompson's group T, such as the normal forms for elements and uniqueness of tree pair diagrams. We relate these properties to those of Thompson's group F when possible, and highlight combinatorial differences between the two groups. We define a set of unique normal forms for elements of T arising from minimal factorizations of elements into convenient pieces. We show that the number of carets in a reduced representative of T estimates the word length, that F is undistorted in T, and that cyclic subgroups of T are undistorted. We show that every element of T has a power which is conjugate to an element of F and describe how to recognize torsion elements in T.

  • Jose Burillo, Sean Cleary and Claas Roever: Commensurations and subgroups of finite index of Thompson's group F, Geom. Topol. 12 (2008), no. 3, 1701--1709.

    We determine the abstract commensurator com(F) of Thompson's group F and describe it in terms of piecewise linear homeomorphisms of the real line and in terms of tree pair diagrams. We show com (F) is not finitely generated and determine which subgroups of finite index in F are isomorphic to F. We show that the natural map from the commensurator group to the quasi-isometry group of F is injective.

  • Tom Brady, Jose Burillo, Sean Cleary and Melanie Stein: Pure braid subgroups of braided Thompson's groups, Publ. Mat. 52 (2008) # 1.

    We describe pure braided versions of Thompson's group F. These groups, BF and $\hat{BF}$, are subgroups of the braided versions of Thompson's group V, introduced by Brin and Dehornoy. Unlike V, elements of F are order-preserving self-maps of the interval and we use pure braids together with elements of F thus preserving order. We define these groups and give normal forms for elements and describe infinite and finite presentations of these groups.

  • Sean Cleary and Tim Riley: Erratum to: ``A finitely presented group with unbounded dead-end depth', Proc. Amer. Math. Soc. 134 (2006), no. 2, 343--349; MR2176000]. Proc. Amer. Math. Soc. 136 (2008), no. 7, 2641-2645.

    he dead-end depth of an element g of a group G, with respect to a generating set A is the distance from g to the complement of the radius $dA(1,g)$ closed ball, in the word metric $dA$ defined with respect to A. We exhibit a finitely presented group G with a finite generating set with respect to which there is no upper bound on the dead-end depth of elements. The authors regret that the published version of this article (Proc. Amer. Math. Soc., 134(2), pp.343-349, 2006) contains a significant error concerning the model for G described in Section 2. We are grateful to Jorg Lehnert for pointing out our mistake. In this corrected version, that model has been overhauled, and that has necessitated a number of changes in the subsequent arguments.

  • Sean Cleary and Katherine St. John: Analyses of haplotype inference algorithms, Far East Journal of Mathematics, Vol. 28, #2, 2008.

    We present experimental and theoretical analyses of data requirements for haplotype inference algorithms. Our experiments include a broad range of problem sizes under two standard models of tree distribution and were designed to yield statistically robust results despite the size of the sample space.
    Our results validate Gusfield's conjecture that a population size of n log n is required to give (with high probability) sufficient information to deduce the n haplotypes and their complete evolutionary history.
    The experimental results inspired our theoretical bounds on the population size. We also analyze the population size required to deduce some fixed fraction of the evolutionary history of a set of n haplotypes and establish linear bounds on the required sample size. These linear bounds are also shown theoretically.

  • Jose Burillo, Sean Cleary and Burt Wiest: Computational explorations in Thompson's group F, Geometric Group Theory, Geneva and Barcelona Conferences, Trends in Mathematics, Birkhauser, 2007.

    We describe the results of some computational explorations in Thompson's group F. We describe experiments to estimate the cogrowth of F with respect to its standard finite generating set, designed to address the subtle and difficult question whether or not Thompson's group is amenable. We also describe experiments to estimate the exponential growth rate of F and the rate of escape of symmetric random walks with respect to the standard generating set.

  • Sean Cleary and Jennifer Taback: Bounding right-arm rotation distances, International Journal of Algebra and Computation 17 #2, 2007.

    Rotation distance measures the difference in shape between binary trees of the same size by counting the minimum number of rotations needed to transform one tree to the other. We describe several types of rotation distance where restrictions are put on the locations where rotations are permitted, and provide upper bounds on distances between trees with a fixed number of nodes with respect to several families of these restrictions. These bounds are sharp in a certain asymptotic sense and are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

  • Sean Cleary, Fabrizio Luccio and Linda Pagli: Refined upper bounds for right-arm rotation distances, Theoretical Computer Science #377, #1-3, 2007.

    Rotation distances measure the difference in shape in rooted binary trees. We construct sharp bounds on maximal right-arm rotation distance and restricted right-arm rotation distance for trees of size n. These bounds sharpen the results of Cleary and Taback and incorporate the lengths of the right side of the trees to improve the bounds.

  • Sean Cleary: Distortion of wreath products in some finitely presented groups, Pacific Journal of Mathematics, 228 #1, 2006.

    Wreath products such as Z wr Z are not finitely-presentable yet can occur as subgroups of finitely presented groups. Here we compute the distortion of Z wr Z as a subgroup of Thompson's group F and as a subgroup of Baumslag's metabelian group G.

  • Sean Cleary and Tim Riley: A finitely presented group with unbounded dead-end depth, Proceedings of the AMS, 134 #2, 2006.

    The dead-end depth of an element g of a group G, with respect to a generating set A is the distance from g to the complement of the radius $dA(1,g)$ closed ball, in the word metric $dA$ defined with respect to A. We exhibit a finitely presented group G with a finite generating set with respect to which there is no upper bound on the dead-end depth of elements.

  • Sean Cleary and Jennifer Taback: Metric properties of the lamplighter group as an automata group, Geometric Methods in Group Theory, Contemp. Math. Series., AMS, 372, 2005.

    We examine the geometry of the Cayley graph of the lamplighter group with respect to the generating set rising from its interpretation as an automata group due to Grigorchuk and Zuk. We find some metric behavior with respect to this generating set analogous to the metric behavior in the standard wreath product generating set. The similar metric behavior includes expressions for geodesic paths and families of "dead-end" elements, which are endpoints of terminating geodesic rays. We also exhibit some different metric behavior between these two generating sets related to the existence of "seesaw" elements.

  • Sean Cleary, Murray Elder and Jennifer Taback: Cone types and geodesic languages for lamplighter groups and Thompson's group F, Journal of Algebra, 303 #2, 2006.

    We study languages of geodesics in lamplighter groups and Thompson's group F. We show that the lamplighter groups $L_n$ have infinitely many cone types, have no regular geodesic languages, and have 1-counter, context-free and counter geodesic languages with respect to certain generating sets. We show that the full language of geodesics with respect to one generating set for the lamplighter group is not counter but is context-free, while with respect to another generating set the full language of geodesics is counter and context-free. In Thompson's group F with respect to the standard finite generating set, we show there are infinitely many cone types and no regular language of geodesics with respect to the standard finite generating set. We show that the existence of families of "seesaw" elements with respect to a given generating set in a finitely generated infinite group precludes a regular language of geodesics and guarantees infinitely many cone types with respect to that generating set.

  • Sean Cleary and Jennifer Taback: Seesaw words in Thompson's group F, Geometric Methods in Group Theory, Contemp. Math. Series., AMS, 372, 2005.

    We describe a family of words in Thompson's group F which present a challenge to the question of finding canonical minimal length representatives, and which show that F is not combable by geodesics. These words have the property that there are only two possible suffixes of long lengths for geodesic paths to the word from the identity; one is of the form $g^k$ and the other of the form $g^{-k}$ where g is a generator of the group.

  • Sean Cleary and Jennifer Taback: Dead end words in lamplighter groups and other wreath products, Quarterly Journal of Mathematics, 56 #2, 2005.

    We explore the geometry of the Cayley graphs of the lamplighter groups and a wide range of wreath products. We show that these groups have dead end elements of arbitrary depth with respect to their natural generating sets. An element $w$ in a group $G$ with finite generating set $X$ is a dead end element if no geodesic ray from the identity to $w$ in the Cayley graph $\Gamma(G,X)$ can be extended past $w$. Additionally, we describe some nonconvex behavior of paths between elements in these Cayley graphs and seesaw words, which are potential obstructions to these graphs satisfying the $k$-fellow traveller property.

  • Sean Cleary and Jennifer Taback: Geometric quasi-isometric embeddings into Thompson's group F, New York Journal of Mathematics, #9 , 2003.

    We use geometric techniques to investigate several examples of quasi-isometrically embedded subgroups of Thompson's group F. Many of these are explored using the metric properties of the shift map phi in F. These subgroups have simple geometric but complicated algebraic descriptions. We present them to illustrate the intricate geometry of Thompson's group F as well as the interplay between its standard finite and infinite presentations. These subgroups include those of the form F^m cross Z^n, for integral non-negative m and n, which were shown to occur as quasi-isometrically embedded subgroups by Burillo and Guba and Sapir.

  • Sean Cleary and Jennifer Taback: Combinatorial properties of Thompson's group F, Transactions of the American Mathematical Society, 356, #7, 2004.

    Abstract: We study some combinatorial properties of the word metric of Thompson's group F in the standard two generator finite presentation. We explore connections between the tree pair diagram representing an element w of F, its normal form in the infinite presentation, its word length, and minimal length representatives of it. We estimate word length in terms of the number and type of carets in the tree pair diagram and show sharpness of those estimates. In addition we explore some properties of the Cayley graph of F with respect to the two generator finite presentation. Namely, we exhibit the form of "dead end" elements in this Cayley graph, and show that it has no "deep pockets". Finally, we discuss a simple method for constructing minimal length representatives for strictly positive or negative words.

  • Sean Cleary and Jennifer Taback: Thompson's group F is not almost convex, Journal of Algebra, 270 #1, 2003.

    We show that Thompson's group F does not satisfy Cannon's almost convexity condition AC(n) for any integer n in the standard finite two generator presentation. To accomplish this, we construct a family of pairs of elements at distance n from the identity and distance 2 from each other, which are not connected by a path lying inside the n-ball of length less than k for increasingly large k. Our techniques rely upon Fordham's method for calculating the length of a word in F and upon an analysis of the generators' geometric actions on the tree pair diagrams representing elements of F.

  • Jose Burillo, Sean Cleary and Melanie Stein: Metrics and embeddings of generalizations of Thompson's group F, Transactions of the American Mathematical Society, 353, #4, 2001.

    The distance from the origin in the word metric for generalizations F(p) of Thompson's group F is quasi-isometric to the number of carets in the reduced rooted tree diagrams representing the elements of F(p). This interpretation of the metric is used to prove that every F(p) admits a quasi-isometric embedding into every F(q), and also to study the behavior of the shift maps under these embeddings.


Up