Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract For a finite set of S points in the plane and a graph with vertices on S, consider the disks with diameters induced by the edges. We show that for any odd set S, there exists a Hamiltonian cycle for which these disks share a point, and for an even set S, there exists a Hamiltonian path with the same property. We discuss high-dimensional versions of these theorems and their relation to other results in discrete geometry. PubDate: 2021-10-11
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We introduce a quasisymmetric class function associated with a group acting on a double poset or on a directed graph. The latter is a generalization of the chromatic quasisymmetric function of a digraph introduced by Ellzey, while the former is a generalization of a quasisymmetric function introduced by Grinberg. We prove representation-theoretic analogues of classical and recent results, including F-positivity, and combinatorial reciprocity theorems. We deduce results for orbital quasisymmetric functions, and study a generalization of the notion of strongly flawless sequences. PubDate: 2021-10-08
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract For each integer partition \(\mathbf {q}\) with d parts, we denote by \(\Delta _{(1,\mathbf {q})}\) the lattice simplex obtained as the convex hull in \(\mathbb {R}^d\) of the standard basis vectors along with the vector \(-\mathbf {q}\) . For \(\mathbf {q}\) with two distinct parts such that \(\Delta _{(1,\mathbf {q})}\) is reflexive and has the integer decomposition property, we establish a characterization of the lattice points contained in \(\Delta _{(1,\mathbf {q})}\) . We then construct a Gröbner basis with a squarefree initial ideal of the toric ideal defined by these simplices. This establishes the existence of a regular unimodular triangulation for reflexive 2-supported \(\Delta _{(1,\mathbf {q})}\) having the integer decomposition property. As a corollary, we obtain a new proof that these simplices have unimodal Ehrhart \(h^*\) -vectors. PubDate: 2021-09-28
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract If every perfect matching of a graph G extends to a Hamiltonian cycle, we shall say that G has the PMH-property—a concept first studied in the 1970s by Las Vergnas and Häggkvist. A pairing of a graph G is a perfect matching of the complete graph having the same vertex set as G. A somewhat stronger property than the PMH-property is the following. A graph G has the PH-property if every pairing of G can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from G. The name for the latter property was coined in 2015 by Alahmadi et al.; however, this was not the first time this property was studied. In 2007, Fink proved that every n-dimensional hypercube, for \(n\ge 2\) , has the PH-property. After characterising all the cubic graphs having the PH-property, Alahmadi et al. attempt to characterise all 4-regular graphs having the same property by posing the following problem: for which values of p and q does the Cartesian product \(C_p\square C_q\) of two cycles on p and q vertices have the PH-property' We here show that this only happens when both p and q are equal to four, namely for \(C_{4}\square C_{4}\) , the 4-dimensional hypercube. For all other values, we show that \(C_{p}\square C_{q}\) does not even admit the PMH-property. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we study concave compositions, an extension of partitions that were considered by Andrews, Rhoades, and Zwegers. They presented several open problems regarding the statistical structure of concave compositions including the distribution of the perimeter and tilt, the number of summands, and the shape of the graph of a typical concave composition. We present solutions to these problems by applying Fristedt’s conditioning device on the uniform measure. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study f-vectors, which are the maximal degree vectors of F-polynomials in cluster algebra theory. For a cluster algebra of finite type, we find that positive f-vectors correspond with d-vectors, which are exponent vectors of denominators of cluster variables. Furthermore, using this correspondence and properties of d-vectors, we prove that cluster variables in a cluster are uniquely determined by their f-vectors when the cluster algebra is of finite type or rank 2. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study the nature of the generating series of some models of walks with small steps in the three quarter plane. More precisely, we restrict ourselves to the situation where the group is infinite, the kernel has genus one, and the step set is diagonally symmetric (i.e., with no steps in anti-diagonal directions). In that situation, after a transformation of the plane, we derive a quadrant-like functional equation. Among the four models of walks, we obtain, using difference Galois theory, that three of them have a differentially transcendental generating series, and one has a differentially algebraic generating series. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In their study of the equivariant K-theory of the generalized flag varieties G/P, where G is a complex semisimple Lie group, and P is a parabolic subgroup of G, Lenart and Postnikov introduced a combinatorial tool, called the alcove path model. It provides a model for the highest weight crystals with dominant integral highest weights, generalizing the model by semistandard Young tableaux. In this paper, we prove a simple and explicit formula describing the crystal isomorphism between the alcove path model and the Gelfand–Tsetlin pattern model for type A. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract For positive integers \(L \ge 3\) and s, Berkovich and Uncu (Ann Comb 23:263–284, 2019) conjectured an inequality between the sizes of two closely related sets of partitions whose parts lie in the interval \(\{s, \ldots , L+s\}\) . Further restrictions are placed on the sets by specifying impermissible parts as well as a minimum part. The authors proved their conjecture for the cases \(s=1\) and \(s=2\) . In the present article, we prove their conjecture for general s by proving a stronger theorem. We also prove other related conjectures found in the same paper. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Partitions, the partition function p(n), and the hook lengths of their Ferrers–Young diagrams are important objects in combinatorics, number theory, and representation theory. For positive integers n and t, we study \(p_t^\mathrm{e}(n)\) (resp. \(p_t^\mathrm{o}(n)\) ), the number of partitions of n with an even (resp. odd) number of t-hooks. We study the limiting behavior of the ratio \(p_t^\mathrm{e}(n)/p(n)\) , which also gives \(p_t^\mathrm{o}(n)/p(n)\) , since \(p_t^\mathrm{e}(n) + p_t^\mathrm{o}(n) = p(n)\) . For even t, we show that $$\begin{aligned} \lim \limits _{n \rightarrow \infty } \dfrac{p_t^\mathrm{e}(n)}{p(n)} = \dfrac{1}{2}, \end{aligned}$$ and for odd t, we establish the non-uniform distribution $$\begin{aligned} \lim \limits _{n \rightarrow \infty } \dfrac{p^\mathrm{e}_t(n)}{p(n)} = {\left\{ \begin{array}{ll} \dfrac{1}{2} + \dfrac{1}{2^{(t+1)/2}} &{} \text {if } 2 \mid n, \\ \\ \dfrac{1}{2} - \dfrac{1}{2^{(t+1)/2}} &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$ Using the Rademacher circle method, we find an exact formula for \(p_t^\mathrm{e}(n)\) and \(p_t^\mathrm{o}(n)\) , and this exact formula yields these distribution properties for large n. We also show that for sufficiently large n, the sign of \(p_t^\mathrm{e}(n) - p_t^\mathrm{o}(n)\) is periodic. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We give a commutative algebra viewpoint on Andrews recursive formula for the partitions appearing in Gordon’s identities, which are a generalization of Rogers–Ramanujan identities. Using this approach and differential ideals, we conjecture a family of partition identities which extend Gordon’s identities. This family is indexed by \(r\ge 2.\) We prove the conjecture for \(r=2\) and \(r=3.\) PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Motivated by the notion of chip-firing on the dual graph of a planar graph, we consider ‘integral flow chip-firing’ on an arbitrary graph G. The chip-firing rule is governed by \({\mathcal {L}}^*(G)\) , the dual Laplacian of G determined by choosing a basis for the lattice of integral flows on G. We show that any graph admits such a basis so that \({\mathcal {L}}^*(G)\) is an M-matrix, leading to a firing rule on these basis elements that is avalanche finite. This follows from a more general result on bases of integral lattices that may be of independent interest. Our results provide a notion of z-superstable flow configurations that are in bijection with the set of spanning trees of G. We show that for planar graphs, as well as for the graphs \(K_5\) and \(K_{3,3}\) , one can find such a flow M-basis that consists of cycles of the underlying graph. We consider the question for arbitrary graphs and address some open questions. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let \({\mathfrak {S}}_{[i,j]}\) be the subgroup of the symmetric group \({\mathfrak {S}}_n\) generated by adjacent transpositions \((i,i+1), \dotsc , (j-1,j)\) , assuming \(1 \le i < j \le n\) . We give a combinatorial rule for evaluating induced sign characters of the type A Hecke algebra \(H_n(q)\) at all elements of the form \(\sum _{w \in {\mathfrak {S}}_{[i,j]}} T_w\) and at all products of such elements. This includes evaluation at some elements \(C'_w(q)\) of the Kazhdan–Lusztig basis. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a bipartite graph with parts A and B having maximum degrees at most \(\Delta _A\) and \(\Delta _B\) , respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size \(k_A\) or \(k_B\) , respectively. We prove some general sufficient conditions in terms of \(\Delta _A\) , \(\Delta _B\) , \(k_A\) , \(k_B\) to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list. These are asymptotically nearly sharp in the very asymmetric cases. We establish one sufficient condition in particular, where \(\Delta _A=\Delta _B=\Delta \) , \(k_A=\log \Delta \) and \(k_B=(1+o(1))\Delta /\log \Delta \) as \(\Delta \rightarrow \infty \) . This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author. We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems. We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following. In the setup above, we conjecture that a proper list colouring is always guaranteed if \(k_A \ge \Delta _A^\varepsilon \) and \(k_B \ge \Delta _B^\varepsilon \) for any \(\varepsilon >0\) provided \(\Delta _A\) and \(\Delta _B\) are large enough; if \(k_A \ge C \log \Delta _B\) and \(k_B \ge C \log \Delta _A\) for some absolute constant \(C>1\) ; or if \(\Delta _A=\Delta _B = \Delta \) and \( k_B \ge C (\Delta /\log \Delta )^{1/k_A}\log \Delta \) for some absolute constant \(C>0\) . These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible. Our general sufficient conditions provide partial progress towards these conjectures. PubDate: 2021-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The degree of symmetry of a combinatorial object, such as a lattice path, is a measure of how symmetric the object is. It typically ranges from zero, if the object is completely asymmetric, to its size, if it is completely symmetric. We study the behavior of this statistic on Dyck paths and grand Dyck paths, with symmetry described by reflection along a vertical line through their midpoint; partitions, with symmetry given by conjugation; and certain compositions interpreted as bargraphs. We find expressions for the generating functions for these objects with respect to their degree of symmetry, and their semilength or semiperimeter, deducing in most cases that, asymptotically, the degree of symmetry has a Rayleigh or half-normal limiting distribution. The resulting generating functions are often algebraic, with the notable exception of Dyck paths, for which we conjecture that it is D-finite (but not algebraic), based on a functional equation that we obtain using bijections to walks in the plane. PubDate: 2021-08-24
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Recently, the study of patterns in inversion sequences was initiated by Corteel–Martinez–Savage–Weselcouch and Mansour–Shattuck independently. Motivated by their works and a double Eulerian equidistribution due to Foata (1977), we investigate several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by Catalan, Large Schröder, Baxter and Euler numbers. One of the two highlights of our results is a fascinating bijection between 000-avoiding inversion sequences and Simsun permutations, which together with Foata’s V- and S-codes, provide a proof of a restricted double Eulerian equidistribution. The other one is a refinement of a conjecture due to Martinez and Savage that the cardinality of \({\mathbf{I}}_n(\ge ,\ge ,>)\) is the n-th Baxter number, which is proved via the so-called obstinate kernel method developed by Bousquet-Mélou. PubDate: 2021-08-23
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study a number of combinatorial and algebraic structures arising from walks on the two-dimensional integer lattice. To a given step set \(X\subseteq \mathbb Z^2\) , there are two naturally associated monoids: \(\mathscr {F}_X\) , the monoid of all X-walks/paths; and \(\mathscr {A}_X\) , the monoid of all endpoints of X-walks starting from the origin O. For each \({A\in \mathscr {A}_X}\) , write \(\pi _X(A)\) for the number of X-walks from O to A. Calculating the numbers \(\pi _X(A)\) is a classical problem, leading to Fibonacci, Catalan, Motzkin, Delannoy and Schröder numbers, among many other well-studied sequences and arrays. Our main results give relationships between finiteness properties of the numbers \(\pi _X(A)\) , geometrical properties of the step set X, algebraic properties of the monoid \(\mathscr {A}_X\) , and combinatorial properties of a certain bi-labelled digraph naturally associated to X. There is an intriguing divergence between the cases of finite and infinite step sets, and some constructions rely on highly non-trivial properties of real numbers. We also consider the case of walks constrained to stay within a given region of the plane. Several examples are considered throughout to highlight the sometimes-subtle nature of the theoretical results. PubDate: 2021-08-18
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Pairs of graded graphs, together with the Fomin property of graded graph duality, are rich combinatorial structures providing among other a framework for enumeration. The prototypical example is the one of the Young graded graph of integer partitions, allowing us to connect number of standard Young tableaux and numbers of permutations. Here, we use operads, algebraic devices abstracting the notion of composition of combinatorial objects, to build pairs of graded graphs. For this, we first construct a pair of graded graphs where vertices are syntax trees, the elements of free nonsymmetric operads. This pair of graphs is dual for a new notion of duality called \(\phi \) -diagonal duality, similar to the ones introduced by Fomin. We also provide a general way to build pairs of graded graphs from operads, wherein underlying posets are analogous to the Young lattice. Some examples of operads leading to new pairs of graded graphs involving integer compositions, Motzkin paths, and m-trees are considered. PubDate: 2021-06-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Using the theory of Properly Embedded Graphs developed in an earlier work we define an involutory duality on the set of labeled non-crossing trees that lifts the obvious duality in the set of unlabeled non-crossing trees. The set of non-crossing trees is a free ternary magma with one generator and this duality is an instance of a duality that is defined in any such magma. Any two free ternary magmas with one generator are isomorphic via a unique isomorphism that we call the structural bijection. Besides the set of non-crossing trees we also consider as free ternary magmas with one generator the set of ternary trees, the set of quadrangular dissections, and the set of flagged Perfectly Chain Decomposed Ditrees, and we give topological and/or combinatorial interpretations of the structural bijections between them. In particular the bijection from the set of quadrangular dissections to the set of non-crossing trees seems to be new. Further we give explicit formulas for the number of self-dual labeled and unlabeled non-crossing trees and the set of quadrangular dissections up to rotations and up to rotations and reflections. PubDate: 2021-06-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Conway and Gordon proved that for every spatial complete graph on six vertices, the sum of the linking numbers over all of the constituent two-component links is odd, and Kazakov and Korablev proved that for every spatial complete graph with arbitrary number of vertices greater than six, the sum of the linking numbers over all of the constituent two-component Hamiltonian links is even. In this paper, we show that for every spatial complete graph whose number of vertices is greater than six, the sum of the square of the linking numbers over all of the two-component Hamiltonian links is determined explicitly in terms of the sum over all of the triangle–triangle constituent links. As an application, we show that if the number of vertices is sufficiently large then every spatial complete graph contains a two-component Hamiltonian link whose absolute value of the linking number is arbitrary large. Some applications to rectilinear spatial complete graphs are also given. PubDate: 2021-06-01
Hybrid journal (It can contain Open Access articles)
[2654 journals]
