Discrete Mathematics and Combinatorics Commons^™

Dissertation_Davis.Pdf, Brian Davis

brian davis

Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez

Vicente Valle Martinez

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Ronald Greenberg

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Ronald Greenberg

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.

An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

Jennifer J. Quinn

In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindström-Gessel-Viennot in which we count nonintersecting n-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.

Fibonacci Determinants — A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

Jennifer J. Quinn

In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindström-Gessel-Viennot in which we count nonintersecting n-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.

Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben

Namrata Vaswani

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above …

Tree Diagrams For String Links, Blake Mellor

Blake Mellor

In previous work, the author defined the intersection graph of a chord diagram associated with string links (as in the theory of finite type invariants). In this paper, we classify the trees which can be obtained as intersection graphs of string link diagrams.

Tree Diagrams For String Links Ii: Determining Chord Diagrams, Blake Mellor

Blake Mellor

In previous work, we defined the intersection graph of a chord diagram associated with a string link (as in the theory of finite type invariants). In this paper, we look at the case when this graph is a tree, and we show that in many cases these trees determine the chord diagram (modulo the usual 1-term and 4-term relations).

Symmetries Of Embedded Complete Bipartite Graphs, Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn

Blake Mellor

We characterize which automorphisms of an arbitrary complete bipartite graph Kn,m can be induced by a homeomorphism of some embedding of the graph in S3.

Chord Diagrams And Gauss Codes For Graphs, Thomas Fleming, Blake Mellor

Blake Mellor

Chord diagrams on circles and their intersection graphs (also known as circle graphs) have been intensively studied, and have many applications to the study of knots and knot invariants, among others. However, chord diagrams on more general graphs have not been studied, and are potentially equally valuable in the study of spatial graphs. We will define chord diagrams for planar embeddings of planar graphs and their intersection graphs, and prove some basic results. Then, as an application, we will introduce Gauss codes for immersions of graphs in the plane and give algorithms to determine whether a particular crossing sequence is …

Rogers-Ramanujan Computer Searches, James Mclaughlin, Andrew Sills, Peter Zimmer

James McLaughlin

We describe three computer searches (in PARI/GP, Maple, and Mathematica, respectively) which led to the discovery of a number of identities of Rogers–Ramanujan type and identities of false theta functions.

An Extremal Problem For Finite Lattices, John Goldwasser, Brendan Nagle, Andres Saez

John Copeland Nagle

For a fixed M x N integer lattice L(M,N), we consider the maximum size of a subset A of L(M,N) which contains no squares of prescribed side lengths k(1),...,k(t). We denote this size by ex(L(M,N), {k(1),...,k(t)}), and when t = 1, we abbreviate this parameter to ex(L(M,N), k), where k = k(1).

