Discrete Mathematics and Combinatorics Commons^™

Simplicial Decomposition And Realization, Matthew Ellison

Dartmouth College Ph.D Dissertations

In simplicial decomposition, we define two invariants --- V_Z and V_Q --- which represent notions of integral and rational volume of a certain class of simplicial complexes. We prove V_Z and V_Q are additive under disjoint union and connected sum, and investigate `integrality gaps' between the two quantities. We apply the theory to establish a conjecture of Sleator, Thurston, and Tarjan on tetrahedral fillings, and, as a corollary, obtain a new proof of Pournin's 2012 result on the diameter of the associahedron. In simplicial realization, we provide practical sufficient conditions and computer code to prove the existence of Euclidean embeddings …

Penney’S Game For Permutations, Yixin Lin

Dartmouth College Ph.D Dissertations

We explore the permutation analog of Penney's game for coin flips. Two players, in order, each choose a permutation of length $k\ge3$. Then a sequence of independent random values from a continuous distribution is generated until the relative order of the last $k$ numbers matches one of the chosen permutations, declaring the player who selected that permutation as the winner.

We calculate the winning probabilities for all pairs of permutations of length $3$ and some pairs of length $4$, demonstrating the non-transitive property of this game, consistent with the original word version. Alternatively, we provide formulas for computing the winning …

On Pattern Avoidance And Dynamical Algebraic Combinatorics, Benjamin Adenbaum

Dartmouth College Ph.D Dissertations

Over the past decade since the term `dynamical algebraic combinatorics' was coined there has been a tremendous amount of activity in the field. Adding to that growing body of work this thesis hopes to be a step towards a broader study of pattern avoidance within dynamical algebraic combinatorics and helps initiate that by considering an action of rowmotion on 321-avoiding permutations. Additionally within we show the first known instance of piecewise-linear rowmotion periodicity for an infinite family of posets that does not follow from a more general birational result. Finally we show that the code of permutation restricted to permutations …

On Generating Bijections For Permutations And Inversion Sequences, Melanie J. Ferreri

Dartmouth College Ph.D Dissertations

Given an algebraic proof of a combinatorial identity, we use recursive methods to construct a bijection demonstrating the identity.

Our first application centers around derangements and nonderangements. A derangement is a permutation with no fixed point, and a nonderangement is a permutation with at least one fixed point. There is a one-term recurrence for the number of derangements of n elements, and we describe a bijective proof of this recurrence which can be found using a recursive map. We then show the combinatorial interpretation of this bijection and how it compares with other known bijections, and show how this extends …

The Multiset Partition Algebra: Diagram-Like Bases And Representations, Alexander N. Wilson

Dartmouth College Ph.D Dissertations

There is a classical connection between the representation theory of the symmetric group and the general linear group called Schur--Weyl Duality. Variations on this principle yield analogous connections between the symmetric group and other objects such as the partition algebra and more recently the multiset partition algebra. The partition algebra has a well-known basis indexed by graph-theoretic diagrams which allows the multiplication in the algebra to be understood visually as combinations of these diagrams. My thesis begins with a construction of an analogous basis for the multiset partition algebra. It continues with applications of this basis to constructing the irreducible …

Fixed Points And Excedances In Restricted Permutations, Sergi Elizalde

Dartmouth Scholarship

Using an unprecedented technique involving diagonals of non-rational generating functions, we prove that among the permutations of length $n$ with $i$ fixed points and $j$ excedances, the number of 321-avoiding ones equals the number of 132-avoiding ones, for any given $i,j$. Our theorem generalizes a result of Robertson, Saracino and Zeilberger. Even though bijective proofs have later been found by the author jointly with Pak and with Deutsch, this paper contains the original analytic proof that was presented at FPSAC 2003.

Building Graphs From Colored Trees, Rachel M. Esselstein, Peter Winkler

Dartmouth Scholarship

We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely, fix a radius $\rho$ and let $N(G)$ be the set of isomorphism classes of $\rho$-neighborhoods of vertices of $G$ where $G$ is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the "center" of the graph. Given a set S of colored graphs with a unique root, when is there a graph G with N (G) = S? Or N (G) ⊂ …

Counting 1324, 4231-Avoiding Permutations, Michael H. Albert, M. D. Atkinson, Vincent Vatter

Dartmouth Scholarship

A complete structural description and enumeration is found for permutations that avoid both 1324 and 4231.

A Sharp Bound For The Reconstruction Of Partitions, Vincent Vatter

Dartmouth Scholarship

Answer in g a question of Cameron, Pretzel and Siemons proved that every integer partition of n >= 2(k + 3) (k + 1) can be reconstructed from its set of k-deletions. We describe a new reconstruction algorithm that lowers this bound to n >= k(2) + 2k and present examples showing that this bound is best possible.

The Zeta Function Of A Hypergraph, Christopher K. Storm

Dartmouth Scholarship

We generalize the Ihara-Selberg zeta function to hypergraphs in a natural way. Hashimoto's factorization results for biregular bipartite graphs apply, leading to exact factorizations. For $(d,r)$-regular hypergraphs, we show that a modified Riemann hypothesis is true if and only if the hypergraph is Ramanujan in the sense of Winnie Li and Patrick Solé. Finally, we give an example to show how the generalized zeta function can be applied to graphs to distinguish non-isomorphic graphs with the same Ihara-Selberg zeta function.

Monomial Nonnegativity And The Bruhat Order, Brian Drake, Sean Gerrish, Mark Skandera

Dartmouth Scholarship

We show that five nonnegativity properties of polynomials coincide when restricted to polynomials of the form x_{1, pi(1)} ... x_n,pi(n) - x_{1, sigma(1)} ... x_{n, sigma(n)}, where $\pi and sigma are permutations in S_n. In particular, we show that each of these properties may be used to characterize the Bruhat order on S_n.

Two New Criteria For Comparison In The Bruhat Order, Brian Drake, Sean Gerrish, Mark Skandera

Dartmouth Scholarship

We give two new criteria by which pairs of permutations may be compared in defining the Bruhat order (of type $A$). One criterion utilizes totally nonnegative polynomials and the other utilizes Schur functions.

A Short Proof That ‘Proper = Unit’, Kenneth P. Bogart, Douglas B. West

Dartmouth Scholarship

A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.

Proper And Unit Bitolerance Orders And Graphs, Kenneth P. Bogart, Garth Isaak

Dartmouth Scholarship

We say any order ≺ is a tolerance order on a set of vertices if we may assign to each vertex x an interval I_x of real numbers and a real number t_x called a tolerance in such a way that x ≺ y if and only if the overlap of I_x and I_y is less than the minimum of t_x and t_y and the center of I_x is less than the center of I_y. An order is a bitolerance order if and only if there are intervals I_x and …

A Classification Of Certain Graphs With Minimal Imperfection Properties, S. H. Whitesides

Dartmouth Scholarship

The family of (α, ω) graphs are of interest for several reasons. For example, any minimal counter-example to Berge's Strong Perfect Graph Conjecture belongs to this family. This paper accounts for all (4, 3) graphs. One of these is not obtainable by existing techniques for generating (α + 1, ω) graphs from (α, ω) graphs.