Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Mathematics

Series

Combinatorics

Institution
Publication Year
Publication

Articles 1 - 30 of 59

Full-Text Articles in Physical Sciences and Mathematics

Staircase Packings Of Integer Partitions, Melody Arteaga May 2023

Staircase Packings Of Integer Partitions, Melody Arteaga

Mathematics, Statistics, and Computer Science Honors Projects

An integer partition is a weakly decreasing sequence of positive integers. We study the family of packings of integer partitions in the triangular array of size n, where successive partitions in the packings are separated by at least one zero. We prove that these are enumerated by the Bell-Like number sequence (OEIS A091768), and investigate its many recursive properties. We also explore their poset (partially ordered set) structure. Finally, we characterize various subfamilies of these staircase packings, including one restriction that connects back to the original patterns of the whole family.

Go to article

Minimal Inscribed Polyforms, Jack Hanke May 2022

Minimal Inscribed Polyforms, Jack Hanke

Honors Scholar Theses

A polyomino of size n is constructed by joining n unit squares together by their edge to form a shape in the plane. This thesis will first examine the formal definition of a polyomino and the common equivalence classes polyominos are enumerated under. We then turn to polyomino families, and provide exact enumeration results for certain families, including the minimal inscribed polyominos. Next we will generalize polyominos to polyforms, and provide novel formulae for polyform analogues of minimal inscribed polyominos. Finally, we discuss some further questions concerning minimal inscribed polyforms.

Go to article

Representation Stability Of The Cohomology Of Springer Varieties And Some Combinatorial Consequences, Aba Mbirika, Julianna Tymoczko May 2021

Representation Stability Of The Cohomology Of Springer Varieties And Some Combinatorial Consequences, Aba Mbirika, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

