Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 10 of 10
Full-Text Articles in Discrete Mathematics and Combinatorics
Fixed Points And Excedances In Restricted Permutations, Sergi Elizalde
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
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
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
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
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
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 x1, pi(1) ... xn,pi(n) - x1, sigma(1) ... xn, sigma(n), where $\pi and sigma are permutations in Sn. In particular, we show that each of these properties may be used to characterize the Bruhat order on Sn.
Two New Criteria For Comparison In The Bruhat Order, Brian Drake, Sean Gerrish, Mark Skandera
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
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
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 Ix of real numbers and a real number tx called a tolerance in such a way that x ≺ y if and only if the overlap of Ix and Iy is less than the minimum of tx and ty and the center of Ix is less than the center of Iy. An order is a bitolerance order if and only if there are intervals Ix and …
A Classification Of Certain Graphs With Minimal Imperfection Properties, S. H. Whitesides
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.