• ### Low complexity algorithms in knot theory(1803.04908)

March 27, 2018 math.CO, math.GT, math.GR
We show that the genus problem for alternating knots with $n$ crossings has linear time complexity and is in Logspace$(n)$. Almost all alternating knots of given genus possess additional combinatorial structure, we call them standard. We show that the genus problem for these knots belongs to $TC^0$ circuit complexity class. We also show, that the equivalence problem for such knots with $n$ crossings has time complexity $n\log (n)$ and is in Logspace$(n)$ and $TC^{0}$ complexity classes.
• ### Maximal torsion-free subgroups of certain lattices of hyperbolic buildings and Davis complexes(1607.01678)

July 6, 2016 math.GR
We give an explicit construction of a maximal torsion-free finite-index subgroup of a certain type of Coxeter group. The subgroup is constructed as the fundamental group of a finite and non-positively curved polygonal complex. First we consider the special case where the universal cover of this polygonal complex is a hyperbolic building, and we construct finite-index embeddings of the fundamental group into certain cocompact lattices of the building. We show that in this special case the fundamental group is an amalgam of surface groups over free groups. We then consider the general case, and construct a finite-index embedding of the fundamental group into the Coxeter group whose Davis complex is the universal cover of the polygonal complex. All of the groups which we embed have minimal index among torsion-free subgroups, and therefore are maximal among torsion-free subgroups.
• ### Hyperbolic triangular buildings without periodic planes of genus two(1409.1401)

Oct. 19, 2015 math.CO, math.GR
We study surface subgroups of groups acting simply transitively on vertex sets of certain hyperbolic triangular buildings. The study is motivated by Gromov's famous surface subgroup question: Does every one-ended hyperbolic group contain a subgroup which is isomorphic to the fundamental group of a closed surface of genus at least 2? Here we consider surface subgroups of the 23 torsion free groups acting simply transitively on the vertices of hyperbolic triangular buildings of the smallest non-trivial thickness. These groups gave the first examples of cocompact lattices acting simply transitively on vertices of hyperbolic triangular Kac-Moody buildings that are not right-angled. With the help of computer searches we show, that in most of the cases there are no periodic apartments invariant under the action of a genus two surface. The existence of such an action would imply the existence of a surface subgroup, but it is not known, whether the existence of a surface subgroup implies the existence of a periodic apartment. These groups are the first candidates for groups that have no surface subgroups arising from periodic apartments.
• ### Quadratic Equations in Hyperbolic Groups are NP-complete(1306.0941)

Sept. 22, 2015 math.GR
We prove that in a torsion-free hyperbolic group $\Gamma$, the length of the value of each variable in a minimal solution of a quadratic equation $Q=1$ is bounded by $N|Q|^3$ for an orientable equation, and by $N|Q|^{4}$ for a non-orientable equation, where $|Q|$ is the length of the equation, and the constant $N$ can be computed. We show that the problem, whether a quadratic equation in $\Gamma$ has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in $\Gamma$. If additionally $\Gamma$ is non-cyclic, then this problem (of deciding existence of a solution) is NP-complete. We also give a slightly larger bound for minimal solutions of quadratic equations in a toral relatively hyperbolic group.
• ### Series of $p$-groups with Beauville structure(1405.3872)

July 19, 2015 math.AG, math.GR
For every $p\geq 2$ we show that each finite $p$-group with an unmixed Beauville structure is part of a surjective infinite projective system of finite $p$-groups with compatible unmixed Beauville structures. This leads to the new notion of an unmixed topological Beauville structure on pro-finite groups. We further construct for $p \geq 5$ a new explicit infinite series of non-abelian $p$-groups that allow unmixed Beauville structures.
• ### Signatures, lifts, and eigenvalues of graphs(1412.6841)

Dec. 21, 2014 math.CO, cs.DM
We study the spectra of cyclic signatures of finite graphs and the corresponding cyclic lifts. Starting from a bipartite Ramanujan graph, we prove the existence of an infinite tower of $3$-cyclic lifts, each of which is again Ramanujan.
• ### Navigating in the Cayley graph of $SL_2(F_p)$ and applications to hashing(1409.4478)

Sept. 16, 2014 cs.CR, math.GR
Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can "backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This "lifting attack" was successfully used by Tillich and Z\'emor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(Z_+)$. However, in this paper we show that the situation with other, "similar", pairs of matrices from $SL_2(Z)$ is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by $A$ and $B$, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.
• ### Simply transitive quaternionic lattices of rank 2 over F_q(t) and a non-classical fake quadric(1304.5549)

