Outputs (3)

On the local geometry of graphs in terms of their spectra (2019)
Journal Article
Huang, B., & Rahman, M. (2019). On the local geometry of graphs in terms of their spectra. European Journal of Combinatorics, 81, 378-393. https://doi.org/10.1016/j.ejc.2019.07.001

In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose G1,G2,G3,... is a sequence of finite and connected graphs that share a common universal cover T and such that the proportion of eigenv... Read More about On the local geometry of graphs in terms of their spectra.

Geometry of Permutation Limits (2019)
Journal Article
Rahman, M., Virág, B., & Vizer, M. (2019). Geometry of Permutation Limits. Combinatorica, 39, 933-960. https://doi.org/10.1007/s00493-019-3817-6

This paper initiates a limit theory of permutation valued processes, building on the recent theory of permutons. We apply this to study the asymptotic behaviour of random sorting networks. We prove that the Archimedean path, the conjectured limit of... Read More about Geometry of Permutation Limits.

Suboptimality of local algorithms for a class of max-cut problems (2019)
Journal Article
Chen, W., Gamarnik, D., Panchenko, D., & Rahman, M. (2019). Suboptimality of local algorithms for a class of max-cut problems. Annals of Probability, 47(3), 1587-1618. https://doi.org/10.1214/18-aop1291

We show that in random K -uniform hypergraphs of constant average degree, for even K ≥ 4 , local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used... Read More about Suboptimality of local algorithms for a class of max-cut problems.