BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bruce E. Sagan

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

ResearcherUnclaimed source record
math.COmath.ATmath.NTmath.PRmath.RAmath.RT

Catalog footprint

What is connected

24works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

24 published item(s)

preprint2022arXiv

q-Stirling numbers in type B

Stirling numbers, which count partitions of a set and permutations in the symmetric group, have found extensive application in combinatorics, geometry, and algebra. We study analogues and q-analogues of these numbers corresponding to the Coxeter group of type B. In particular, we show how they are related to complete homogeneous and elementary symmetric polynomials; demonstrate how they q-count signed partitions and permutations; compute their ordinary, exponential, and q-exponential generating functions; and prove various identities about them. Ordered analogues of the q-Stirling numbers of the second kind have recently appeared in conjectures of Zabrocki and of Swanson--Wallach concerning the Hilbert series of certain super coinvariant algebras. We provide conjectural bases for these algebras and show that they have the correct Hilbert series.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Rowmotion on rooted trees

A rooted tree T is a poset whose Hasse diagram is a graph-theoretic tree having a unique minimal element. We study rowmotion on antichains and lower order ideals of T. Recently Elizalde, Roby, Plante and Sagan considered rowmotion on fences which are posets whose Hasse diagram is a path (but permitting any number of minimal elements). They showed that in this case, the orbits could be described in terms of tilings of a cylinder. They also defined a new notion called homometry which means that a statistic takes a constant value on all orbits of the same size. This is a weaker condition than the well-studied concept of homomesy which requires a constant value for the average of the statistic over all orbits. Rowmotion on fences is often homometric for certain statistics, but not homomesic. We introduce a tiling model for rowmotion on rooted trees. We use it to study various specific types of trees and show that they exhibit homometry, although not homomesy, for certain statistics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bijective proofs of proper coloring theorems

The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a rank-unimodality conjecture of Morier-Genoud and Ovsienko

Let alpha = (a,b,...) be a composition. Consider the associated poset F(alpha), called a fence, whose covering relations are x_1 < x_2 < ... < x_{a+1} > x_{a+2} > ... > x_{a+b+1} < x_{a+b+2} < ... . We study the associated distributive lattice L(alpha) consisting of all lower order ideals of F(alpha). These lattices are important in the theory of cluster algebras and their rank generating functions can be used to define q-analogues of rational numbers. In particular, we make progress on a recent conjecture of Morier-Genoud and Ovsienko that L(alpha) is rank unimodal. We show that if one of the parts of alpha is greater than the sum of the others, then the conjecture is true. We conjecture that L(alpha) enjoys the stronger properties of having a nested chain decomposition and having a rank sequence which is either top or bottom interlacing, the latter being a recently defined property of sequences. We verify that these properties hold for compositions with at most three parts and for what we call d-divided posets, generalizing work of Claussen and simplifying a construction of Gansner.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Increasing spanning forests in graphs and simplicial complexes

Let G be a graph with vertex set {1,...,n}. A spanning forest F of G is increasing if the sequence of labels on any path starting at the minimum vertex of a tree of F form an increasing sequence. Hallam and Sagan showed that the generating function ISF(G,t) for increasing spanning forests of G has all nonpositive integral roots. Furthermore they proved that, up to a change of sign, this polynomial equals the chromatic polynomial of G precisely when 1,...,n is a perfect elimination order for G. We give new, purely combinatorial proofs of these results which permit us to generalize them in several ways. For example, we are able to bound the coefficients of ISF(G,t) using broken circuits. We are also able to extend these results to simplicial complexes using the new notion of a cage-free complex. A generalization to labeled multigraphs is also given. We end by exploring spanning forests where the increasing condition is replaced by having the label sequences avoid the patterns 231, 312, and 321.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Restricted growth function patterns and statistics

A restricted growth function (RGF) of length n is a sequence w = w_1 w_2 ... w_n of positive integers such that w_1 = 1 and w_i is at most 1 + max{w_1,..., w_{i-1}} for i at least 2. RGFs are of interest because they are in natural bijection with set partitions of {1, 2, ..., n}. RGF w avoids RGF v if there is no subword of w which standardizes to v. We study the generating functions sum_{w in R_n(v)} q^{st(w)} where R_n(v) is the set of RGFs of length n which avoid v and st(w) is any of the four fundamental statistics on RGFs defined by Wachs and White. These generating functions exhibit interesting connections with integer partitions and two-colored Motzkin paths, as well as noncrossing and nonnesting set partitions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Bijections on m-level Rook Placements