April 19, 2013 math.AG, math.NT, math.GR
We construct an infinite series of simply transitive irreducible lattices in PGL_2(F_q((t))) \times PGL_2(F_q((t))) by means of a quaternion algebra over F_q(t). The lattices depend on an odd prime power q = p^r and a parameter \tau\ in F_q^* different from 1, and are the fundamental group of a square complex with just one vertex and universal covering T_{q+1} \times T_{q+1}, a product of trees with constant valency q + 1. Our lattices give rise via non-archimedian uniformization to smooth projective surfaces of general type over F_q((t)) with ample canonical class, Chern ratio (c_1)^2/c_2 = 2, trivial Albanese variety and non-reduced Picard scheme. For q = 3, the Zariski-Euler characteristic attains its minimal value \chi = 1: the surface is a non-classical fake quadric.
• ### An infinite family of 2-groups with mixed Beauville structures(1304.4480)

April 16, 2013 math.AG, math.GR
We construct an infinite family of triples $(G_k,H_k,T_k)$, where $G_k$ are 2-groups of increasing order, $H_k$ are index-2 subgroups of $G_k$, and $T_k$ are pairs of generators of $H_k$. We show that the triples $u_k = (G_k,H_k,T_k)$ are mixed Beauville structures if $k$ is not a power of 2. This is the first known infinite family of 2-groups admitting mixed Beauville structures. Moreover, the associated Beauville surface $S(u_3)$ is real and, for $k > 3$ not a power of 2, the Beauville surface $S(u_k)$ is not biholomorphic to $\bar{S(u_k)}$.
• ### Trivalent expanders and hyperbolic surfaces(1202.2304)

Feb. 10, 2012 math.CO
We introduce a family of trivalent expanders which tessellate compact hyperbolic surfaces with large isometry groups. We compare this family with Platonic graphs and modifications of them and prove topological and spectral properties of these families.
• ### Groups acting simply transitively on hyperbolic buildings(1107.3690)

Oct. 31, 2011 math.CO, math.GR
We construct and classify all groups, given by triangular presentations associated to the smallest thick generalized quadrangle, that act simply transitively on the vertices of hyperbolic triangular buildings of the smallest non-trivial thickness. Our classification shows 23 non-isomorphic torsion free groups (obtained in an earlier work) and 168 non-isomorphic torsion groups acting on one of two possible buildings with the smallest thick generalized quadrangle as the link of each vertex. In analogy with the Euclidean case, we find both torsion and torsion free groups acting on the same building.
• ### Expander graphs from Curtis Tits groups(1009.0667)

Oct. 28, 2011 math.CO, math.GT, math.GR
Using the construction of a nonorientable Curtis-Tits group of type $\tilde A_n$, we obtain new explicit families of expander graphs of valency five for unitary groups over finite fields.
• ### Regular algebraic surfaces isogenous to a higher product constructed from group representations using projective planes(1109.6053)

Sept. 27, 2011 math.AG, math.GR
Regular algebraic surfaces isogenous to a higher product of curves can be obtained from finite groups with ramification structures. We find unmixed ramification structures for finite groups constructed as p-quotients of particular infinite groups with special presentations related to finite projective planes.
• ### Linear estimates for solutions of quadratic equations in free groups(1107.2843)

July 14, 2011 math.GR
We prove that in a free group the length of the value of each variable in a minimal solution of a standard quadratic equation is bounded by $2s$ for orientable equation and by $12s^4$ for non-orientable equation, where $s$ is the sum of the lengths of the coefficients
• ### On the number of optimal surfaces(0904.1877)

April 12, 2009 math.GT, math.MG
Let X be a closed oriented Riemann surface of genus > 1 of constant negative curvature -1. A surface containing a disk of maximal radius is an optimal surface. This paper gives exact formulae for the number of optimal surfaces of genus > 3 up to orientation-preserving isometry. We show that the automorphism group of such a surface is always cyclic of order 1,2,3 or 6. We also describe a combinatorial structure of nonorientable hyperbolic optimal surfaces.
• ### Cayley Graph Expanders and Groups of Finite Width(0809.1560)

