More Like this

1. Coprime automorphisms of finite groups

   https://doi.org/10.1090/tran/8553  

   Acciarri, Cristina; Guralnick, Robert; Shumyatsky, Pavel (July 2022, Transactions of the American Mathematical Society)

   Let G G be a finite group admitting a coprime automorphism α \alpha of order e e . Denote by I G ( α ) I_G(\alpha ) the set of commutators g − 1 g α g^{-1}g^\alpha , where g ∈ G g\in G , and by [ G , α ] [G,\alpha ] the subgroup generated by I G ( α ) I_G(\alpha ) . We study the impact of I G ( α ) I_G(\alpha ) on the structure of [ G , α ] [G,\alpha ] . Suppose that each subgroup generated by a subset of I G ( α ) I_G(\alpha ) can be generated by at most r r elements. We show that the rank of [ G , α ] [G,\alpha ] is ( e , r ) (e,r) -bounded. Along the way, we establish several results of independent interest. In particular, we prove that if every element of I G ( α ) I_G(\alpha ) has odd order, then [ G , α ] [G,\alpha ] has odd order too. Further, if every pair of elements from I G ( α ) I_G(\alpha ) generates a soluble, or nilpotent, subgroup, then [ G , α ] [G,\alpha ] is soluble, or respectively nilpotent. 

   more » « less
2. $$K_{r,s}$$ Graph Bootstrap Percolation

   https://doi.org/10.37236/8997  

   Bayraktar, Erhan; Chakraborty, Suman (January 2022, The Electronic Journal of Combinatorics)

   A graph $$G$$ percolates in the $$K_{r,s}$$-bootstrap process if we can add all missing edges of $$G$$ in some order such that each edge creates a new copy of $$K_{r,s}$$, where $$K_{r,s}$$ is the complete bipartite graph. We study $$K_{r,s}$$-bootstrap percolation on the Erdős-Rényi random graph, and determine the percolation threshold for balanced $$K_{r,s}$$ up to a logarithmic factor. This partially answers a question raised by Balogh, Bollobás, and Morris. We also establish a general lower bound of the percolation threshold for all $$K_{r,s}$$, with $$r\geq s \geq 3$$. 

   more » « less
3. Local Correlation Clustering with Asymmetric Classification Errors

   Jafarov, Jafar; Kalhan, Sanchit; Makarychev, Konstantin; Makarychev, Yury (January 2021, Proceedings of Machine Learning Research)

   Meila, Marina; Zhang, Tong (Ed.)

   In the Correlation Clustering problem, we are given a complete weighted graph $$G$$ with its edges labeled as “similar" and “dissimilar" by a noisy binary classifier. For a clustering $$\mathcal{C}$$ of graph $$G$$, a similar edge is in disagreement with $$\mathcal{C}$$, if its endpoints belong to distinct clusters; and a dissimilar edge is in disagreement with $$\mathcal{C}$$ if its endpoints belong to the same cluster. The disagreements vector, $$\mathbf{disagree}$$, is a vector indexed by the vertices of $$G$$ such that the $$v$$-th coordinate $$\mathbf{disagree}_v$$ equals the weight of all disagreeing edges incident on $$v$$. The goal is to produce a clustering that minimizes the $$\ell_p$$ norm of the disagreements vector for $$p\geq 1$$. We study the $$\ell_p$$ objective in Correlation Clustering under the following assumption: Every similar edge has weight in $$[\alpha\mathbf{w},\mathbf{w}]$$ and every dissimilar edge has weight at least $$\alpha\mathbf{w}$$ (where $$\alpha \leq 1$$ and $$\mathbf{w}>0$$ is a scaling parameter). We give an $$O\left((\frac{1}{\alpha})^{\frac{1}{2}-\frac{1}{2p}}\cdot \log\frac{1}{\alpha}\right)$$ approximation algorithm for this problem. Furthermore, we show an almost matching convex programming integrality gap. 

   more » « less
4. Discorrelation Between Primes in Short Intervals and Polynomial Phases

   https://doi.org/10.1093/imrn/rnz188  

   Matomäki, Kaisa; Shao, Xuancheng (September 2019, International Mathematics Research Notices)

   Abstract Let $$H = N^{\theta }, \theta> 2/3$$ and $$k \geq 1$$. We obtain estimates for the following exponential sum over primes in short intervals: \begin{equation*} \sum_{N < n \leq N+H} \Lambda(n) \mathrm e(g(n)), \end{equation*}where $$g$$ is a polynomial of degree $$k$$. As a consequence of this in the special case $$g(n) = \alpha n^k$$, we deduce a short interval version of the Waring–Goldbach problem. 

   more » « less
5. COUNTING CONJUGACY CLASSES IN

   https://doi.org/10.1017/S0004972718000047  

   HULL, MICHAEL; KAPOVICH, ILYA (June 2018, Bulletin of the Australian Mathematical Society)

   We show that if a finitely generated group $$G$$ has a nonelementary WPD action on a hyperbolic metric space $$X$$ , then the number of $$G$$ -conjugacy classes of $$X$$ -loxodromic elements of $$G$$ coming from a ball of radius $$R$$ in the Cayley graph of $$G$$ grows exponentially in $$R$$ . As an application we prove that for $$N\geq 3$$ the number of distinct $$\text{Out}(F_{N})$$ -conjugacy classes of fully irreducible elements $$\unicode[STIX]{x1D719}$$ from an $$R$$ -ball in the Cayley graph of $$\text{Out}(F_{N})$$ with $$\log \unicode[STIX]{x1D706}(\unicode[STIX]{x1D719})$$ of the order of $$R$$ grows exponentially in $$R$$ . 

   more » « less