Source author record

David G. L. Wang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.CA math.CV math.MG

Catalog footprint

Research overview

26works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

A decomposition of ballot permutations, pattern avoidance and Gessel walks

A permutation whose any prefix has no more descents than ascents is called a ballot permutation. In this paper, we present a decomposition of ballot permutations that enables us to construct a bijection between ballot permutations and odd order permutations, which proves a set-valued extension of a conjecture due to Spiro using the statistic of peak values. This bijection also preserves the neighbors of the largest letter in permutations and thus resolves a refinement of Spiro' s conjecture proposed by Wang and Zhang. Our decomposition can be extended to well-labelled positive paths, a class of generalized ballot permutations arising from polytope theory, that were enumerated by Bernardi, Duplantier and Nadeau. We will also investigate the enumerative aspect of ballot permutations avoiding a single pattern of length 3 and establish a connection between 213-avoiding ballot permutations and Gessel walks.

preprint2020arXiv

A Toeplitz property of ballot permutations and odd order permutations

We give a new semi-combinatorial proof for the equality of the number of ballot permutations of length $n$ and the number of odd order permutations of length $n$ , which is due to Bernardi, Duplantier and Nadeau. Spiro conjectures that the descent number of ballot permutations and certain cyclic weight of odd order permutations of the same length are equi-distributed. We present a bijection to establish a Toeplitz property for ballot permutations with any fixed number of descents, and a Toeplitz property for odd order permutations with any fixed cyclic weight. This allows us to refine Spiro's conjecture by tracking the neighbors of the largest letter in permutations.

preprint2020arXiv

Around the $q$ -binomial-Eulerian polynomials

We find a combinatorial interpretation of Shareshian and Wachs' $q$ -binomial-Eulerian polynomials, which leads to an alternative proof of their $q$ - $γ$ -positivity using group actions. Motivated by the sign-balance identity of Désarménien--Foata--Loday for the $(\mathrm{des}, \mathrm{inv})$ -Eulerian polynomials, we further investigate the sign-balance of the $q$ -binomial-Eulerian polynomials. We show the unimodality of the resulting signed binomial-Eulerian polynomials by exploiting their continued fraction expansion and making use of a new quadratic recursion for the $q$ -binomial-Eulerian polynomials. We finally use the method of continued fractions to derive a new $(p,q)$ -extension of the $γ$ -positivity of binomial-Eulerian polynomials which involves crossings and nestings of permutations.

preprint2020arXiv

Geometry of limits of zeros of polynomial sequences of type $(1,2)$

We study the root distribution of some univariate polynomials satisfying a recurrence of order two with linear and quadratic polynomial coefficients. We show that the set of non-isolated limits of zeros of the polynomials is the closure of an arc, a circle, an interval or its exterior under the real line, the union of at most two different shapes of the above cases expect the union of an arc and a circle, and some degenerate forms.

preprint2020arXiv

Non-Schur-positivity of chromatic symmetric functions

We provide a formula for every Schur coefficient in the chromatic symmetric function of a graph in terms of special rim hook tabloids. This formula is useful in confirming the non-Schur positivity of the chromatic symmetric function of a graph, especially when Stanley's stable partition method does not work. As applications, we determine Schur positive fan graphs and Schur positive complete tripartite graphs. We show that any squid graph obtained by adding $n$ leaves to a common vertex on an $m$ -vertex cycle is not Schur positive if $m\ne 2n-1$ , and conjecture that neither are the squid graphs with $m=2n-1$ .

preprint2020arXiv

The edge metric dimension of the generalized Petersen graph $P(n,3)$ is 4

It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph $P(n,k)$ is at least 3. We prove that the graph $P(n,3)$ has edge dimension 4 for $n\ge 11$ , by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.

preprint2020arXiv

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation $π$ such that in any prefix of $π$ the descent number is not more than the ascent number. By using a reversal concatenation map, we give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, and connect this distribution and the joint distribution (pk, dp, des) of the peak, depth, and descent statistics over ordinary permutations in terms of generating functions. As corollaries, we obtain several formulas for the bivariate generating function for (i) the peak statistic over ballot permutations,(ii) the descent statistic over ballot permutations, and (iii) the depth statistic over ordinary permutations. In particular, we confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.