Sept. 9, 2008 math.GR
We present new infinite families of expander graphs of vertex degree 4, which is the minimal possible degree for Cayley graph expanders. Our first family defines a tower of coverings (with covering indices equals 2) and our second family is given as Cayley graphs of finite groups with very short presentations with only 2 generators and 4 relations. Both families are based on particular finite quotients of a group G of infinite upper triangular matrices over the ring M(3,F2). We present explicit vector space bases for the finite abelian quotients of the lower exponent-2 groups of G by upper triangular subgroups and prove a particular 3-periodicity of these quotients. The pro-2 completion of the group G satisfies the Golod-Shafarevich inequality $|R| \geq (|X|^2)/4$, it is infinite, not p-adic analytic, contains a free nonabelian subgroup, but not a free pro-p group. We also conjecture that the group G has finite width 3 and finite average width 8/3.
• ### Square free words as products of commutators(0809.1577)

Sept. 9, 2008 math.GR
Elements of the commutator subgroup of a free group can be presented as values of canonical forms, called Wicks forms. We show that, starting from sufficiently high genus g, there is a sequence of words w(g) which can be presented by f(g) distinct Wicks forms, where f(g)>g!. Moreover we may choose these words w(g) to be square free.
• ### K-theory of some C*-algebras and buildings(math/0607796)

July 31, 2006 math.OA, math.KT
We compute an exact formula for the order of the class of the identity in the K_0 group of an infinite class of two-dimensional Kuntz-Crieger algebras.
• ### Triangular hyperbolic buildings(math/0506613)

June 30, 2005 math.CO
We construct triangular hyperbolic polyhedra whose links are generalized 4-gons. The universal cover of those polyhedra are hyperbolic buildings, which appartments are hyperbolic planes tesselated by regular triangles with angles $\pi/4$. Moreover, the fundamental groups of the polyhedra acts simply transitively on vertices of the buildings.
• ### $C^*$-algebras coming from some buildings(math/0406162)

June 9, 2004 math.CO
We construct compact polyhedra with triangular faces whose links are generalized 3-gons. They are interesting compact spaces covered by Euclidean buildings of type $A_2$. Those spaces give us two-dimensional subshifts, which can be used to construct some $C^*$-algebras.
• ### On the number of extremal surfaces(math/0311533)

Nov. 28, 2003 math.DG
Let $X$ be a compact Riemann surface of genus $\geq 2$ of constant negative curvature -1. An extremal disk is an embedded (resp. covering) disk of maximal (resp. minimal) radius. A surface containing an extremal disk is an {\em extremal surface}. This paper gives formulas enumerating extremal surfaces of genus $\geq 4$ up to isometry. We show also that the isometry group of an extremal surface is always cyclic of order 1, 2, 3 or 6.
• ### Groups, periodic planes and hyperbolic buildings(math/0307380)

July 30, 2003 math.CO, math.GR
We give an elementary construction of polyhedra whose links are connected bipartite graphs, which are not necessarily isomorphic pairwise. We show, that the fundamental groups of some of our polyhedra contain surface groups. In particular, we construct polyhedra whose links are generalized $m$-gons. The polyhedra of this type are interesting because of their universal coverings, which are two-dimensional hyperbolic buildings with different links. The presentation of the results is done in the language of combinatorial group theory.
• ### Polyhedra with specified links(math/0302298)

Feb. 25, 2003 math.CO
We construct compact polyhedra with $m$-gonal faces whose links are generalized 3-gons. It gives examples of cocompact hyperbolic bildings of type $P(m,3)$. For $m=3$ we get compact spaces covered by Euclidean buildings of type $A_2$.
• ### Counting 1-vertex Triangulations Of Oriented Surfaces(math/0110025)

Oct. 2, 2001 math.CO, math.GR
A {\em $1-$vertex triangulation} of an oriented compact surface $S$ of genus $g$ is an embedded graph $T\subset S$ with a unique vertex such that all connected components of $S\setminus T$ are triangles (adjacent to exactly 3 edges of $T$). This paper gives formulas enumerating such triangulations (up to equivalence) on an oriented surface of given genus. {\em Une triangulation \a un sommet} d'une surface orient\'ee compacte $S$ de genre $g$ est un graphe $T\subset S$ qui a un unique sommet et dont toutes les faces (composantes connexes de $S\setminus T$) sont des triangles (incidentes \a trois ar\^etes de $T$). Cet article donne des formules permettant d'\'enum\'erer ces triangulations.