skip to main content

Title: Cycle type of random permutations: a toolkit
We prove a number of results, new and old, about the cycle type of a random permutation on S_n. Underlying our analysis is the idea that the number of cycles of size k is roughly Poisson distributed with parameter 1/k. In particular, we establish strong results about the distribution of the number of cycles whose lengths lie in a fixed but arbitrary set I. Our techniques are motivated by the theory of sieves in number theory.  more » « less
Award ID(s):
Author(s) / Creator(s):
Gowers, W. T.
Date Published:
Journal Name:
Discrete analysis
Page Range / eLocation ID:
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1-\eps)$-approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$-approximation for densest-at-least-$k$ subgraph \cite{ks-09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave function $g$. 
    more » « less
  2. Elementary school is the first opportunity most students have to learn about STEM; however, elementary teachers are sometimes the least confident and prepared to teach STEM concepts and practices. Research Experience for Teachers (RET) programs are an established form of K-12 teacher professional development in which teachers are invited to work as members of a laboratory research team to increase their enthusiasm, knowledge and experience in STEM fields. The Engineering for Biology: Multidisciplinary Research Experiences for Teachers (MRET) of Elementary Grades was a 7-week summer program in which teachers were embedded as contributing members of engineering laboratory research teams and was established with the goals of (1) increasing teacher knowledge of STEM concepts and practices, (2) fostering mentoring relationships among researchers and teachers in each laboratory, and (3) guiding the translation of the teachers’ laboratory experience into the classroom through the development of STEM learning units. This exploratory study focuses on the second goal, and involves the use of developmental network theory to discriminate mentoring among participants within the summer 2017 and 2018 cycles of MRET. Using data collected in daily observations as well as daily activity and conversation logs submitted by all participants during the lab experience, post participation surveys, and post program semi structured interviews, we have characterized a network of mentoring that existed within the lab portion of MRET as being multidirectional and potentially beneficial to all members, including researchers as well as teachers. This finding challenges the currently accepted assumption that teachers are the primary beneficiaries of mentoring within RET programs. If demonstrated to be appropriate and transferrable to the RET context, such a perspective could enhance our understanding of the experience and be used for maximizing the outcomes for all participants. 
    more » « less
  3. null (Ed.)
    Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $G$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $k$; in addition, if $G$ is $2$-connected and non-bipartite, then it contains cycles of all lengths modulo $k$. 2. For all $k\geq 3$, every $k$-connected graph contains a cycle of length zero modulo $k$. 3. Every $3$-connected non-bipartite graph with minimum degree at least $k+1$ contains $k$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $k$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible. 
    more » « less
  4. Measurements of turbulence, as rate of dissipation of turbulent kinetic energy (ε), adjacent to the air-water interface are rare but essential for understanding of gas transfer velocities (k) used to compute fluxes of greenhouse gases. Variability in ε is expected over diel cycles of stratification and mixing. Monin-Obukhov similarity theory (MOST) predicts an enhancement in ε during heating (buoyancy flux, β+) relative to that for shear (u*w 3/κz where u*w is water friction velocity, κ is von Karman constant, z is depth). To verify and expand predictions, we quantified ε in the upper 0.25 m and below from profiles of temperature-gradient microstructure in combination with time series meteorology and temperature in a tropical reservoir for winds <4 m s−1. Maximum likelihood estimates of near-surface ε during heating were independent of wind speed and high, ∼5 × 10−6 m2 s−3, up to three orders of magnitude higher than predictions from u*w 3/κz, increased with heating, and were ∼10 times higher than during cooling. k, estimated using near-surface ε, was ∼10 cm hr−1, validated with k obtained from chamber measurements, and 2–5 times higher than computed from wind-based models. The flux Richardson number (Rf) varied from ∼0.4 to ∼0.001 with a median value of 0.04 in the upper 0.25 m, less than the critical value of 0.2. We extend MOST by incorporating the variability in Rf when scaling the influence of β+ relative to u*w 3/κz in estimates of ε, and by extension, k, obtained from time series meteorological and temperature data. 
    more » « less
  5. Abstract

    Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginalskand their support sizesn. This paper develops a general theory about what “structure” makes MOT solvable in$$\mathrm {poly}(n,k)$$poly(n,k)time. We develop a unified algorithmic framework for solving MOT in$$\mathrm {poly}(n,k)$$poly(n,k)time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in$$\mathrm {poly}(n,k)$$poly(n,k)time. Second, our framework makes it much simpler to develop$$\mathrm {poly}(n,k)$$poly(n,k)time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle—which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing$$\mathrm {poly}(n,k)$$poly(n,k)-time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has$$\mathrm {poly}(n,k)$$poly(n,k)runtime; moreover, we provide the first$$\mathrm {poly}(n,k)$$poly(n,k)time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first$$\mathrm {poly}(n,k)$$poly(n,k)time algorithms, even for approximate computation. Together, these three structures encompass many—if not most—current applications of MOT.

    more » « less