preprint2015arXiv

A Tutte-type characterization for graph factors

Let $G$ be a connected general graph. Let $f\colon V(G)\to \Z^+$ be a function. We show that $G$ satisfies the Tutte-type condition $o(G-S)\le f(S)\qquad\text{for all vertex subsets $S$},$ if and only if it contains a colored $J_f^*$ -factor for any $2$ -end-coloring, where $J_f^*(v)$ is the union of all odd integers smaller than $f(v)$ and the integer $f(v)$ itself. This is a generalization of the $(1,f)$ -odd factor characterization theorem, and answers a problem of Cui and Kano. We also derive an analogous characterization for graphs of odd orders, which addresses a problem of Akiyama and Kano.

preprint2015arXiv

Convolution Preserves Partial Synchronicity of Log-concave Sequences

In a recent proof of the log-concavity of genus polynomials of some families of graphs, Gross et al. defined the weakly synchronicity relation between log-concave sequences, and conjectured that the convolution operation by any log-concave sequence preserves weakly synchronicity. We disprove it by providing a counterexample. Furthermore, we find the so-called partial synchronicity relation between log-concave sequences, which is (i) weaker than the synchronicity, (ii) stronger than the weakly synchronicity, and (iii) preserved by the convolution operation.

preprint2015arXiv

On colored set partitions of type $B_n$

Generalizing Reiner's notion of set partitions of type $B_n$ , we define colored $B_n$ -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored $B_n$ -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored $B_n$ -partition. We find an asymptotic expression of the total number of colored $B_n$ -partitions up to an error of $O(n^{-1/2}\log^{7/2}{n})$ , and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored $B_n$ -partitions.

preprint2015arXiv

Surface embedding of non-bipartite $k$ -extendable graphs

We find the minimum number $k=μ'(Σ)$ for any surface $Σ$ , such that every $Σ$ -embeddable non-bipartite graph is not $k$ -extendable. In particular, we construct the so-called bow-tie graphs $C_6\bowtie P_n$ , and show that they are $3$ -extendable. This confirms the existence of an infinite number of $3$ -extendable non-bipartite graphs which can be embedded in the Klein bottle.

preprint2015arXiv

The CLLC conjecture holds for cyclic outer permutations

Recently, Gross et al. posed the LLC conjecture for the locally log-concavity of the genus distribution of every graph, and provided an equivalent combinatorial version, the CLLC conjecture, on the log-concavity of the generating function counting cycles of some permutation compositions. In this paper, we confirm the CLLC conjecture for cyclic permutations, with the aid of Hultman numbers and by applying the Hermite--Biehler theorem on the generating function of Stirling numbers of the first kind. This leads to a further conjecture that every local genus polynomial is real-rooted.

preprint2015arXiv

The maximum number of perfect matchings of semi-regular graphs

Let $n\ge 34$ be an even integer, and $D_n=2\lceil n/4 \rceil-1$ . In this paper, we prove that every $\{D_n,\,D_n+1\}$ -graph of order $n$ contains $\lceil n/4 \rceil$ disjoint perfect matchings. This result is sharp in the sense that (i) there exists a $\{D_n,\,D_n+1\}$ -graph containing exactly $\lceil n/4 \rceil$ disjoint perfect matchings, and that (ii) there exists a $\{D_n-1,\,D_n\}$ -graph without perfect matchings for each $n$ . As a consequence, for any integer $D\ge D_n$ , every $\{D,\,D+1\}$ -graph of order $n$ contains $\lceil (D+1)/2 \rceil$ disjoint perfect matchings. This extends Csaba et~al.'s breathe-taking result that every $D$ -regular graph of sufficiently large order is $1$ -factorizable, generalizes Zhang and Zhu's result that every $D_n$ -regular graph of order $n$ contains $\lceil n/4 \rceil$ disjoint perfect matchings, and improves Hou's result that for all $k\ge n/2$ , every $\{k,\,k+1\}$ -graph of order $n$ contains $(\lfloor n/3\rfloor+1+k-n/2)$ disjoint perfect matchings.