Suppose the rows of a board are partitioned into sets of m rows called levels. An m-level rook placement is a subset of the board where no two squares are in the same column or the same level. We construct explicit bijections to prove three theorems about such placements. We start with two bijections between Ferrers boards having the same number of m-level rook placements. The first generalizes a map by Foata and Sch\"utzenberger and our proof applies to any Ferrers board. This bijection also preserves the m-inversion number statistic of an m-level rook placement, defined by Briggs and Remmel. The second generalizes work of Loehr and Remmel. This construction only works for a special class of Ferrers boards, but it yields a formula for calculating the rook numbers of these boards in terms of elementary symmetric functions. Finally we generalize another result of Loehr and Remmel giving a bijection between boards with the same hit numbers. The second and third bijections involve the Involution Principle of Garsia and Milne.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distance preserving graphs and graph products

If $G$ is a graph then a subgraph $H$ is $isometric$ if, for every pair of vertices $u,v$ of $H$, we have $d_H(u,v) = d_G(u,v)$ where $d$ is the distance function. We say a graph $G$ is $distance\ preserving\ (dp)$ if it has an isometric subgraph of every possible order up to the order of $G$. We give a necessary and sufficient condition for the lexicographic product of two graphs to be a dp graph. A graph $G$ is $sequentially\ distance\ preserving\ (sdp)$ if the vertex set of $G$ can be ordered so that, for all $i\ge1$, deleting the first $i$ vertices in the sequence results in an isometric graph. We show that the Cartesian product of two graphs is sdp if and only if each of them is sdp. In closing, we state a conjecture concerning the Cartesian products of dp graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Factoring the characteristic polynomial of a lattice

We introduce a new method for showing that the roots of the characteristic polynomial of certain finite lattices are all nonnegative integers. This method is based on the notion of a quotient of a poset which will be developed to explain this factorization. Our main theorem will give two simple conditions under which the characteristic polynomial factors with nonnegative integer roots. We will see that Stanley's Supersolvability Theorem is a corollary of this result. Additionally, we will prove a theorem which gives three conditions equivalent to factorization. To our knowledge, all other theorems in this area only give conditions which imply factorization. This theorem will be used to connect the generating function for increasing spanning forests of a graph to its chromatic polynomial. We finish by mentioning some other applications of quotients of posets as well as some open questions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Set partition patterns and statistics

A set partition $σ$ of $[n]=\{1,\dots,n\}$ contains another set partition $π$ if restricting $σ$ to some $S\subseteq[n]$ and then standardizing the result gives $π$. Otherwise we say $σ$ avoids $π$. For all sets of patterns consisting of partitions of $[3]$, the sizes of the avoidance classes were determined by Sagan and by Goyt. Set partitions are in bijection with restricted growth functions (RGFs) for which Wachs and White defined four fundamental statistics. We consider the distributions of these statistics over various avoidance classes, thus obtaining multivariate analogues of the previously cited cardinality results. This is the first in-depth study of such distributions. We end with a list of open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Constructing Regular Distance-Preserving Graphs

Let G be a simple, connected graph on n vertices. Let d_G(u,v) denote the distance between vertices u and v in G. A subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for every u,v in V(H). We say that G is a distance-preserving graph if G contains at least one isometric subgraph of order k for every k, 1\le k\le n. In this paper we construct regular distance-preserving graphs of all possible orders and degrees of regularity. By modifying the Havel-Hakimi algorithm, we are able to construct distance preserving graphs for certain other degree sequences as well. We include a discussion of some related conjectures which we have computationally verified for small values of n.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Fibonacci polynomials and Fibonomial coefficients

The focus of this paper is the study of generalized Fibonacci polynomials and Fibonomial coefficients. The former are polynomials {n} in variables s and t given by {0} = 0, {1} = 1, and {n} = s{n-1}+t{n-2} for n ge 2. The latter are defined by {n choose k} = {n}!/({k}!{n-k}!) where {n}! = {1}{2}...{n}. These quotients are also polynomials in s and t, and specializations give the ordinary binomial coefficients, the Fibonomial coefficients, and the q-binomial coefficients. We present some of their fundamental properties, including a more general recursion for {n}, an analogue of the binomial theorem, a new proof of the Euler-Cassini identity in this setting with applications to estimation of tails of series, and valuations when s and t take on integral values. We also study a corresponding analogue of the Catalan numbers. Conjectures and open problems are scattered throughout the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

m-Level rook placements

