Source author record

Samantha Petti

Samantha Petti appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.GT Data Structures and Algorithms math.AT Neural and Evolutionary Computing Populations and Evolution

Catalog footprint

What is connected

5works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Approximating Sparse Graphs: The Random Overlapping Communities Model

How can we approximate sparse graphs and sequences of sparse graphs (with unbounded average degree)? We consider convergence in the first $k$ moments of the graph spectrum (equivalent to the numbers of closed $k$-walks) appropriately normalized. We introduce a simple, easy to sample, random graph model that captures the limiting spectra of many sequences of interest, including the sequence of hypercube graphs. The Random Overlapping Communities (ROC) model is specified by a distribution on pairs $(s,q)$, $s \in \mathbb{Z}_+, q \in (0,1]$. A graph on $n$ vertices with average degree $d$ is generated by repeatedly picking pairs $(s,q)$ from the distribution, adding an Erdős-Rényi random graph of edge density $q$ on a subset of vertices chosen by including each vertex with probability $s/n$, and repeating this process so that the expected degree is $d$. Our proof of convergence to a ROC random graph is based on the Stieltjes moment condition. We also show that the model is an effective approximation for individual graphs. For almost all possible triangle-to-edge and four-cycle-to-edge ratios, there exists a pair $(s,q)$ such that the ROC model with this single community type produces graphs with both desired ratios, a property that cannot be achieved by stochastic block models of bounded description size. Moreover, ROC graphs exhibit an inverse relationship between degree and clustering coefficient, a characteristic of many real-world networks.

preprint2016arXiv

A Space of Phylogenetic Networks

A classic problem in computational biology is constructing a phylogenetic tree given a set of distances between n species. In most cases, a tree structure is too constraining. We consider a circular split network, a generalization of a tree in which multiple parallel edges signify divergence. A geometric space of such networks is introduced, forming a natural extension of the work by Billera, Holmes, and Vogtmann on tree space. We explore properties of this space, and show a natural embedding of the compactification of the real moduli space of curves within it.

preprint2016arXiv

Cortical Computation via Iterative Constructions

We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type of construction needs little global coordination or control and thus is a candidate for neurally feasible computation. Valiant's construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process and the learnability of the functions realized. We show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is a well-known cognitive finding.

preprint2014arXiv

Multi-crossing Number for Knots and the Kauffman Bracket Polynomial

A multi-crossing (or n-crossing) is a singular point in a projection at which n strands cross so that each strand bisects the crossing. We generalize the classic result of Kauffman, Murasugi, and Thistlethwaite, which gives the upper bound on the span of the bracket polynomial of K as 4c_2(K), to the n-crossing number: span<K> is bounded above by ([n^2/2] + 4n-8) c_n(K) for all integers n at least 3. We also explore n-crossing additivity under composition, and find that for n at least 4, there are examples of knots such that the n-crossing number is sub-additive. Further, we present the first extensive list of calculations of n-crossing numbers for knots. Finally, we explore the monotonicity of the sequence of n-crossings of a knot, which we call the crossing spectrum.

preprint2013arXiv

Bounds on Übercrossing and Petal Numbers for Knots

An $n$-crossing is a point in the projection of a knot where $n$ strands cross so that each strand bisects the crossing. An übercrossing projection has a single $n$-crossing and a petal projection has a single $n$-crossing such that there are no loops nested within others. The übercrossing number, $\text{ü}(K)$, is the smallest $n$ for which we can represent a knot $K$ with a single $n$-crossing. The petal number is the number of loops in the minimal petal projection. In this paper, we relate the übercrossing number and petal number to well-known invariants such as crossing number, bridge number, and unknotting number. We find that the bounds we have constructed are tight for $(r, r+1)$-torus knots. We also explore the behavior of übercrossing number under composition.