A sequence of Sn-representations { Vn} is said to be uniformly representation stable if the decomposition of Vn= ⨁ μcμ,nV(μ) n into irreducible representations is independent of n for each μ—that is, the multiplicities cμ,n are eventually independent of n for each μ. Church–Ellenberg–Farb proved that the cohomology of flag varieties (the so-called diagonal coinvariant algebra) is uniformly representation stable. We generalize their result from flag varieties to all Springer fibers. More precisely, we show that for any increasing subsequence of Young diagrams, the corresponding sequence of Springer representations form a graded co-FI-module of finite type (in the sense of …

Go to article

Hadamard Equiangular Tight Frames, Matthew C. Fickus, John Jasper, Dustin G. Mixon, Jesse D. Peterson Aug 2019

Hadamard Equiangular Tight Frames, Matthew C. Fickus, John Jasper, Dustin G. Mixon, Jesse D. Peterson

Faculty Publications

An equiangular tight frame (ETF) is a type of optimal packing of lines in Euclidean space. They are often represented as the columns of a short, fat matrix. In certain applications we want this matrix to be flat, that is, have the property that all of its entries have modulus one. In particular, real flat ETFs are equivalent to self-complementary binary codes that achieve the Grey-Rankin bound. Some flat ETFs are (complex) Hadamard ETFs, meaning they arise by extracting rows from a (complex) Hadamard matrix. These include harmonic ETFs, which are obtained by extracting the rows of a character table …

Go to article

Stirling Numbers Of Sunflower Graphs, Jose Garcia, Jessica Longo, Matt Phad, Page Wilson May 2019

Stirling Numbers Of Sunflower Graphs, Jose Garcia, Jessica Longo, Matt Phad, Page Wilson

Undergraduate Research

A Stirling number of the second kind, S(n, k), is the number of ways to take all of the elements from an n element set and put them into k subsets, so that the subsets are non-empty and pairwise disjoint. To get the graphical Stirling number for a graph G, we add the restriction that any two vertices that are adjacent in G cannot be in the same subset. The traditional Stirling numbers are the graphical Stirling number where the graph is empty. We find graphical Stirling numbers for sunflower graphs, which are powers of paths …

Go to article

Blackjack: The Math Behind The Cards, Hanna Blanchard Apr 2019

Blackjack: The Math Behind The Cards, Hanna Blanchard

Mathematics Senior Capstone Papers

In this paper the reader will learn about the math behind the cards in the game of Blackjack. Blackjack or “21” has been played around the world with various rules and regulations in both professional and informal environments. The ultimate objective of the game is to receive a total card value of 21, or as close to 21 as possible without exceeding it, from the cards in a player’s hand in order to beat the dealer’s total. The goal of this project is to calculate the probabilities of various hands to determine the best strategies to win 21. The probabilities …

Go to article

The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger Mar 2019

The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger

Faculty Publications

In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim(G1+G2)=1+dimG1+dimG2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order N will have dimension N−1. We finish by finding lower and upper bounds on the Knill dimension of a graph in terms of its clique number.

Go to article

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley Mar 2016

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

Lusztig's theory of PBW bases gives a way to realize the infinity crystal for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our …

Go to article

A Simplification Of Inclusion-Exclusion Via Minimal Complexes, Andrew J. Brandt Jan 2016

A Simplification Of Inclusion-Exclusion Via Minimal Complexes, Andrew J. Brandt

Summer Research

This poster discusses the discovery and use of previously unproved methods for solving counting problems using the fundamental ideas of the inclusion exclusion-principle and the Euler characteristic. While both methods use a weighted version of the Euler characteristic to determine the order of a union of finite sets, the first method can be used with contractible, planar graphs whereas the second method generalizes this idea to multi-dimensional complexes and their minimal complexes. These methods seem to be promising in their applications to subjects such as homology theory, Betti numbers, and abstract tubes.

Go to article

Generalized Eulerian Numbers And Multiplex Juggling Sequences, Esther M. Banaian Jan 2016

Generalized Eulerian Numbers And Multiplex Juggling Sequences, Esther M. Banaian

All College Thesis Program, 2016-2019

We consider generalizations of both juggling sequences and non-attacking rook placements. We demonstrate the important connection between these objects, and also propose a generalization of the Eulerian numbers. These generalizations give rise to several interesting counting problems, which we explore.

Go to article

Properties Of Catlin’S Reduced Graphs And Supereulerian Graphs, Wei-Guo Chen, Zhi-Hong Chen, Mei Lu Sep 2015

Properties Of Catlin’S Reduced Graphs And Supereulerian Graphs, Wei-Guo Chen, Zhi-Hong Chen, Mei Lu

Scholarship and Professional Work - LAS

A graph G is called collapsible if for every even subset R ⊆ V (G), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is the reduction of G if it is obtained from G by contracting all the nontrivial collapsible subgraphs. A graph is reduced if it has no nontrivial collapsible subgraphs. In this paper, we first prove a few results on the properties of reduced graphs. As an application, for 3-edge-connected graphs G of order n with d(u) + d(v) ≥ 2(n/p − …

Go to article

On Representations Of Semigroups Having Hypercube-Like Cayley Graphs, Cody Cassiday, G. Stacey Staples Jan 2015

On Representations Of Semigroups Having Hypercube-Like Cayley Graphs, Cody Cassiday, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

The $n-dimensional hypercube, or n-cube, is the Cayley graph of the Abelian group Z2n. A number of combinatorially-interesting groups and semigroups arise from modified hypercubes. The inherent combinatorial properties of these groups and semigroups make them useful in a number of contexts, including coding theory, graph theory, stochastic processes, and even quantum mechanics. In this paper, particular groups and semigroups whose Cayley graphs are generalizations of hypercubes are described, and their irreducible representations are characterized. Constructions of faithful representations are also presented for each semigroup. The associated semigroup algebras are realized within the context …

Go to article

A Combinatorial Proof Of A Theorem Of Katsuura, Brian K. Miceli Nov 2014

A Combinatorial Proof Of A Theorem Of Katsuura, Brian K. Miceli

Mathematics Faculty Research

We give a combinatorial proof of an algebraic result of Katsuura's. Moreover, we use the proof of this result to shed some light on an interesting property of the result itself.

Go to article

The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg Nov 2014

The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg

Faculty Publications

Symmetry plays a fundamental role in design of experiments. In particular, symmetries of factorial designs that preserve their statistical properties are exploited to find designs with the best statistical properties. By using a result proved by Rosenberg [6], the concept of the LP relaxation orthogonal array polytope is developed and studied. A complete characterization of the permutation symmetry group of this polytope is made. Also, this characterization is verified computationally for many cases. Finally, a proof is provided.

Go to article

Edge-Connectivities For Spanning Trails With Prescribed Edges, Wei-Guo Chen, Zhi-Hong Chen, Weiqi Luo Jul 2014

Edge-Connectivities For Spanning Trails With Prescribed Edges, Wei-Guo Chen, Zhi-Hong Chen, Weiqi Luo

Scholarship and Professional Work - LAS

No abstract provided.

Go to article

Slicing A Puzzle And Finding The Hidden Pieces, Martha Arntson Apr 2013

Slicing A Puzzle And Finding The Hidden Pieces, Martha Arntson

Honors Program Projects

The research conducted was to investigate the potential connections between group theory and a puzzle set up by color cubes. The goal of the research was to investigate different sized puzzles and discover any relationships between solutions of the same sized puzzles. In this research, first, there was an extensive look into the background of Abstract Algebra and group theory, which is briefly covered in the introduction. Then, each puzzle of various sizes was explored to find all possible color combinations of the solutions. Specifically, the 2x2x2, 3x3x3, and 4x4x4 puzzles were examined to find that the 2x2x2 has 24 …

Go to article

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar Jan 2013

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

Go to article

The Rook-Brauer Algebra, Elise G. Delmas May 2012

The Rook-Brauer Algebra, Elise G. Delmas

Mathematics, Statistics, and Computer Science Honors Projects

We introduce an associative algebra RBk(x) that has a basis of rook-Brauer diagrams. These diagrams correspond to partial matchings on 2k vertices. The rook-Brauer algebra contains the group algebra of the symmetric group, the Brauer algebra, and the rook monoid algebra as subalgebras. We show that the basis of RBk(x) is generated by special diagrams si, ti (1 <= i < k) and pj (1 <= j <= k), where the si are the simple transpositions that generated the symmetric group Sk, the ti are the "contraction maps" which generate the …

Go to article

Linear Combinations Of Heuristics For Examination Timetabling, Jay Yellen, Edmund K. Burke, Nam Pham Apr 2012

Linear Combinations Of Heuristics For Examination Timetabling, Jay Yellen, Edmund K. Burke, Nam Pham

Faculty Publications

Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In …

Go to article

Combinatorics Of Two-Toned Tilings, Arthur T. Benjamin, Phyllis Chinn, Jacob N. Scott '11, Greg Simay Nov 2011

Combinatorics Of Two-Toned Tilings, Arthur T. Benjamin, Phyllis Chinn, Jacob N. Scott '11, Greg Simay

All HMC Faculty Publications and Research

We introduce the function a(r, n) which counts tilings of length n + r that utilize white tiles (whose lengths can vary between 1 and n) and r identical red squares. These tilings are called two-toned tilings. We provide combinatorial proofs of several identities satisfied by a(r, n) and its generalizations, including one that produces kth order Fibonacci numbers. Applications to integer partitions are also provided.

Go to article

A New Framework For Network Disruption, Susan E. Martonosi, Doug Altner, Michael Ernst, Elizabeth Ferme, Kira Langsjoen, Danika Lindsay, Sean S. Plott '08, Andrew S. Ronan Sep 2011

A New Framework For Network Disruption, Susan E. Martonosi, Doug Altner, Michael Ernst, Elizabeth Ferme, Kira Langsjoen, Danika Lindsay, Sean S. Plott '08, Andrew S. Ronan

All HMC Faculty Publications and Research

Traditional network disruption approaches focus on disconnecting or lengthening paths in the network. We present a new framework for network disruption that attempts to reroute flow through critical vertices via vertex deletion, under the assumption that this will render those vertices vulnerable to future attacks. We define the load on a critical vertex to be the number of paths in the network that must flow through the vertex. We present graph-theoretic and computational techniques to maximize this load, firstly by removing either a single vertex from the network, secondly by removing a subset of vertices.

Go to article

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn Jun 2011

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn

All HMC Faculty Publications and Research

We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.

Go to article

Third And Fourth Binomial Coefficients, Arthur T. Benjamin, Jacob N. Scott '11 May 2011

Third And Fourth Binomial Coefficients, Arthur T. Benjamin, Jacob N. Scott '11

All HMC Faculty Publications and Research

While formulas for the sums of kth binomial coefficients can be shown inductively or algebraically, these proofs give little insight into the combinatorics involved. We prove formulas for the sums of 3rd and 4th binomial coefficients via purely combinatorial arguments.

Go to article

A Census Of Vertices By Generations In Regular Tessellations Of The Plane, Alice Paul '12, Nicholas Pippenger Apr 2011

A Census Of Vertices By Generations In Regular Tessellations Of The Plane, Alice Paul '12, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider regular tessellations of the plane as infinite graphs in which q edges and q faces meet at each vertex, and in which p edges and p vertices surround each face. For 1/p + 1/q = 1/2, these are tilings of the Euclidean plane; for 1/p + 1/q < 1/2, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all p ≥ 3 and q ≥ 3 with 1/p + 1/q ≤ 1/2, we give simple combinatorial derivations of the rational generating functions for the number of vertices in each generation.

Go to article

Sums Of Evenly Spaced Binomial Coefficients, Arthur T. Benjamin, Bob Chen '10, Kimberly Kindred Dec 2010

Sums Of Evenly Spaced Binomial Coefficients, Arthur T. Benjamin, Bob Chen '10, Kimberly Kindred

All HMC Faculty Publications and Research

We provide a combinatorial proof of a formula for the sum of evenly spaced binomial coefficients. This identity, along with a generalization, are proved by counting weighted walks on a graph.

Go to article

Poset Pinball, Gkm-Compatible Subspaces, And Hessenberg Varieties, Megumi Harada, Julianna Tymoczko Jul 2010

Poset Pinball, Gkm-Compatible Subspaces, And Hessenberg Varieties, Megumi Harada, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

This paper has three main goals. First, we set up a general framework to address the problem of constructing module bases for the equivariant cohomology of certain subspaces of GKM spaces. To this end we introduce the notion of a GKM-compatible subspace of an ambient GKM space. We also discuss poset-upper-triangularity, a key combinatorial notion in both GKM theory and more generally in localization theory in equivariant cohomology. With a view toward other applications, we present parts of our setup in a general algebraic and combinatorial framework. Second, motivated by our central problem of building module bases, we introduce a …

Go to article

On The Characteristic Polynomial Of Regular Linear Matrix Pencil, Yan Wu, Phillip Lorren Jun 2010

On The Characteristic Polynomial Of Regular Linear Matrix Pencil, Yan Wu, Phillip Lorren

Department of Mathematical Sciences Faculty Publications

Linear matrix pencil, denoted by (A,B), plays an important role in control systems and numerical linear algebra. The problem of finding the eigenvalues of (A,B) is often solved numerically by using the well-known QZ method. Another approach for exploring the eigenvalues of (A,B) is by way of its characteristic polynomial, P(λ)=A − λB. There are other applications of working directly with the characteristic polynomial, for instance, using Routh-Hurwitz analysis to count the stable roots of P(λ) and transfer function representation of control systems governed by differential-algebraic equations. In this paper, we …

Go to article

Voting, The Symmetric Group, And Representation Theory, Zajj Daugherty '05, Alexander K. Eustis '06, Gregory Minton '08, Michael E. Orrison Dec 2009

Voting, The Symmetric Group, And Representation Theory, Zajj Daugherty '05, Alexander K. Eustis '06, Gregory Minton '08, Michael E. Orrison

All HMC Faculty Publications and Research

We show how voting may be viewed naturally from an algebraic perspective by viewing voting profiles as elements of certain well-studied QSn-modules. By using only a handful of simple combinatorial objects (e.g., tabloids) and some basic ideas from representation theory (e.g., Schur's Lemma), this allows us to recast and extend some well-known results in the field of voting theory.

Go to article

Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter Jul 2009

Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter

Dartmouth Scholarship

The permutation π of length n, written in one-line notation as π (1)π (2)· · · π (n), is said to contain the permutation σ if π has a subsequence that is order isomorphic to σ, and each such subsequence is said to be an occurrence of σ in π or simply a σ pattern. For example, π = 491867532 contains σ = 51342 because of the subsequence π (2)π (3)π (5)π (6)π (9) = 91672. Permutation containment is easily seen to be a partial order on the set of all (finite) permutations, which we simply denote by ≤. If …

Go to article

Counting On Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07 Apr 2009

Counting On Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

Chebyshev polynomials have several elegant combinatorial interpretations. Specificially, the Chebyshev polynomials of the first kind are defined by T0(x) = 1, T1(x) = x, and Tn(x) = 2x Tn-1(x) - Tn-2(x). Chebyshev polynomials of the second kind Un(x) are defined the same way, except U1(x) = 2x. Tn and Un are shown to count tilings of length n strips with squares and dominoes, where the tiles are given weights and sometimes color. Using these interpretations, many identities satisfied by Chebyshev polynomials can be given …

Go to article

Next Last