preprint2014arXiv

Log-Concavity of Combinations of Sequences and Applications to Genus Distributions

We formulate conditions on a set of log-concave sequences, under which any linear combination of those sequences is log-concave, and further, of conditions under which linear combinations of log-concave sequences that have been transformed by convolution are log-concave. These conditions involve relations on sequences called \textit{synchronicity} and \textit{ratio-dominance}, and a characterization of some bivariate sequences as \textit{lexicographic}. We are motivated by the 25-year old conjecture that the genus distribution of every graph is log-concave. Although calculating genus distributions is NP-hard, they have been calculated explicitly for many graphs of tractable size, and the three conditions have been observed to occur in the \textit{partitioned genus distributions} of all such graphs. They are used here to prove the log-concavity of the genus distributions of graphs constructed by iterative amalgamation of double-rooted graph fragments whose genus distributions adhere to these conditions, even though it is known that the genus polynomials of some such graphs have imaginary roots. A blend of topological and combinatorial arguments demonstrates that log-concavity is preserved through the iterations.

preprint2014arXiv

Recurrence relations in counting the pattern 13-2 in flattened permutations

We prove that the generating function for the number of flattened permutations having a given number of occurrences of the pattern 13-2 is rational, by using the recurrence relations and the kernel method.

preprint2014arXiv

Surface embedding of $(n,k)$ -extendable graphs

This paper is concerned with the surface embedding of matching extendable graphs. There are two directions extending the theory of perfect matchings, that is, matching extendability and factor-criticality. In solving a problem posed by Plummer, Dean (The matching extendability of surfaces, J. Combin. Theory Ser. B 54 (1992), 133--141) established the fascinating formula for the minimum number $k= μ(Σ)$ such that every $Σ$ -embeddable graph is not $k$ -extendable. Su and Zhang, Plummer and Zha found the minimum number $n=ρ(Σ)$ such that every $Σ$ -embeddable graph is not $n$ -factor-critical. Based on the notion of $(n,k)$ -graphs which associates these two parameters, we found the formula for the minimum number $k=μ(n,Σ)$ such that every $Σ$ -embeddable graph is not an $(n,k)$ -graph. To access this two-parameter-problem, we consider its dual problem and find out $μ(n,Σ)$ conversely. The same approach works for rediscovering the formula of the number $ρ(Σ)$ .

preprint2013arXiv

Counting subwords in flattened permutations

In this paper, we consider the number of occurrences of descents, ascents, 123-subwords, 321-subwords, peaks and valleys in flattened permutations, which were recently introduced by Callan in his study of finite set partitions. For descents and ascents, we make use of the kernel method and obtain an explicit formula (in terms of Eulerian polynomials) for the distribution on $\mathcal{S}_n$ in the flattened sense. For the other four patterns in question, we develop a unified approach to obtain explicit formulas for the comparable distributions. We find that the formulas so obtained for 123- and 321-subwords can be expressed in terms of the Chebyshev polynomials of the second kind, while those for peaks and valleys are more related to the Eulerian polynomials. We also provide a bijection showing the equidistribution of descents in flattened permutations of a given length with big descents in permutations of the same length in the usual sense.

preprint2013arXiv

Recurrence relations for patterns of type $(2,1)$ in flattened permutations

We consider the problem of counting the occurrences of patterns of the form $xy-z$ within flattened permutations of a given length. Using symmetric functions, we find recurrence relations satisfied by the distributions on $\mathcal{S}_n$ for the patterns 12-3, 21-3, 23-1 and 32-1, and develop a unified approach to obtain explicit formulas. By these recurrences, we are able to determine simple closed form expressions for the number of permutations that, when flattened, avoid one of these patterns as well as expressions for the average number of occurrences. In particular, we find that the average number of 23-1 patterns and the average number of 32-1 patterns in $\text{Flatten}(π)$ , taken over all permutations $π$ of the same length, are equal, as are the number of permutations avoiding either of these patterns. We also find that the average number of 21-3 patterns in $\text{Flatten}(π)$ over all $π$ is the same as it is for 31-2 patterns.