Goldman, Joichi, and White proved a beautiful theorem showing that the falling factorial generating function for the rook numbers of a Ferrers board factors over the integers. Briggs and Remmel studied an analogue of rook placements where rows are replaced by sets of $m$ rows called levels. They proved a version of the factorization theorem in that setting, but only for certain Ferrers boards. We generalize this result to any Ferrers board as well as giving a p,q-analogue. We also consider a dual situation involving weighted file placements which permit more than one rook in the same row. In both settings, we discuss properties of the resulting equivalence classes such as the number of elements in a class. In addition, we prove analogues of a theorem of Foata and Schützenberger giving a distinguished representative in each class as well as make connections with the q,t-Catalan numbers. We end with some open questions raised by this work.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On 021-Avoiding Ascent Sequences

Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of $(\bf{2+2})$-free posets. An ascent sequence of length $n$ is a nonnegative integer sequence $x=x_{1}x_{2}... x_{n}$ such that $x_{1}=0$ and $x_{i}\leq \asc(x_{1}x_{2}...x_{i-1})+1$ for all $1<i\leq n$, where $\asc(x_{1}x_{2}...x_{i-1})$ is the number of ascents in the sequence $x_{1}x_{2}... x_{i-1}$. We let $\cA_n$ stand for the set of such sequences and use $\cA_n(p)$ for the subset of sequences avoiding a pattern $p$. Similarly, we let $S_{n}(τ)$ be the set of $τ$-avoiding permutations in the symmetric group $S_{n}$. Duncan and Steingr\'ımsson have shown that the ascent statistic has the same distribution over $\cA_n(021)$ as over $S_n(132)$. Furthermore, they conjectured that the pair $(\asc, \rlm)$ is equidistributed over $\cA_n(021)$ and $S_n(132)$ where $\rlm$ is the right-to-left minima statistic. We prove this conjecture by constructing a bistatistic-preserving bijection.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Permutation patterns and statistics

Let S_n denote the symmetric group of all permutations of the set {1, 2, ...,n} and let S = \cup_{n\ge0} S_n. If Pi is a set of permutations, then we let Av_n(Pi) be the set of permutations in S_n which avoid every permutation of Pi in the sense of pattern avoidance. One of the celebrated notions in pattern theory is that of Wilf-equivalence, where Pi and Pi' are Wilf equivalent if #Av_n(Pi)=#Av_n(Pi') for all n\ge0. In a recent paper, Sagan and Savage proposed studying a q-analogue of this concept defined as follows. Suppose st:S->N is a permutation statistic where N represents the nonnegative integers. Consider the corresponding generating function, F_n^{st}(Pi;q) = sum_{sigma in Av_n(Pi)} q^{st sigma}, and call Pi,Pi' st-Wilf equivalent if F_n^{st}(Pi;q)=F_n^{st}(Pi';q) for all n\ge0. We present the first in-depth study of this concept for the inv and maj statistics. In particular, we determine all inv- and maj-Wilf equivalences for any Pi containd in S_3. This leads us to consider various q-analogues of the Catalan numbers, Fibonacci numbers, triangular numbers, and powers of two. Our proof techniques use lattice paths, integer partitions, and Foata's fundamental bijection. We also answer a question about Mahonian pairs raised in the Sagan-Savage article.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Möbius function of generalized subword order

Let P be a poset and let P* be the set of all finite length words over P. Generalized subword order is the partial order on P* obtained by letting u \leq w if and only if there is a subword u' of w having the same length as u such that each element of u is less than or equal to the corresponding element of u' in the partial order on P. Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P, we give a simple formula for the Mobius function of P* in terms of the Mobius function of P. This permits us to rederive in a easy and uniform manner previous results of Bjorner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P* for any finite P of rank at most 1.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Counting (3+1) - Avoiding permutations

A poset is {\it $(\3+\1)$-free} if it contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. These posets are of interest because of their connection with interval orders and their appearance in the $(\3+\1)$-free Conjecture of Stanley and Stembridge. The dimension 2 posets $P$ are exactly the ones which have an associated permutation $π$ where $i\prec j$ in $P$ if and only if $i<j$ as integers and $i$ comes before $j$ in the one-line notation of $π$. So we say that a permutation $π$ is {\it $(\3+\1)$-free} or {\it $(\3+\1)$-avoiding} if its poset is $(\3+\1)$-free. This is equivalent to $π$ avoiding the permutations 2341 and 4123 in the language of pattern avoidance. We give a complete structural characterization of such permutations. This permits us to find their generating function.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Mahonian Pairs

