skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.

Title: Pattern-Functions, Statistics, and Shallow Permutations
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
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Background

    Vestibular deficits can impair an individual’s ability to maintain postural and/or gaze stability. Characterizing gait abnormalities among individuals affected by vestibular deficits could help identify patients at high risk of falling and inform rehabilitation programs. Commonly used gait assessment tools rely on simple measures such as timing and visual observations of path deviations by clinicians. These simple measures may not capture subtle changes in gait kinematics. Therefore, we investigated the use of wearable inertial measurement units (IMUs) and machine learning (ML) approaches to automatically discriminate between gait patterns of individuals with vestibular deficits and age-matched controls. The goal of this study was to examine the effects of IMU placement and gait task selection on the performance of automatic vestibular gait classifiers.


    Thirty study participants (15 with vestibular deficits and 15 age-matched controls) participated in a single-session gait study during which they performed seven gait tasks while donning a full-body set of IMUs. Classification performance was reported in terms of area under the receiver operating characteristic curve (AUROC) scores for Random Forest models trained on data from each IMU placement for each gait task.


    Several models were able to classify vestibular gait better than random (AUROC > 0.5), but their performance varied according to IMU placement and gait task selection. Results indicated that a single IMU placed on the left arm when walking with eyes closed resulted in the highest AUROC score for a single IMU (AUROC = 0.88 [0.84, 0.89]). Feature permutation results indicated that participants with vestibular deficits reduced their arm swing compared to age-matched controls while they walked with eyes closed.


    These findings highlighted differences in upper extremity kinematics during walking with eyes closed that were characteristic of vestibular deficits and showed evidence of the discriminative ability of IMU-based automated screening for vestibular deficits. Further research should explore the mechanisms driving arm swing differences in the vestibular population.

    more » « less
  2. Aims. Various nucleosynthesis studies have pointed out that the r -process elements in very metal-poor (VMP) halo stars might have different origins. By means of familiar concepts from statistics (correlations, cluster analysis, and rank tests of elemental abundances), we look for causally correlated elemental abundance patterns and attempt to link them to astrophysical events. Some of these events produce the r -process elements jointly with iron, while others do not have any significant iron contribution. We try to (a) characterize these different types of events by their abundance patterns and (b) identify them among the existing set of suggested r -process sites. Methods. The Pearson and Spearman correlation coefficients were used in order to investigate correlations among r -process elements (X,Y) as well as their relation to iron (Fe) in VMP halo stars. We gradually tracked the evolution of those coefficients in terms of the element enrichments [X/Fe] or [X/Y] and the metallicity [Fe/H]. This approach, aided by cluster analysis to find different structures of abundance patterns and rank tests to identify whether several events contributed to the observed pattern, is new and provides deeper insights into the abundances of VMP stars. Results. In the early stage of our Galaxy, at least three r -process nucleosynthesis sites have been active. The first two produce and eject iron and the majority of the lighter r -process elements. We assign them to two different types of core-collapse events, not identical to regular core-collapse supernovae (CCSNe), which produce only light trans-Fe elements. The third category is characterized by a strong r -process and is responsible for the major fraction of the heavy main r -process elements without a significant coproduction of Fe. It does not appear to be connected to CCSNe, in fact most of the Fe found in the related r -process enriched stars must come from previously occurring CCSNe. The existence of actinide boost stars indicates a further division among strong r -process sites. We assign these two strong r -process sites to neutron star mergers without fast black hole formation and to events where the ejecta are dominated by black hole accretion disk outflows. Indications from the lowest-metallicity stars hint at a connection with massive single stars (collapsars) forming black holes in the early Galaxy. 
    more » « less
  3. Aboelhadid, Shawky M (Ed.)
    The COVID-19 pandemic has caused over 500 million cases and over six million deaths globally. From these numbers, over 12 million cases and over 250 thousand deaths have occurred on the African continent as of May 2022. Prevention and surveillance remains the cornerstone of interventions to halt the further spread of COVID-19. Google Health Trends (GHT), a free Internet tool, may be valuable to help anticipate outbreaks, identify disease hotspots, or understand the patterns of disease surveillance. We collected COVID-19 case and death incidence for 54 African countries and obtained averages for four, five-month study periods in 2020–2021. Average case and death incidences were calculated during these four time periods to measure disease severity. We used GHT to characterize COVID-19 incidence across Africa, collecting numbers of searches from GHT related to COVID-19 using four terms: ‘coronavirus’, ‘coronavirus symptoms’, ‘COVID19’, and ‘pandemic’. The terms were related to weekly COVID-19 case incidences for the entire study period via multiple linear and weighted linear regression analyses. We also assembled 72 variables assessing Internet accessibility, demographics, economics, health, and others, for each country, to summarize potential mechanisms linking GHT searches and COVID-19 incidence. COVID-19 burden in Africa increased steadily during the study period. Important increases for COVID-19 death incidence were observed for Seychelles and Tunisia. Our study demonstrated a weak correlation between GHT and COVID-19 incidence for most African countries. Several variables seemed useful in explaining the pattern of GHT statistics and their relationship to COVID-19 including: log of average weekly cases, log of cumulative total deaths, and log of fixed total number of broadband subscriptions in a country. Apparently, GHT may best be used for surveillance of diseases that are diagnosed more consistently. Overall, GHT-based surveillance showed little applicability in the studied countries. GHT for an ongoing epidemic might be useful in specific situations, such as when countries have significant levels of infection with low variability. Future studies might assess the algorithm in different epidemic contexts. 
    more » « less
  4. Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)
    We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unbounded-width unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [Lee-Pyne-Vadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [Hoza-Pyne-Vadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unbounded-width unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no non-trivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [Bogdanov-Hoza-Prakriya-Pyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a non-trivial seed length is known for this class. We remark that there are some functions computable by constant-width adaptive branching programs but not by sub-exponential-width unordered branching programs. In terms of techniques, we indeed show that the Forbes-Kelley PRG (with the right parameters) from [Forbes-Kelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of Forbes-Kelly, and we believe it further demonstrates the versatility of the Forbes-Kelley PRG. 
    more » « less
  5. Abstract

    It is important to understand how point measurements across spatially heterogeneous ecosystems are scaled to represent these systems. Stream biogeochemistry presents an illustrative example because water quality concerns within stream networks and recipient water bodies motivate heterogeneous watershed studies. Measurements of the stream water‐groundwater (SW‐GW) interface (i.e., the shallow stream subsurface) are well‐documented for point‐scale sampling density measurements (i.e., cm2–m2features), but poorly characterized for network‐scale sampling density measurements (i.e., km2; stream reaches and networks). Sampling the SW‐GW interface is more time and labor intensive than surface water sampling, meaning sample point selection must be made with care for network‐scale analyses. In this study, we endeavor to determine which of two common spatial sampling schemes is appropriate for characterizing SW‐GW interface biogeochemistry across a third‐order stream network, focusing on dissolved organic carbon. The first scheme, called Local Sampling, focuses on characterizing small‐scale (< 10 m2) variability produced by the local physical and biogeochemical heterogeneity, with fewer points across the stream network. The second scheme, called Longitudinal Sampling, has approximately the same number of measurements distributed over many more points across the stream network with less local variability characterization. This comparison reveals that selection of a Local Sampling versus a Longitudinal Sampling scheme influences the biogeochemical pattern interpretation at the stream network scale. Additionally, this study found that increasing observation efforts at the local scale added limited information for reach‐ to network‐scale biogeochemical patterns, suggesting that emphasis should be placed on characterizing variability across broader spatial scales with the Longitudinal Sampling approach.

    more » « less