Subjects -> MATHEMATICS (Total: 1013 journals)     - APPLIED MATHEMATICS (92 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (714 journals)    - MATHEMATICS (GENERAL) (45 journals)    - NUMERICAL ANALYSIS (26 journals)    - PROBABILITIES AND MATH STATISTICS (113 journals) MATHEMATICS (714 journals)                  1 2 3 4 | Last

1 2 3 4 | Last

Similar Journals
 Annals of CombinatoricsJournal Prestige (SJR): 0.932 Citation Impact (citeScore): 1Number of Followers: 3      Hybrid journal (It can contain Open Access articles) ISSN (Print) 0219-3094 - ISSN (Online) 0218-0006 Published by Springer-Verlag  [2467 journals]
• Diameter Estimates for Graph Associahedra

Abstract: Abstract Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of the search trees on G, defined recursively by a root r together with search trees on each of the connected components of $$G-r$$ . In particular, the 1-skeleton of the corresponding graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. We give a tight bound of $$\Theta (m)$$ on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. We also prove that the maximum diameter of associahedra of graphs of pathwidth two is $$\Theta (n\log n)$$ . Finally, we give the exact diameter of the associahedra of complete split graphs and of unbalanced complete bipartite graphs.
PubDate: 2022-12-01

• File Placements, Fractional Matchings, and Normal Ordering

Abstract: Abstract In this paper, the bijection between k-rook placements on a Ferrers board and k-matchings in the associated bipartite graph is extended to a bijection between k-file placements and certain fractional matchings. Using the latter bijection, a new interpretation is given for the normal ordering coefficients in the shift algebra. Several further results concerning normal ordering in the shift algebra are derived.
PubDate: 2022-12-01

• Construction of Evidently Positive Series and an Alternative Construction
for A Family of Partition Generating Functions Due to Kanade and Russell

Abstract: Abstract We give an alternative construction for a family of partition generating functions due to Kanade and Russell. In our alternative construction, we use ordinary partitions instead of jagged partitions. We also present new generating functions which are evidently positive series for partitions due to Kanade and Russell. To obtain those generating functions, we first construct an evidently positive series for a key infinite product. In that construction, a series of combinatorial moves is used to decompose an arbitrary partition into a base partition together with some auxiliary partitions that bijectively record the moves.
PubDate: 2022-12-01

• Pairwise Compatibility for 2-Simple Minded Collections II: Preprojective
Algebras and Semibrick Pairs of Full Rank

Abstract: Abstract Let $$\Lambda$$ be a finite-dimensional associative algebra over a field. A semibrick pair is a finite set of $$\Lambda$$ -modules for which certain Hom- and Ext-sets vanish. A semibrick pair is completable if it can be enlarged so that a generating condition is satisfied. We prove that if $$\Lambda$$ is $$\tau$$ -tilting finite with at most three simple modules, then the completability of a semibrick pair can be characterized using conditions on pairs of modules. We then use the weak order to construct a combinatorial model for the semibrick pairs of preprojective algebras of type $$A_n$$ . From this model, we deduce that any semibrick pair of size n satisfies the generating condition, and that the dimension vectors of any semibrick pair form a subset of the column vectors of some c-matrix. Finally, we show that no “pairwise” criteria for completability exists for preprojective algebras of Dynkin diagrams with more than three vertices.
PubDate: 2022-12-01

• Lozenge Tilings of a Hexagon with a Horizontal Intrusion

Abstract: Abstract Motivated by a conjecture posed by Fulmek and Krattenthaler, we provide product formulas for the number of lozenge tilings of a semiregular hexagon containing a horizontal intrusion. As a direct corollary, we obtain a product formula for the number of boxed plane partitions with a certain restriction. We also investigate the asymptotic behavior of the ratio between the number of lozenge tilings of a semiregular hexagon containing a horizontal intrusion and that of a semiregular hexagon without an intrusion.
PubDate: 2022-12-01

• Growing Random Uniform d-ary Trees

Abstract: Abstract Let $${{\mathcal {T}}}_{d}(n)$$ be the set of d-ary rooted trees with n internal nodes. We give a method to construct a sequence $$( \textbf{t}_{n},n\ge 0)$$ , where, for any $$n\ge 1$$ , $$\textbf{t}_{n}$$ has the uniform distribution in $${{\mathcal {T}}}_{d}(n)$$ , and $$\textbf{t}_{n}$$ is constructed from $$\textbf{t}_{n-1}$$ by the addition of a new node, and a rearrangement of the structure of $$\textbf{t}_{n-1}$$ . This method is inspired by Rémy’s algorithm which does this job in the binary case, but it is different from it. This provides a method for the random generation of a uniform d-ary tree in $${{\mathcal {T}}}_{d}(n)$$ with a cost linear in n.
PubDate: 2022-11-29

• Large $$p$$ -Core $$p'$$ -Partitions and Walks on the Additive Residue
Graph

Abstract: Abstract This paper investigates partitions which have neither parts nor hook lengths divisible by $$p$$ , referred to as $$p$$ -core $$p'$$ -partitions. We show that the largest $$p$$ -core $$p'$$ -partition corresponds to the longest walk on a graph with vertices $$\{0, 1, \ldots , p-1\}$$ and labelled edges defined via addition modulo $$p$$ . We also exhibit an explicit family of large $$p$$ -core $$p'$$ -partitions, giving a lower bound on the size of the largest such partition which is of the same degree as the upper bound found by McSpirit and Ono.
PubDate: 2022-11-24

• The Limit Theorem with Respect to the Matrices on Non-backtracking
Paths of a Graph

Abstract: Abstract We give a limit theorem with respect to the matrices related to non-backtracking paths of a regular graph. The limit obtained closely resembles the kth moments of the arcsine law. Furthermore, we obtain the asymptotics of the averages of the $$p^m$$ th Fourier coefficients of the cusp forms related to the Ramanujan graphs defined by A. Lubotzky, R. Phillips and P. Sarnak.
PubDate: 2022-11-15

• Upper Bounds on the Smallest Positive Eigenvalue of Trees

Abstract: Abstract In this article, we undertake the problem of finding the first four trees on a fixed number of vertices with the maximum smallest positive eigenvalue. Let $${\mathcal {T}}_{n,d}$$ denote the class of trees on n vertices with diameter d. First, we obtain the bounds on the smallest positive eigenvalue of trees in $${\mathcal {T}}_{n,d}$$ for $$d =2,3,4$$ and then upper bounds on the smallest positive eigenvalue of trees are obtained in general class of all trees on n vertices. Finally, the first four trees on n vertices with the maximum, second maximum, third maximum and fourth maximum smallest positive eigenvalue are characterized.
PubDate: 2022-11-09

• On Two-Sided Cayley Graphs of Semigroups and Groups

Abstract: Abstract In this paper, first we introduce the notion of two-sided Cayley graph of a semigroup. Then, we investigate some fundamental properties of these graphs and we use our results to give partial answers to some problems raised by Iradmusa and Praeger about two-sided group graphs (two-sided Cayley graphs of groups). Specially, as a consequence of our results, we determine all undirected two-sided Cayley graphs of groups which are connected. Furthermore, by introducing the notion of color-preserving automorphisms of a two-sided Cayley graph of a semigroup (group) and calculating them under some assumptions, we determine the family of color-vertex transitive two-sided Cayley graphs of semigroups (groups).
PubDate: 2022-11-06

• On Perfect Sequence Covering Arrays

Abstract: Abstract A PSCA $$(v, t, \lambda )$$ is a multiset of permutations of the v-element alphabet $$\{0, \dots , v-1\}$$ , such that every sequence of t distinct elements of the alphabet appears in the specified order in exactly $$\lambda$$ of the permutations. For $$v \geqslant t \geqslant 2$$ , we define g(v, t) to be the smallest positive integer $$\lambda$$ , such that a PSCA $$(v, t, \lambda )$$ exists. We show that $$g(6, 3) = g(7, 3) = g(7, 4) = 2$$ and $$g(8, 3) = 3$$ . Using suitable permutation representations of groups, we make improvements to the upper bounds on g(v, t) for many values of $$v \leqslant 32$$ and $$3\leqslant t\leqslant 6$$ . We also prove a number of restrictions on the distribution of symbols among the columns of a PSCA.
PubDate: 2022-11-01

• Asymptotics, Turán Inequalities, and the Distribution of the BG-Rank and
2-Quotient Rank of Partitions

Abstract: Abstract Let j, n be even positive integers, and let $$\overline{p}_j(n)$$ denote the number of partitions with BG-rank j, and $$\overline{p}_j(a,b;n)$$ to be the number of partitions with BG-rank j and 2-quotient rank congruent to $$a \ \, \left( \mathrm {mod} \, b \right)$$ . We give asymptotics for both statistics, and show that $$\overline{p}_j(a,b;n)$$ is asymptotically equidistributed over the congruence classes modulo b. We also show that each of $$\overline{p}_j(n)$$ and $$\overline{p}_j(a,b;n)$$ asymptotically satisfy all higher-order Turán inequalities.
PubDate: 2022-10-29

• Sandpile Groups of Random Bipartite Graphs

Abstract: Abstract We determine the asymptotic distribution of the p-rank of the sandpile groups of random bipartite graphs. We see that this depends on the ratio between the number of vertices on each side, with a threshold when the ratio between the sides is equal to $$\frac{1}{p}$$ . We follow the approach of Wood (J Am Math Soc 30(4):915–958, 2017) and consider random graphs as a special case of random matrices, and rely on a variant the definition of min-entropy given by Maples (Cokernels of random matrices satisfy the Cohen–Lenstra heuristics, 2013) to obtain useful results about these random matrices. Our results show that unlike the sandpile groups of Erdős–Rényi random graphs, the distribution of the sandpile groups of random bipartite graphs depends on the properties of the graph, rather than coming from some more general random group model.
PubDate: 2022-10-29

• Ramanujan’s Theta Functions and Parity of Parts and Cranks of
Partitions

Abstract: Abstract In this paper, we explore intricate connections between Ramanujan’s theta functions and a class of partition functions defined by the nature of the parity of their parts. This consequently leads us to the parity analysis of the crank of a partition and its correlation with the number of partitions with odd number of parts, self-conjugate partitions, and also with Durfee squares and Frobenius symbols.
PubDate: 2022-10-25

• A Proof of the $$\frac{n!}{2}$$ Conjecture for Hook Shapes

Abstract: Abstract A well-known representation-theoretic model for the transformed Macdonald polynomial $${\widetilde{H}}_\mu (Z;t,q)$$ , where $$\mu$$ is an integer partition, is given by the Garsia–Haiman module $${\mathcal {H}}_\mu$$ . We study the $$\frac{n!}{k}$$ conjecture of Bergeron and Garsia, which concerns the behavior of certain k-tuples of Garsia–Haiman modules under intersection. In the special case that $$\mu$$ has hook shape, we use a basis for $${\mathcal {H}}_\mu$$ due to Adin, Remmel, and Roichman to resolve the $$\frac{n!}{2}$$ conjecture by constructing an explicit basis for the intersection of two Garsia–Haiman modules.
PubDate: 2022-10-20

• A Combinatorial Characterization of Cluster Algebras: On the Number of
Arrows of Cluster Quivers

Abstract: Abstract Let $$\tilde{Q}$$ (resp. Q) be an extended exchange (resp. exchange) cluster quiver of finite mutation type. We introduce the distribution set of the numbers of arrows for $$Mut[\tilde{Q}]$$ (resp. Mut[Q]), give the maximum and minimum numbers of the distribution set and establish the existence of an extended complete walk (resp. a complete walk). As a consequence, we prove that the distribution set for $$Mut[\tilde{Q}]$$ (resp. Mut[Q]) is continuous except in the case of exceptional cluster algebras. In case of cluster quivers $$Q_{inf}$$ of infinite mutation type, the distribution set for $$Mut[Q_{inf}]$$ in general is not continuous. Besides, we show that the maximal number of arrows of quivers in $$Mut[Q_{inf}]$$ is infinite if and only if the maximal number of arrows between any two vertices of a quiver in $$Mut[Q_{inf}]$$ is infinite.
PubDate: 2022-10-06

• Matching Complexes of Trees and Applications of the Matching Tree
Algorithm

Abstract: Abstract A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G. The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. We study two specific families of trees. For caterpillar graphs, we give explicit formulas for the number of spheres in each dimension and for perfect binary trees we find a strict connectivity bound. We also use a tool from discrete Morse theory called the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.
PubDate: 2022-09-27

• The Free m-Cone of a Matroid and Its $${\mathcal {G}}$$ G -Invariant

Abstract: Abstract For a matroid, its configuration determines its $${\mathcal {G}}$$ -invariant. Few examples are known of pairs of matroids with the same $${\mathcal {G}}$$ -invariant but different configurations. In order to produce new examples, we introduce the free m-cone $$Q_m(M)$$ of a loopless matroid M, where m is a positive integer. We show that the $${\mathcal {G}}$$ -invariant of M determines the $${\mathcal {G}}$$ -invariant of $$Q_m(M)$$ , and that the configuration of $$Q_m(M)$$ determines M; so if M and N are nonisomorphic and have the same $${\mathcal {G}}$$ -invariant, then $$Q_m(M)$$ and $$Q_m(N)$$ have the same $${\mathcal {G}}$$ -invariant but different configurations. We prove analogous results for several variants of the free m-cone. We also define a new matroid invariant of M, and show that it determines the Tutte polynomial of $$Q_m(M)$$ .
PubDate: 2022-09-13
DOI: 10.1007/s00026-022-00606-2

• Polycubes with Small Perimeter Defect

Abstract: Abstract In this paper, we consider enumeration of d-dimensional polycubes, whose perimeter (defined as the number of empty cells neighboring the polycube) has a fixed deviation from the maximum possible value. We provide a general framework for deriving such formulae, as well as several explicit formulae. In particular, we prove that for any fixed dimension d, the generating function that enumerates polycubes with a fixed defect (with respect to their volume) is rational. Moreover, its denominator is a product of cyclotomic polynomials.
PubDate: 2022-09-10
DOI: 10.1007/s00026-022-00601-7

• Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse
into the Matching Pattern Poset

Abstract: Abstract A matching of the set $$[2n]=\{1,2,\ldots ,2n\}$$ is a partition of [2n] into blocks with two elements, i.e. a graph on [2n], such that every vertex has degree one. Given two matchings $$\sigma$$ and $$\tau$$ , we say that $$\sigma$$ is a $$pattern$$ of $$\tau$$ when $$\sigma$$ can be obtained from $$\tau$$ by deleting some of its edges and consistently relabelling the remaining vertices. This is a partial order relation turning the set of all matchings into a poset, which will be called the matching pattern poset. In this paper, we continue the study of classes of pattern avoiding matchings (see below for previous work on this subject). In particular, we work out explicit formulas to enumerate the class of matchings avoiding two new patterns, obtained by juxtaposition of smaller patterns, and we describe a recursive formula for the generating function of the class of matchings avoiding the lifting of a pattern and two additional patterns. Moreover, we introduce the notion of unlabeled pattern, as a combinatorial way to collect patterns, and we provide enumerative formulas for two classes of matchings avoiding an unlabeled pattern of order three. In one case, the enumeration follows from an interesting bijection between the matchings of the class and ternary trees. The last part of the paper initiates the study of the matching pattern poset, by providing some preliminary results about its Möbius functions and the structure of some simple intervals.
PubDate: 2022-09-04
DOI: 10.1007/s00026-022-00596-1

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762