We introduce the notion of a Mahonian pair. Consider the set, P^*, of all words having the positive integers as alphabet. Given finite subsets S,T of P^*, we say that (S,T) is a Mahonian pair if the distribution of the major index, maj, over S is the same as the distribution of the inversion number, inv, over T. So the well-known fact that maj and inv are equidistributed over the symmetric group, S_n, can be expressed by saying that (S_n,S_n) is a Mahonian pair. We investigate various Mahonian pairs (S,T) with S different from T. Our principal tool is Foata's fundamental bijection f: P^* -> P^* since it has the property that maj w = inv f(w) for any word w. We consider various families of words associated with Catalan and Fibonacci numbers. We show that, when restricted to words in {1,2}^*, f transforms familiar statistics on words into natural statistics on integer partitions such as the size of the Durfee square. The Rogers-Ramanujan identities, the Catalan triangle, and various q-analogues also make an appearance. We generalize the definition of Mahonian pairs to infinite sets and use this as a tool to connect a partition bijection of Corteel-Savage-Venkatraman with the Greene-Kleitman decomposition of a Boolean algebra into symmetric chains. We close with comments about future work and open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The cyclic sieving phenomenon: a survey

The cyclic sieving phenomenon was defined by Reiner, Stanton, and White in a 2004 paper. Let X be a finite set, C be a finite cyclic group acting on X, and f(q) be a polynomial in q with nonnegative integer coefficients. Then the triple (X,C,f(q)) exhibits the cyclic sieving phenomenon if, for all g in C, we have # X^g = f(w) where # denotes cardinality, X^g is the fixed point set of g, and w is a root of unity chosen to have the same order as g. It might seem improbable that substituting a root of unity into a polynomial with integer coefficients would have an enumerative meaning. But many instances of the cyclic sieving phenomenon have now been found. Furthermore, the proofs that this phenomenon hold often involve interesting and sometimes deep results from representation theory. We will survey the current literature on cyclic sieving, providing the necessary background about representations, Coxeter groups, and other algebraic aspects as needed.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Partitions, rooks, and symmetric functions in noncommuting variables

Let $Π_n$ denote the set of all set partitions of $\{1,2,\ldots,n\}$. We consider two subsets of $Π_n$, one connected to rook theory and one associated with symmetric functions in noncommuting variables. Let $\cE_n\sbeΠ_n$ be the subset of all partitions corresponding to an extendable rook (placement) on the upper-triangular board, $\cT_{n-1}$. Given $π\inΠ_m$ and $\si\inΠ_n$, define their {\it slash product\/} to be $π|\si=π\cup(\si+m)\inΠ_{m+n}$ where $\si+m$ is the partition obtained by adding $m$ to every element of every block of $\si$. Call $τ$ {\it atomic\/} if it can not be written as a nontrivial slash product and let $\cA_n\sbeΠ_n$ denote the subset of atomic partitions. Atomic partitions were first defined by Bergeron, Hohlweg, Rosas, and Zabrocki during their study of $NCSym$, the symmetric functions in noncommuting variables. We show that, despite their very different definitions, $\cE_n=\cA_n$ for all $n\ge0$. Furthermore, we put an algebra structure on the formal vector space generated by all rook placements on upper triangular boards which makes it isomorphic to $NCSym$. We end with some remarks and an open problem.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Infinite log-concavity: developments and conjectures

Given a sequence (a_k) = a_0, a_1, a_2,... of real numbers, define a new sequence L(a_k) = (b_k) where b_k = a_k^2 - a_{k-1} a_{k+1}. So (a_k) is log-concave if and only if (b_k) is a nonnegative sequence. Call (a_k) "infinitely log-concave" if L^i(a_k) is nonnegative for all i >= 1. Boros and Moll conjectured that the rows of Pascal's triangle are infinitely log-concave. Using a computer and a stronger version of log-concavity, we prove their conjecture for the nth row for all n <= 1450. We also use our methods to give a simple proof of a recent result of Uminsky and Yeats about regions of infinite log-concavity. We investigate related questions about the columns of Pascal's triangle, q-analogues, symmetric functions, real-rooted polynomials, and Toeplitz matrices. In addition, we offer several conjectures.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

The Multiplicities of a Dual-thin Q-polynomial Association Scheme

Let Y denote a symmetric association scheme which is Q-polynomial with respect to an ordering E_0,...,E_D of the primitive idempotents. Bannai and Ito conjectured that the associated sequence of multiplicities m_0,...,m_D is unimodal. We prove that if Y is dual-thin in the sense of Terwilliger, then the sequence of multiplicities satisfies m_i <= m_{i+1} and m_i <= m_{D-i} for i < D/2.

0 citations0 reviewsNo code linkedOpen access