preprint2012arXiv

On the Existence of General Factors in Regular Graphs

Let $G$ be a graph, and $H\colon V(G)\to 2^\mathbb{N}$ a set function associated with $G$ . A spanning subgraph $F$ of $G$ is called an $H$ -factor if the degree of any vertex $v$ in $F$ belongs to the set $H(v)$ . This paper contains two results on the existence of $H$ -factors in regular graphs. First, we construct an $r$ -regular graph without some given $H^*$ -factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lovász's characterization theorem on the existence of $(g, f)$ -factors, we find a sharp condition for the existence of general $H$ -factors in $\{r, r+1\}$ -graphs, in terms of the maximum and minimum of $H$ . The result reduces to Thomassen's theorem for the case that $H(v)$ consists of the same two consecutive integers for all vertices $v$ , and to Tutte's theorem if the graph is regular in addition.

preprint2012arXiv

The Real-Rootedness and Log-concavities of Coordinator Polynomials of Weyl Group Lattices

It is well-known that the coordinator polynomials of the classical root lattice of type $A_n$ and those of type $C_n$ are real-rooted. They can be obtained, either by the Aissen-Schoenberg-Whitney theorem, or from their recurrence relations. In this paper, we develop a trigonometric substitution approach which can be used to establish the real-rootedness of coordinator polynomials of type $D_n$ . We also find the coordinator polynomials of type $B_n$ are not real-rooted in general. As a conclusion, we obtain that all coordinator polynomials of Weyl group lattices are log-concave.

preprint2011arXiv

A Note on $\{k,n-k\}$ -Factors of Regular Graphs

Let $r$ be an odd integer, and $k$ an even integer. In this note, we present $r$ -regular graphs which have no $\{k,r-k\}$ -factors for all $1\le k\le {r\over2}-1$ . This gives a negative answer to a problem posed by Akbari and Kano recently.

preprint2011arXiv

Determining All Universal Tilers

A universal tiler is a convex polyhedron whose every cross-section tiles the plane. In this paper, we introduce a certain slight-rotating operation for cross-sections of pentahedra. Based on a selected initial cross-section and by applying the slight-rotating operation suitably, we prove that a convex polyhedron is a universal tiler if and only if it is a tetrahedron or a triangular prism.

preprint2011arXiv

On Cui-Kano's Characterization Problem on Graph Factors

An $H_n$ -factor of a graph $G$ is defined to be a spanning subgraph $F$ of $G$ such that each vertex has degree belonging to the set $\{1,3,5,...,2n-1,2n\}$ in $F$ . In this paper, we investigate $H_n$ -factors of graphs by using Lovász's structural descriptions to the degree prescribed subgraph problem. We find some sufficient conditions for the existence of an $H_n$ -factor of a graph. In particular, we make progress on the characterization problem for a special family of graphs proposed by Cui and Kano in 1988.

preprint2011arXiv

On Universal Tilers

A famous problem in discrete geometry is to find all monohedral plane tilers, which is still open to the best of our knowledge. This paper concerns with one of its variants that to determine all convex polyhedra whose every cross-section tiles the plane. We call such polyhedra universal tilers. We obtain that a convex polyhedron is a universal tiler only if it is a tetrahedron or a pentahedron.

preprint2011arXiv

The Limiting Distribution of the Number of Block Pairs in Type B Set Partitions

It is a classical result of Harper that the limiting distribution of the number of blocks in partitions of the set $\{1, 2,..., n\}$ is normal. In this paper, using the saddle point method we prove the normality of the limiting distribution of the number of block pairs in set partitions of type $B_n$ . Moreover, we obtain that the limiting distribution of the number of block pairs in $B_n$ -partitions without zero-block is also normal.

preprint2010arXiv

A Bijection between Atomic Partitions and Unsplitable Partitions

In the study of the algebra $\mathrm{NCSym}$ of symmetric functions in noncommutative variables, Bergeron and Zabrocki found a free generating set consisting of power sum symmetric functions indexed by atomic partitions. On the other hand, Bergeron, Reutenauer, Rosas, and Zabrocki studied another free generating set of $\mathrm{NCSym}$ consisting of monomial symmetric functions indexed by unsplitable partitions. Can and Sagan raised the question of finding a bijection between atomic partitions and unsplitable partitions. In this paper, we provide such a bijection.

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.

