More Like this

1. Pattern-Functions, Statistics, and Shallow Permutations

   https://doi.org/10.37236/10858  

   Berman, Yosef; Tenner, Bridget Eileen (October 2022, The Electronic Journal of Combinatorics)

   We study relationships between permutation statistics and pattern-functions, counting the number of times particular patterns occur in a permutation. This allows us to write several familiar statistics as linear combinations of pattern counts, both in terms of a permutation and in terms of its image under the fundamental bijection. We use these enumerations to resolve the question of characterizing so-called "shallow" permutations, whose depth (equivalently, disarray/displacement) is minimal with respect to length and reflection length. We present this characterization in several ways, including vincular patterns, mesh patterns, and a new object that we call "arrow patterns." Furthermore, we specialize to characterizing and enumerating shallow involutions and shallow cycles, encountering the Motzkin and large Schröder numbers, respectively. 

   more » « less
2. Measuring the functional complexity of nanoscale connectomes: polarity matters

   https://doi.org/10.1101/2024.09.24.614724  

   Wang, Qingyang; Randel, Nadine; Yin, Yijie; Shand, Cameron; Strange, Amy; Winding, Michael; Cardona, Albert; Zlatic, Marta; Vogelstein, Joshua T; Priebe, Carey E (September 2024, bioRxiv)

   The emerging electron microscopy connectome datasets provides connectivity maps of the brains at single cell resolution, enabling us to estimate various network statistics, such as connectedness. We desire the ability to assess how the functional complexity of these networks depends on these network statistics. To this end, we developed an analysis pipeline and a statistic, XORness, which quantifies the functional complexity of these networks with varying network statistics. We illustrate that actual connectomes have high XORness, as do generated connectomes with the same network statistics, suggesting a normative role for functional complexity in guiding the evolution of connectomes, and providing clues to guide the development of artificial neural networks. 

   more » « less
3. Cyclic Shuffle-Compatibility Via Cyclic Shuffle Algebras

   https://doi.org/10.1007/s00026-023-00669-9  

   Liang, Jinting; Sagan, Bruce_E; Zhuang, Yan (October 2023, Annals of Combinatorics)

   Abstract A permutation statistic$${{\,\textrm{st}\,}}$$ $\text{st}$is said to be shuffle-compatible if the distribution of$${{\,\textrm{st}\,}}$$ $\text{st}$over the set of shuffles of two disjoint permutations$$\pi $$ $\pi$and$$\sigma $$ $\sigma$depends only on$${{\,\textrm{st}\,}}\pi $$ $\text{st}\pi$,$${{\,\textrm{st}\,}}\sigma $$ $\text{st}\sigma$, and the lengths of$$\pi $$ $\pi$and$$\sigma $$ $\sigma$. Shuffle-compatibility is implicit in Stanley’s early work onP-partitions, and was first explicitly studied by Gessel and Zhuang, who developed an algebraic framework for shuffle-compatibility centered around their notion of the shuffle algebra of a shuffle-compatible statistic. For a family of statistics called descent statistics, these shuffle algebras are isomorphic to quotients of the algebra of quasisymmetric functions. Recently, Domagalski, Liang, Minnich, Sagan, Schmidt, and Sietsema defined a version of shuffle-compatibility for statistics on cyclic permutations, and studied cyclic shuffle-compatibility through purely combinatorial means. In this paper, we define the cyclic shuffle algebra of a cyclic shuffle-compatible statistic, and develop an algebraic framework for cyclic shuffle-compatibility in which the role of quasisymmetric functions is replaced by the cyclic quasisymmetric functions recently introduced by Adin, Gessel, Reiner, and Roichman. We use our theory to provide explicit descriptions for the cyclic shuffle algebras of various cyclic permutation statistics, which in turn gives algebraic proofs for their cyclic shuffle-compatibility. 

   more » « less
4. Statistical evidence for the presence of trajectory in single-cell data

   https://doi.org/10.1186/s12859-022-04875-9  

   Tenha, Lovemore; Song, Mingzhou (August 2022, BMC Bioinformatics)

   Abstract BackgroundCells progressing from an early state to a developed state give rise to lineages in cell differentiation. Knowledge of these lineages is central to developmental biology. Each biological lineage corresponds to a trajectory in a dynamical system. Emerging single-cell technologies such as single-cell RNA sequencing can capture molecular abundance in diverse cell types in a developing tissue. Many computational methods have been developed to infer trajectories from single-cell data. However, to our knowledge, none of the existing methods address the problem of determining the existence of a trajectory in observed data before attempting trajectory inference. ResultsWe introduce a method to identify the existence of a trajectory using three graph-based statistics. A permutation test is utilized to calculate the empirical distribution of the test statistic under the null hypothesis that a trajectory does not exist. Finally, ap-value is calculated to quantify the statistical significance for the presence of trajectory in the data. ConclusionsOur work contributes new statistics to assess the level of uncertainty in trajectory inference to increase the understanding of biological system dynamics. 

   more » « less
5. On Differentially Private U Statistics

   Chaudhuri, Kamalika; Loh, Po-Ling; Pandey, Shourya; Sarkar, Purnamrita (July 2024, https://doi.org/10.48550/arXiv.2407.04945)

   We consider the problem of privately estimating a parameter 𝔼[h(X1,…,Xk)], where X1, X2, …, Xk are i.i.d. data from some distribution and h is a permutation-invariant function. Without privacy constraints, standard estimators are U-statistics, which commonly arise in a wide range of problems, including nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and can be shown to be minimum variance unbiased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied to obtain confidence intervals, we show that they can lead to suboptimal private error, e.g., constant-factor inflation in the leading term, or even Θ(1/n) rather than O(1/n²) in degenerate settings. To remedy this, we propose a new thresholding-based approach using local Hájek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics. 

   more » « less