On permutation patterns, pinnacle sets, and backbones of bipartite projections

This dissertation encompasses the study of two different fields, one regarding permutations including pattern containment and pinnacle sets, and the other on weighted networks, specifically bipartite projections and their backbones.The study of pattern containment and avoidance for linear permutations is a well-established area of enumerative combinatorics. A cyclic permutation is the set of all rotations of a linear permutation. Callan initiated the study of permutation avoidance in cyclic permutations and characterized the avoidance classes for all single permutations of length 4. We continue this work. In particular, we establish a cyclic variant of the Erdos-Szekeres Theorem that any linear permutation of length mn + 1 must contain either the increasing pattern of length m + 1 or the decreasing pattern of length n + 1. We then derive results about avoidance of multiple patterns of length 4. We also determine generating functions for the cyclic descent statistic on these classes.We then study the pinnacle set, which is the value analogue of a well-studied permutation statistic, the peak set. Let Ï⁰ = Ï⁰1 Ï⁰2 ... Ï⁰n be a permutation in the symmetric group Sn written in one-line notation. The pinnacle set of Ï⁰ denoted Pin Ï⁰ is the set of all Ï⁰i such that piÏ⁰i-1piÏ⁰i+1. The classic peak set statistic consists of the positions of these values. The pinnacle set was introduced by Davis, Nelson, Petersen, and Tenner who showed that it has many interesting properties. In particular, they proved that the number of subsets of [n] = {1,2,...,n} which can be the pinnacle set of some permutation is a binomial coefficient. Their proof involved a bijection with lattice paths and was somewhat involved. We give a simpler demonstration of this result which does not need lattice paths. Moreover, we show that our map and theirs are different descriptions of the same function. Davis et al. also studied the number of pinnacle sets with maximum m and cardinality d which they denoted by p(m,d ). We show that these integers are the well-known ballot numbers and give two proofs of this fact: one using finite differences and one bijective. Diaz-Lopez, Harris, Huang, Insko, and Nilsen found a summation formula for calculating the number of permutations in Sn having a given pinnacle set. We derive a new expression for this number which is faster to calculate in many cases. We also show how this method can be adapted to find the number of orderings of a pinnacle set which can be realized by some Ï⁰ in Sn. This concludes our research on permutations.Bipartite projections are used in a wide range of network contexts including politics (bill co-sponsorship), geography (firm co-location), genetics (gene co-expression), economics (executive board co-membership), and innovation (patent co-authorship). However, because bipartite projections are always weighted graphs, which are inherently challenging to analyze and visualize, it is often useful to examine the 'backbone,' an unweighted subgraph containing only the most significant edges. We introduce the R package backbone for extracting the backbone of weighted bipartite projections, and use two empirical datasets to demonstrate its functionality, bill sponsorship data from the 114th session of the United States Senate and a Globalization and World Cities data set regarding firm locations in 2000.After introducing and demonstrating five different models for backbone extraction, the fixed fill model (FFM), fixed row model (FRM), fixed column model (FCM), fixed degree sequence model (FDSM), and stochastic degree sequence model (SDSM), we compare them in terms of accuracy, speed, statistical power, similarity, and community detection. Here, we aim to find which models perform similarly to FDSM, since the FDSM model controls for both degree sequences exactly. We find that the computationally-fast SDSM offers a statistically conservative but close approximation of the computationally-impractical FDSM under a wide range of conditions, and that it correctly recovers a known community structure even when the signal is weak. Therefore, although each backbone model may have particular applications, we recommend SDSM for extracting the backbone of most bipartite projections.