David G. L. Wang

Research overview

Is this your work?

26 publications

A decomposition of ballot permutations, pattern avoidance and Gessel walks

A Toeplitz property of ballot permutations and odd order permutations

Around the $q$ -binomial-Eulerian polynomials

Geometry of limits of zeros of polynomial sequences of type $(1,2)$

Non-Schur-positivity of chromatic symmetric functions

The edge metric dimension of the generalized Petersen graph $P(n,3)$ is 4

The peak and descent statistics over ballot permutations

A Tutte-type characterization for graph factors

Convolution Preserves Partial Synchronicity of Log-concave Sequences

On colored set partitions of type $B_n$

Surface embedding of non-bipartite $k$ -extendable graphs

The CLLC conjecture holds for cyclic outer permutations

The maximum number of perfect matchings of semi-regular graphs

Log-Concavity of Combinations of Sequences and Applications to Genus Distributions

Recurrence relations in counting the pattern 13-2 in flattened permutations

Surface embedding of $(n,k)$ -extendable graphs

Counting subwords in flattened permutations

Recurrence relations for patterns of type $(2,1)$ in flattened permutations

On the Existence of General Factors in Regular Graphs

The Real-Rootedness and Log-concavities of Coordinator Polynomials of Weyl Group Lattices

A Note on $\{k,n-k\}$ -Factors of Regular Graphs

Determining All Universal Tilers

On Cui-Kano's Characterization Problem on Graph Factors

On Universal Tilers

The Limiting Distribution of the Number of Block Pairs in Type B Set Partitions

A Bijection between Atomic Partitions and Unsplitable Partitions

See the researcher in context

Building this map preview

David G. L. Wang

Research overview

Is this your work?

26 publications

A decomposition of ballot permutations, pattern avoidance and Gessel walks

A Toeplitz property of ballot permutations and odd order permutations

Around the qqq-binomial-Eulerian polynomials

Geometry of limits of zeros of polynomial sequences of type (1,2)(1,2)(1,2)

Non-Schur-positivity of chromatic symmetric functions

The edge metric dimension of the generalized Petersen graph P(n,3)P(n,3)P(n,3) is 4

The peak and descent statistics over ballot permutations

A Tutte-type characterization for graph factors

Convolution Preserves Partial Synchronicity of Log-concave Sequences

On colored set partitions of type BnB_nBn​

Surface embedding of non-bipartite kkk-extendable graphs

The CLLC conjecture holds for cyclic outer permutations

The maximum number of perfect matchings of semi-regular graphs

Log-Concavity of Combinations of Sequences and Applications to Genus Distributions

Recurrence relations in counting the pattern 13-2 in flattened permutations

Surface embedding of (n,k)(n,k)(n,k)-extendable graphs

Counting subwords in flattened permutations

Recurrence relations for patterns of type (2,1)(2,1)(2,1) in flattened permutations

On the Existence of General Factors in Regular Graphs

The Real-Rootedness and Log-concavities of Coordinator Polynomials of Weyl Group Lattices

A Note on {k,n−k}\{k,n-k\}{k,n−k}-Factors of Regular Graphs

Determining All Universal Tilers

On Cui-Kano's Characterization Problem on Graph Factors

On Universal Tilers

The Limiting Distribution of the Number of Block Pairs in Type B Set Partitions

A Bijection between Atomic Partitions and Unsplitable Partitions

See the researcher in context

Building this map preview

Around the $q$ -binomial-Eulerian polynomials

Geometry of limits of zeros of polynomial sequences of type $(1,2)$

The edge metric dimension of the generalized Petersen graph $P(n,3)$ is 4

On colored set partitions of type $B_n$

Surface embedding of non-bipartite $k$ -extendable graphs

Surface embedding of $(n,k)$ -extendable graphs

Recurrence relations for patterns of type $(2,1)$ in flattened permutations

A Note on $\{k,n-k\}$ -Factors of Regular Graphs