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 prove that the acyclic reorientation poset of a directed acyclic graph D is a lattice if and only if the transitive reduction of any induced subgraph of D is a forest. We then show that the acyclic reorientation lattice is always congruence normal, semidistributive (thus congruence uniform) if and only if D is filled, and distributive if and only if D is a forest. When the acyclic reorientation lattice is semidistributive, we introduce the ropes of D that encode the join irreducible acyclic reorientations and exploit this combinatorial model in three directions. First, we describe the canonical join and meet representations of acyclic reorientations in terms of non-crossing rope diagrams. Second, we describe the congruences of the acyclic reorientation lattice in terms of lower ideals of a natural subrope order. Third, we use Minkowski sums of shard polytopes of ropes to construct a quotientope for any congruence of the acyclic reorientation lattice. PubDate: 2024-08-09 DOI: 10.1007/s00026-024-00697-z
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, Blecher and Knopfmacher applied the notion of fixed points to integer partitions. This has already been generalized and refined in various ways such as h-fixed points for an integer parameter h by Hopkins and Sellers. Here, we consider the sequence of first column hook lengths in the Young diagram of a partition and corresponding fixed hooks. We enumerate these, using both generating function and combinatorial proofs, and find that they match occurrences of part sizes equal to their multiplicity. We establish connections to work of Andrews and Merca on truncations of the pentagonal number theorem and classes of partitions partially characterized by certain minimal excluded parts (mex). PubDate: 2024-08-09 DOI: 10.1007/s00026-024-00714-1
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 Grothendieck polynomials \(\mathfrak {G}_w\) of permutations \(w\in S_n\) were introduced by Lascoux and Schützenberger (C R Acad Sci Paris Sér I Math 295(11):629–633, 1982) as a set of distinguished representatives for the K-theoretic classes of Schubert cycles in the K-theory of the flag variety of \(\mathbb {C}^n\) . We conjecture that the exponents of nonzero terms of the Grothendieck polynomial \(\mathfrak {G}_w\) form a poset under componentwise comparison that is isomorphic to an induced subposet of \(\mathbb {Z}^n\) . When \(w\in S_n\) avoids a certain set of patterns, we conjecturally connect the coefficients of \(\mathfrak {G}_w\) with the Möbius function values of the aforementioned poset with \(\hat{0}\) appended. We prove special cases of our conjectures for Grassmannian and fireworks permutations PubDate: 2024-08-08 DOI: 10.1007/s00026-024-00712-3
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 Euler’s partition theorem states that every integer has as many partitions into odd parts as into distinct parts. In this work, we reveal a new result behind this statement. On one hand, we study the partitions into odd parts according to the residue modulo 4 of the size of those parts occurring an odd number of times. On the other hand, we discuss the partitions into distinct parts with respect to the position of odd parts in the sequence. Some other statistics are also considered together, including the length, alternating sum and minimal odd excludant. PubDate: 2024-08-08 DOI: 10.1007/s00026-024-00713-2
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 discuss sequential stub matching for directed graphs and show that this process can be used to sample simple digraphs with asymptotically equal probability. The process starts with an empty edge set and repeatedly adds edges to it with a certain state-dependent bias until the desired degree sequence is fulfilled, whilst avoiding placing a double edge or self-loop. We show that uniform sampling is achieved in the sparse regime when the maximum degree \(d_\text {max}\) is asymptotically dominated by \(m^{1/4}\) , where m is the number of edges. The proof is based on deriving various combinatorial estimates related to the number of digraphs with a given degree sequence and controlling concentration of these estimates in large digraphs. This suggests that sequential stub matching can be viewed as a practical algorithm for almost uniform sampling of digraphs. We show that this algorithm can be implemented to feature a linear expected runtime O(m). PubDate: 2024-08-07 DOI: 10.1007/s00026-024-00715-0
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 A graph is cubical if it is a subgraph of a hypercube. For a cubical graph H and a hypercube \(Q_n\) , \(\textrm{ex}(Q_n, H)\) is the largest number of edges in an H-free subgraph of \(Q_n\) . If \(\textrm{ex}(Q_n, H)\) is at least a positive proportion of the number of edges in \(Q_n\) , then H is said to have positive Turán density in the hypercube; otherwise it has zero Turán density. Determining \(\textrm{ex}(Q_n, H)\) and even identifying whether H has positive or zero Turán density remains a widely open question for general H. In this paper we focus on layered graphs, i.e., graphs that are contained in an edge layer of some hypercube. Graphs H that are not layered have positive Turán density because one can form an H-free subgraph of \(Q_n\) consisting of edges of every other layer. For example, a 4-cycle is not layered and has positive Turán density. However, in general, it is not obvious what properties layered graphs have. We give a characterization of layered graphs in terms of edge-colorings. We show that most non-trivial subdivisions have zero Turán density, extending known results on zero Turán density of even cycles of length at least 12 and of length 8. However, we prove that there are cubical graphs of girth 8 that are not layered and thus having positive Turán density. The cycle of length 10 remains the only cycle for which it is not known whether its Turán density is positive or not. We prove that \(\textrm{ex}(Q_n, C_{10})= \Omega (n2^n/ \log ^a n)\) , for a constant a, showing that the extremal number for a 10-cycle behaves differently from any other cycle of zero Turán density. PubDate: 2024-07-29 DOI: 10.1007/s00026-024-00705-2
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 call a pair of vertex-disjoint, induced subtrees of a rooted tree twins if they have the same counts of vertices by out-degrees. The likely maximum size of twins in a uniformly random, rooted Cayley tree of size \(n\rightarrow \infty \) is studied. It is shown that the expected number of twins of size \((2+\delta )\sqrt{\log n\cdot \log \log n}\) approaches zero, while the expected number of twins of size \((2-\delta )\sqrt{\log n\cdot \log \log n}\) approaches infinity. PubDate: 2024-07-27 DOI: 10.1007/s00026-024-00711-4
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 derived graph of a voltage graph consisting of a single vertex and two loops of different voltages is a circulant graph with two generators. We characterize the automorphism groups of connected, two-generator circulant graphs, and give their determining and distinguishing number, and when relevant, their cost of 2-distinguishing. We do the same for the subdivisions of connected, two-generator circulant graphs obtained by replacing one loop in the voltage graph with a directed cycle. PubDate: 2024-07-26 DOI: 10.1007/s00026-024-00709-y
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 investigate a permutation statistic that was independently introduced by Romik (Funct Anal Appl 39(2):52–155, 2005). This statistic counts the number of bumps that occur during the execution of the Robinson–Schensted procedure when applied to a given permutation. We provide several interpretations of this bump statistic that include the tableaux shape and also as an extremal problem concerning permutations and increasing subsequences. Several aspects of this bump statistic are investigated from both structural and enumerative viewpoints. PubDate: 2024-07-08 DOI: 10.1007/s00026-024-00708-z
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 calculate the volume of the tropical Prym variety of a harmonic double cover of metric graphs having non-trivial dilation. We show that the tropical Prym variety behaves discontinuously under deformations of the double cover that change the number of connected components of the dilation subgraph. PubDate: 2024-07-08 DOI: 10.1007/s00026-024-00707-0
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 give a combinatorial proof of a positivity result of Chern related to Andrews’s \(\mathcal{E}\mathcal{O}^*\) -type partitions. This combinatorial proof comes after reframing Chern’s result in terms of copartitions.Using this new perspective, we also reprove an overpartition result of Chern by showing that it comes essentially “for free” from our combinatorial proof and some basic properties of copartitions. Finally, the application of copartitions leads us to more general positivity conjectures for families of both infinite and finite products, with a proof in one special case. PubDate: 2024-07-01 DOI: 10.1007/s00026-024-00704-3
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 two tableaux assigned by the Robinson–Schensted correspondence are equal if and only if the input permutation is an involution, so the RS algorithm restricts to a bijection between involutions in the symmetric group and standard tableaux. Beissinger found a concise way of formulating this restricted map, which involves adding an extra cell at the end of a row after a Schensted insertion process. We show that by changing this algorithm slightly to add cells at the end of columns rather than rows, one obtains a different bijection from involutions to standard tableaux. Both maps have an interesting connection to representation theory. Specifically, our insertion algorithms classify the molecules (and conjecturally the cells) in the pair of W-graphs associated with the unique equivalence class of perfect models for a generic symmetric group. PubDate: 2024-06-28 DOI: 10.1007/s00026-024-00701-6
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 with initial repetitions were introduced by George Andrews. We consider a subclass of these partitions and find Legendre theorems associated with their respective partition functions. The results in turn provide partition-theoretic interpretations of some Rogers–Ramanujan identities due to Lucy J. Slater. PubDate: 2024-06-25 DOI: 10.1007/s00026-024-00706-1
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 generalize valuations on polyhedral cones to valuations on (plane) fans. For fans induced by hyperplane arrangements, we show a correspondence between rotation-invariant valuations and deletion– restriction invariants. In particular, we define a characteristic polynomial for fans in terms of spherical intrinsic volumes and show that it coincides with the usual characteristic polynomial in the case of hyperplane arrangements. This gives a simple deletion–restriction proof of a result of Klivans–Swartz. The metric projection of a cone is a piecewise-linear map, whose underlying fan prompts a generalization of spherical intrinsic volumes to indicator functions. We show that these intrinsic indicators yield valuations that separate polyhedral cones. Applied to hyperplane arrangements, this generalizes a result of Kabluchko on projection volumes. PubDate: 2024-06-24 DOI: 10.1007/s00026-024-00699-x
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 graph X with a Hamilton cycle C, the compression factor \(\kappa (X,C)\) of C is the order of the largest cyclic subgroup of \({\textrm{Aut}}\,(C)\cap {\textrm{Aut}}\,(X)\) , and the Hamilton compression \(\kappa (X)\) of X is the maximum of \(\kappa (X,C)\) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor et al. (Ann Comb, arXiv:2205.08126v1, https://doi.org/10.1007/s00026-023-00674-y, 2023) whether for every positive integer k, there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products \(\mathbb {Z}_p\rtimes \mathbb {Z}_k\) where p is a prime and \(k \ge 2\) a divisor of \(p-1\) . Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given. PubDate: 2024-06-20 DOI: 10.1007/s00026-024-00703-4
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 B-polynomial and quasisymmetric B-function, introduced by Awan and Bernardi, extends the widely studied Tutte polynomial and Tutte symmetric function to digraphs. In this article, we address one of the fundamental questions concerning these digraph invariants, which is, the determination of the classes of digraphs uniquely characterized by them. We solve an open question originally posed by Awan and Bernardi, regarding the identification of digraphs that result from replacing every edge of a graph with a pair of opposite arcs. Further, we address the more challenging problem of reconstructing digraphs using their quasisymmetric functions. In particular, we show that the quasisymmetric B-function reconstructs partially symmetric orientations of proper caterpillars. As a consequence, we establish that all orientations of paths and asymmetric proper caterpillars can be reconstructed from their quasisymmetric B-functions. These results enhance the pool of oriented trees distinguishable through quasisymmetric functions. PubDate: 2024-06-18 DOI: 10.1007/s00026-024-00702-5
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 A permutation statistic \({{\,\textrm{st}\,}}\) is said to be shuffle-compatible if the distribution of \({{\,\textrm{st}\,}}\) over the set of shuffles of two disjoint permutations \(\pi \) and \(\sigma \) depends only on \({{\,\textrm{st}\,}}\pi \) , \({{\,\textrm{st}\,}}\sigma \) , and the lengths of \(\pi \) and \(\sigma \) . Shuffle-compatibility is implicit in Stanley’s early work on P-partitions, and was first explicitly studied by Gessel and Zhuang, who developed an algebraic framework for shuffle-compatibility centered around their notion of the shuffle algebra of a shuffle-compatible statistic. For a family of statistics called descent statistics, these shuffle algebras are isomorphic to quotients of the algebra of quasisymmetric functions. Recently, Domagalski, Liang, Minnich, Sagan, Schmidt, and Sietsema defined a version of shuffle-compatibility for statistics on cyclic permutations, and studied cyclic shuffle-compatibility through purely combinatorial means. In this paper, we define the cyclic shuffle algebra of a cyclic shuffle-compatible statistic, and develop an algebraic framework for cyclic shuffle-compatibility in which the role of quasisymmetric functions is replaced by the cyclic quasisymmetric functions recently introduced by Adin, Gessel, Reiner, and Roichman. We use our theory to provide explicit descriptions for the cyclic shuffle algebras of various cyclic permutation statistics, which in turn gives algebraic proofs for their cyclic shuffle-compatibility. PubDate: 2024-06-01 DOI: 10.1007/s00026-023-00669-9
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 2022, Defant and Kravitz introduced extended promotion (denoted \( \partial \) ), a map that acts on the set of labelings of a poset. Extended promotion is a generalization of Schützenberger’s promotion operator, a well-studied map that permutes the set of linear extensions of a poset. It is known that if L is a labeling of an n-element poset P, then \( \partial ^{n-1}(L) \) is a linear extension. This allows us to regard \( \partial \) as a sorting operator on the set of all labelings of P, where we think of the linear extensions of P as the labelings which have been sorted. The labelings requiring \( n-1 \) applications of \( \partial \) to be sorted are called tangled; the labelings requiring \( n-2 \) applications are called quasi-tangled. We count the quasi-tangled labelings of a relatively large class of posets called inflated rooted trees with deflated leaves. Given an n-element poset with a unique minimal element with the property that the minimal element has exactly one parent, it follows from the aforementioned enumeration that this poset has \( 2(n-1)!-(n-2)! \) quasi-tangled labelings. Using similar methods, we outline an algorithmic approach to enumerating the labelings requiring \( n-k-1 \) applications to be sorted for any fixed \( k\in \{1,\ldots ,n-2\} \) . We also make partial progress towards proving a conjecture of Defant and Kravitz on the maximum possible number of tangled labelings of an n-element poset. PubDate: 2024-06-01 DOI: 10.1007/s00026-023-00646-2
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 say that a Hamilton cycle \(C=(x_1,\ldots ,x_n)\) in a graph G is k-symmetric, if the mapping \(x_i\mapsto x_{i+n/k}\) for all \(i=1,\ldots ,n\) , where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices \(x_1,\ldots ,x_n\) equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a \(360^\circ /k\) wedge of the drawing. The maximum k for which there exists a k-symmetric Hamilton cycle in G is referred to as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases, we determine their Hamilton compression exactly, and in other cases, we provide close lower and upper bounds. The constructed cycles have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced. PubDate: 2024-06-01 DOI: 10.1007/s00026-023-00674-y
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 As a spin analog of the plethystic Murnaghan–Nakayama rule for Schur functions, the plethystic Murnaghan–Nakayama rule for Schur Q-functions is established with the help of the vertex operator realization. This generalizes both the Murnaghan–Nakayama rule and the Pieri rule for Schur Q-functions. A plethystic Murnaghan–Nakayama rule for Hall–Littlewood functions is also investigated. PubDate: 2024-06-01 DOI: 10.1007/s00026-023-00686-8
Hybrid journal (It can contain Open Access articles)
[2468 journals]