Our first result gives an exact formula for ex(L( …

On The Topology Of The Permutation Pattern Poset, Peter R. W. Mcnamara, Einar Steingrímsson

Peter R. W. McNamara

Examining The Literature On “Networks In Space And In Time.” An Introduction, Luca De Benedictis, Prosperina Vitale, Stanley Wasserman

Luca De Benedictis

The Network science special issue of “Networks in space and in time: methods and applications” contributes to the debate on contextual analysis in network science. It includes seven research papers that shed light on the analysis of network phenomena studied within geographic space and across temporal dimensions. In these papers, methodological issues as well as specific applications are described from different fields. We take the seven papers, study their citations and texts, and relate them to the broader literature. By exploiting the bibliographic information and the textual data of these seven documents, citation analysis and lexical correspondence analysis allow us …

Comparing Skew Schur Functions: A Quasisymmetric Perspective, Peter R. W. Mcnamara

Peter R. W. McNamara

Reiner, Shaw and van Willigenburg showed that if two skew Schur functions s_A and s_B are equal, then the skew shapes $A$ and $B$ must have the same "row overlap partitions." Here we show that these row overlap equalities are also implied by a much weaker condition than Schur equality: that s_A and s_B have the same support when expanded in the fundamental quasisymmetric basis F. Surprisingly, there is significant evidence supporting a conjecture that the converse is also true.

In fact, we work in terms of inequalities, showing that if the F-support of s_{A …}

A Bijective Proof Of A Factorization Formula For Specialized Macdonald Polynomials, Nicholas A. Loehr, Elizabeth Niese

Elizabeth Niese

Let μ and ν = (ν 1, . . . , ν k ) be partitions such that μ is obtained from ν by adding m parts of sizer. Descouens and Morita proved algebraically that the modified Macdonald polynomials H~μ(X;q,t) satisfy the identity H~μ=H~νH~(rm) when the parameter t is specialize to an mth root of unity. Descouens, Morita, and Numata proved this formula bijectively when r ≤ ν k and r∈{1,2}. This note gives a bijective proof of the formula for all r ≤ ν k .

New Combinatorial Formulations Of The Shuffle Conjecture, Nicholas A. Loehr, Elizabeth Niese

Elizabeth Niese

The shuffle conjecture (due to Haglund, Haiman, Loehr, Remmel, and Ulyanov) provides a combinatorial formula for the Frobenius series of the diagonal harmonics module DHn, which is the symmetric function∇(en). This formula is a sum over all labeled Dyck paths of terms built from combinatorial statistics called area, dinv, and IDes. We provide three new combinatorial formulations of the shuffle conjecture based on other statistics on labeled paths, parking functions, and related objects. Each such reformulation arises by introducing an appropriate new definition of the inverse descent set. Analogous results are proved for the higher-order shuffle conjecture involving ∇m(en). We …

A New Recursion For Three-Column Combinatorial Macdonald Polynomials, Elizabeth Niese

Elizabeth Niese

The Hilbert series of the Garsia–Haiman module Mμ can be described combinatorially as the generating function of certain fillings of the Ferrers diagram of μ where μ is an integer partition of n . Since there are n ! fillings that generate , it is desirable to find recursions to reduce the number of fillings that need to be considered when computing combinatorially. In this paper, we present a combinatorial recursion for the case where μ is an n by 3 rectangle. This allows us to reduce the number of fillings under consideration from (3n)! to (3n)!/(3!nn!).

An Injection From Standard Fillings To Parking Functions, Elizabeth Niese

Elizabeth Niese

The Hilbert series of the Garsia-Haiman module can be written as a generating function of standard fillings of Ferrers diagrams. It is conjectured by Haglund and Loehr that the Hilbert series of the diagonal harmonics can be written as a generating function of parking functions. In this paper we present a weight-preserving injection from standard fillings to parking functions for certain cases.

Unevening The Odds Of "Even Up", Arthur T. Benjamin, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Paint It Black -- A Combinatorial Yawp, Arthur T. Benjamin, Jennifer J. Quinn, James A. Sellers, Mark A. Shattuck

Jennifer J. Quinn

No abstract provided in this paper.

A Stirling Encounter With Harmonic Numbers, Arthur T. Benjamin, Gregory O. Preston '01, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Composite Fermions And Integer Partitions, Arthur Benjamin, Jennifer Quinn, John Quinn, Arkadiusz Wojs

Jennifer J. Quinn

We utilize the KOH theorem to prove the unimodality of integer partitions with at most a parts, all parts less than or equal to b, that are required to contain either repeated or consecutive parts. We connect this result to an open question in quantum physics relating the number of distinct total angular momentum multiplets of a system of N fermions, each with angular momentum ℓ, to those of a system in which each Fermion has angular momentum ℓ*=ℓ−N+1.

The Fibonacci Numbers -- Exposed More Discretely, Arthur T. Benjamin, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Random Approaches To Fibonacci Identities, Arthur T. Benjamin, Gregory M. Levin, Karl Mahlburg '01, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Counting On Continued Fractions, Arthur T. Benjamin, Francis E. Su, Jennifer J. Quinn

Jennifer J. Quinn

No abstract provided in this article.

Phased Tilings And Generalized Fibonacci Identities, Arthur T. Benjamin, Jennifer J. Quinn, Francis E. Su

Jennifer J. Quinn

Fibonacci numbers arise in the solution of many combinatorial problems. They count the number of binary sequences with no consecutive zeros, the number of sequences of 1's and 2's which sum to a given number, and the number of independent sets of a path graph. Similar interpretations exist for Lucas numbers. Using these interpretations, it is possible to provide combinatorial proofs that shed light on many interesting Fibonacci and Lucas identities (see [1], [3]). In this paper we extend the combinatorial approach to understand relationships among generalized Fibonacci numbers. Given G0 and G1 a generalized Fibonacci sequence G0, G1, G2,... …

Summing Cubes By Counting Rectangles, Arthur T. Benjamin, Jennifer J. Quinn, Calyssa Wurtz

Jennifer J. Quinn

No abstract provided in this article.