Subjects -> COMPUTER SCIENCE (Total: 2313 journals)     - ANIMATION AND SIMULATION (33 journals)    - ARTIFICIAL INTELLIGENCE (133 journals)    - AUTOMATION AND ROBOTICS (116 journals)    - CLOUD COMPUTING AND NETWORKS (75 journals)    - COMPUTER ARCHITECTURE (11 journals)    - COMPUTER ENGINEERING (12 journals)    - COMPUTER GAMES (23 journals)    - COMPUTER PROGRAMMING (25 journals)    - COMPUTER SCIENCE (1305 journals)    - COMPUTER SECURITY (59 journals)    - DATA BASE MANAGEMENT (21 journals)    - DATA MINING (50 journals)    - E-BUSINESS (21 journals)    - E-LEARNING (30 journals)    - ELECTRONIC DATA PROCESSING (23 journals)    - IMAGE AND VIDEO PROCESSING (42 journals)    - INFORMATION SYSTEMS (109 journals)    - INTERNET (111 journals)    - SOCIAL WEB (61 journals)    - SOFTWARE (43 journals)    - THEORY OF COMPUTING (10 journals) COMPUTER SCIENCE (1305 journals)                  1 2 3 4 5 6 7 | 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  [2469 journals]
• Some More Identities of Kanade–Russell Type Derived Using
Rosengren’s Method

Abstract: Abstract In the present paper, we consider some variations and generalizations of the multi-sum to single-sum transformation recently used by Rosengren in his proof of the Kanade–Russell identities. These general transformations are then used to prove a number of identities equating multi-sums and infinite products or multi-sums and infinite product $$\times$$ a false theta series. Examples include the following: \begin{aligned}&\sum _{j,k,p,r=0}^{\infty } \frac{(-1)^{j+k} q^{ (2 j + k - p + r)^2/2 + k (k + 4)/2 + 3 j - p/2 + 3 r/2}(-q;q)_r}{\left( q^2;q^2\right) {}_j (q;q)_k (q;q)_p (q;q)_r} \\&\quad =2\frac{ \left( -q;q^2\right) {}_{\infty } \left( -q^2,-q^{14},q^{16};q^{16}\right) {}_{\infty }}{(q;q)_{\infty }}. \end{aligned} Let \begin{aligned} Q(i,j,k,l,p):= & {} \frac{1}{2} (i+6j+4 k+2 l-p) (i+6 j+4 k+2 l-p-1)\\&+2 k (k-1)+l (l-1)+3 i +15j+14k+5 l-2 p. \end{aligned} Then \begin{aligned}&\sum _{i,j,k,l,p=0}^{\infty } \frac{(-1)^{l+k}q^{Q(i,j,k,l,p)} }{ \left( q;q\right) {}_i \left( q^6;q^6\right) {}_j \left( q^4;q^4\right) {}_k \left( q^2;q^2\right) {}_l (q;q)_p } \\&\quad = \frac{2 (-q;q)_{\infty }^2 }{q \left( q^3;q^6\right) {}_{\infty } \left( q^4;q^4\right) {}_{\infty }}\left( 1+ \sum _{r=1}^{\infty } \left( q^{9 r^2+6 r}-q^{9 r^2-6 r}\right) \right) . \\&\sum _{j,k,p=0}^{\infty } (-1)^{k} \frac{q^{(3j+2k-p)(3j+2k-p-1)/2+k(k-1)-p+6j+6k} }{(q^3;q^3)_j(q^2;q^2)_{k} (q;q)_{p}}\\&\quad = \frac{ (-1;q)_{\infty }(q^{18};q^{18})_{\infty } }{ (q^3;q^3)_{\infty }(q^{9};q^{18})_{\infty } }. \end{aligned}
PubDate: 2022-05-12

• On the Universality and Extremality of Graphs with a Distance Constrained
Colouring

Abstract: Abstract A lambda colouring (or L(2, 1)-colouring) of a graph is an assignment of non-negative integers (with minimum assignment 0) to its vertices such that the adjacent vertices must receive integers at least two apart and the vertices at distance two must receive distinct integers. The lambda chromatic number (or the $$\lambda$$ number) of a graph G is the least non-negative integer among all the maximum assigned non-negative integer over all possible lambda colouring of the graph G. Here we have shown that every edge maximum graph with lambda chromatic number $$t\ge 5$$ , admits an equitable L(2, 1) colouring. Further, we have established a classification result, identifying all possible n-vertex graphs with lambda chromatic number $$t\ge 3$$ , where $$n\ge t+1$$ , which contain the maximum number of edges. Such classification provides a complete solution to a problem posed more than two decades ago in 1996 by John P. Georges and David W. Mauro.
PubDate: 2022-04-29

• A Fast Algorithm for Computing the Number of Magic Series

Abstract: Abstract We present a fast algorithm for computing the number of magic series, an enumeration problem of a certain integer partition. Kinnaes showed that the number appears as a coefficient in a Gaussian polynomial and that the exact value can be efficiently extracted with a finite variant of Cauchy’s integral formula. The algorithm requires a bit time complexity of $$O(m^4 M(m \log m))$$ and $$O(m \log m)$$ -bit space, where m is the order of the magic series and $$M(n)$$ is the time complexity of multiplying two n-bit numbers. Through our analysis, we confirm that this is the most efficient among previously reported algorithms. In addition, we show that the number can be computed with a bit time complexity of $$O(m^3 \log m M(m \log m))$$ by directly carrying out polynomial multiplication and division on the Gaussian polynomial. Though the space consumption increases to $$O(m^3 \log m)$$ bits, we demonstrate that our method actually computes the number faster for large orders.
PubDate: 2022-04-28

• Diamond Cone for $${{\mathfrak {sl}}}(m,n)$$ sl ( m , n )

Abstract: Abstract In this paper, we study the shape and the reduced shape algebra for the Lie superalgebra $${\mathfrak {sl}}(m,n)$$ . We define quasistandard Young tableaux, and they give a combinatorial basis for the reduced shape algebra, called the diamond cone. There is a natural bijective map from the set of semistandard tableaux with shape $$\lambda$$ to the set of quasistandard tableaux with smaller shape: the diamond cone is compatible with the stratification of the reduced shape algebra.
PubDate: 2022-04-26

• 3-Critical Subgraphs of Snarks

Abstract: Abstract In this paper we further our understanding of the structure of class two cubic graphs, or snarks, as they are commonly known. We do this by investigating their 3-critical subgraphs, or as we will call them, minimal conflicting subgraphs. We consider how the minimal conflicting subgraphs of a snark relate to its possible minimal 4-edge-colourings. We fully characterise the relationship between the resistance of a snark and the set of minimal conflicting subgraphs. That is, we show that the resistance of a snark is equal to the minimum number of edges which can be selected from the snark, such that the selection contains at least one edge from each minimal conflicting subgraph. We similarly characterise the relationship between what we call the critical subgraph of a snark and the set of minimal conflicting subgraphs. The critical subgraph being the set of all edges which are conflicting in some minimal colouring of the snark. Further to this, we define groups, or clusters, of minimal conflicting subgraphs. We then highlight some interesting properties and problems relating to clusters of minimal conflicting subgraphs.
PubDate: 2022-04-26

• Minimum Quantum Degrees for Isotropic Grassmannians in Types B and C

Abstract: Abstract We give a formula in terms of Young diagrams to calculate the minimum positive integer d such that $$q^d$$ appears in the quantum product of two Schubert classes for the submaximal isotropic Grassmannians in types B and C. We do this by studying curve neighborhoods. We compute curve neighborhoods in several combinatorial models including k-strict partitions and a set of partitions where their inclusion is compatible with the Bruhat order.
PubDate: 2022-04-22

• Pattern Hopf Algebras

Abstract: Abstract In this paper, we expand on the notion of combinatorial presheaf, first introduced explicitly by Aguiar and Mahajan in 2010 but already present in the literature in some other points of view. We do this by adapting the algebraic framework of species to the study of substructures in combinatorics. Afterwards, we consider functions that count the number of patterns of objects and endow the linear span of these functions with a product and a coproduct. In this way, any well-behaved family of combinatorial objects that admits a notion of substructure generates a Hopf algebra, and this association is functorial. For example, the Hopf algebra on permutations studied by Vargas in 2014 and the Hopf algebra on symmetric functions are particular cases of this construction. A specific family of pattern Hopf algebras of interest are the ones arising from commutative combinatorial presheaves. This includes the presheaves on graphs, posets and generalized permutahedra. Here, we show that all the pattern Hopf algebras corresponding to commutative presheaves are free. We also study a remarkable non-commutative presheaf structure on marked permutations, i.e. permutations with a marked element. These objects have a natural product called inflation, which is an operation motivated by factorization theorems for permutations. In this paper, we find new factorization theorems for marked permutations. We use these theorems to show that the pattern Hopf algebra for marked permutations is also free, using Lyndon words techniques.
PubDate: 2022-04-19

• Labeled Trees Generating Complete, Compact, and Discrete Ultrametric
Spaces

Abstract: Abstract We investigate the interrelations between labeled trees and ultrametric spaces generated by these trees. The labeled trees, which generate complete ultrametrics, totally bounded ultrametrics, and discrete ones, are characterized up to isomorphism. As corollary, we obtain a characterization of labeled trees generating compact ultrametrics and discrete totally bounded ultrametrics. It is also shown that every ultrametric space generated by labeled tree contains a dense discrete subspace.
PubDate: 2022-04-18

• Permutations with Exactly One Copy of a Monotone Pattern of Length k, and
a Generalization

Abstract: Abstract We construct an injection from the set of permutations of length n that contain exactly one copy of the decreasing pattern of length k to the set of permutations of length $$n+2$$ that avoid that pattern. We then prove that the generating function counting the former is not rational, and in the case when k is even and $$k\ge 4$$ , it is not even algebraic. We extend our injection and our nonrationality result to a larger class of patterns.
PubDate: 2022-04-12

• Polynomial Tau Functions of Symplectic KP and Multi-component Symplectic
KP Hierarchies

Abstract: Abstract In this paper, we prove that a zero mode of an appropriate combinatorial generating function is a polynomial tau-function of a form of symplectic KP (SKP) hierarchy and extend it to the multi-component SKP hierarchy. Moreover, we write the polynomial tau-function of SKP hierarchy as determinant form in terms of the Vandermonde-like identity.
PubDate: 2022-04-12

• Matching in Power Graphs of Finite Groups

Abstract: Abstract The power graph P(G) of a finite group G is the undirected simple graph with vertex set G, where two elements are adjacent if one is a power of the other. In this paper, the matching numbers of power graphs of finite groups are investigated. We give upper and lower bounds, and conditions for the power graph of a group to possess a perfect matching. We give a formula for the matching number for any finite nilpotent group. In addition, using some elementary number theory, we show that the matching number of the enhanced power graph $$P_e(G)$$ of G (in which two elements are adjacent if both are powers of a common element) is equal to that of the power graph of G.
PubDate: 2022-03-13

• Congruence Normality of Simplicial Hyperplane Arrangements via Oriented
Matroids

Abstract: Abstract A catalogue of simplicial hyperplane arrangements was first given by Grünbaum in 1971. These arrangements naturally generalize finite Coxeter arrangements and also the weak order through the poset of regions. The weak order is known to be a congruence normal lattice, and congruence normality of lattices of regions of simplicial arrangements can be determined using polyhedral cones called shards. In this article, we update Grünbaum’s catalogue by providing normals realizing all known simplicial arrangements with up to 37 lines and key invariants. Then we add structure to this catalogue by determining which arrangements always/sometimes/never lead to congruence normal lattices of regions. To this end, we use oriented matroids to recast shards as covectors to determine congruence normality of large hyperplane arrangements. We also show that lattices of regions coming from finite Weyl groupoids of any rank are always congruence normal.
PubDate: 2022-03-01

• On a Theorem of Baxter and Zeilberger via a Result of Roselle

Abstract: Abstract We provide a new proof of a result of Baxter and Zeilberger showing that $${{\,\mathrm{inv}\,}}$$ and $${{\,\mathrm{maj}\,}}$$ on permutations are jointly independently asymptotically normally distributed. The main feature of our argument is that it uses a generating function due to Roselle, answering a question raised by Romik and Zeilberger.
PubDate: 2022-02-11
DOI: 10.1007/s00026-022-00570-x

• ¿How do 9 Points Look Like in $$\mathbb {E}^3$$ E 3 '

Abstract: Abstract The aim of this note is to give an elementary proof of the following fact: given three red convex sets and three blue convex sets in $$\mathrm{I\!E}^3$$ , such that every red intersects every blue, there is a line transversal to the reds or there is a line transversal to the blues. This is a special case of a theorem of Montajano and Karasev (Discrete Comput Geom 46(2):283–300, 2011) and generalizes, in a sense, the colourful Helly theorem due to Lovász (cf. Discrete Math 40(2,3):141–152, 1982)
PubDate: 2022-01-30
DOI: 10.1007/s00026-022-00568-5

• On the Shifted Littlewood–Richardson Coefficients and the
Littlewood–Richardson Coefficients

Abstract: Abstract We give a new interpretation of the shifted Littlewood–Richardson coefficients $$f_{\lambda \mu }^\nu$$ ( $$\lambda ,\mu ,\nu$$ are strict partitions). The coefficients $$g_{\lambda \mu }$$ which appear in the decomposition of Schur Q-function $$Q_\lambda$$ into the sum of Schur functions $$Q_\lambda = 2^{l(\lambda )}\sum \nolimits _{\mu }g_{\lambda \mu }s_\mu$$ can be considered as a special case of $$f_{\lambda \mu }^\nu$$ (here $$\lambda$$ is a strict partition of length $$l(\lambda )$$ ). We also give another description for $$g_{\lambda \mu }$$ as the cardinal of a subset of a set that counts Littlewood–Richardson coefficients $$c_{\mu ^t\mu }^{{\tilde{\lambda }}}$$ . This new point of view allows us to establish connections between $$g_{\lambda \mu }$$ and $$c_{\mu ^t \mu }^{{\tilde{\lambda }}}$$ . More precisely, we prove that $$g_{\lambda \mu }=g_{\lambda \mu ^t}$$ , and $$g_{\lambda \mu } \le c_{\mu ^t\mu }^{{\tilde{\lambda }}}$$ . We conjecture that $$g_{\lambda \mu }^2 \le c^{{\tilde{\lambda }}}_{\mu ^t\mu }$$ and formulate some conjectures on our combinatorial models which would imply this inequality if it is valid.
PubDate: 2022-01-24
DOI: 10.1007/s00026-022-00566-7

• Flexibility and Movability in Cayley Graphs

Abstract: Abstract Let $${\varvec{\Gamma }} = (V,E)$$ be a (non-trivial) finite graph with $$\lambda : E \rightarrow {\mathbb {R}}_{+}$$ an edge labeling of $${\varvec{\Gamma }}$$ . Let $$\rho : V\rightarrow {\mathbb {R}}^{2}$$ be a map which preserves the edge labeling, i.e., \begin{aligned} \Vert \rho (u) - \rho (v)\Vert _{2} = \lambda ((u,v)), \,\forall (u,v)\in E, \end{aligned} where $$\Vert x-y\Vert _{2}$$ denotes the Euclidean distance between two points $$x,y \in {\mathbb {R}}^{2}$$ . The labeled graph is said to be flexible if there exists an infinite number of such maps (up to equivalence by rigid transformations) and it is said to be movable if there exists an infinite number of injective maps (again up to equivalence by rigid transformations). We study movability of Cayley graphs and construct regular movable graphs of all degrees. Further, we give explicit constructions of dense, movable graphs.
PubDate: 2022-01-23
DOI: 10.1007/s00026-022-00569-4

• Positivity Among P-partition Generating Functions

Abstract: Abstract We seek simple conditions on a pair of labeled posets that determine when the difference of their $$(P,\omega )$$ -partition enumerators is F-positive, i.e., positive in Gessel’s fundamental basis. This is a quasisymmetric analogue of the extensively studied problem of finding conditions on a pair of skew shapes that determine when the difference of their skew Schur functions is Schur-positive. We determine necessary conditions and separate sufficient conditions for F-positivity, and show that a broad operation for combining posets preserves positivity properties. We conclude with classes of posets for which we have conditions that are both necessary and sufficient.
PubDate: 2022-01-16
DOI: 10.1007/s00026-021-00563-2

• The Penney’s Game with Group Action

Abstract: Abstract Consider equipping an alphabet $$\mathcal {A}$$ with a group action which partitions the set of words into equivalence classes which we call patterns. We answer standard questions for Penney’s game on patterns and show non-transitivity for the game on patterns as the length of the pattern tends to infinity. We also analyze bounds on the pattern-based Conway leading number and expected wait time, and further explore the game under the cyclic and symmetric group actions.
PubDate: 2022-01-15
DOI: 10.1007/s00026-021-00564-1

• Complete Circular Regular Dessins of Type $$\{2^e,2^f\}$$ { 2 e , 2 f } I:
Metacyclic Case

Abstract: Abstract A complete dessin of type $$\{2^e,2^f\}$$ is an orientable map with underlying graph being a complete bipartite graph $$\mathbf{K}_{2^e,2^f}$$ , which is said to be regular if all edges are equivalent under the group of color- and orientation-preserving automorphisms, and circular if the boundary cycle of each face is a circuit (a simple cycle). As one of a series papers towards a classification of complete circular regular dessins of type $$\{m,n\}$$ , this paper presents such a classification for the case $$\{m,n\}=\{2^e,2^f\}$$ , where e, f are positive integers and $$e\ge f\ge 2$$ . We note that the group G of color- and orientation-preserving automorphisms is a bicyclic 2-group of type $$\{2^e,2^f\}$$ , and our analysis splits naturally into two cases depending on whether the group G is metacyclic or not. In this paper, we deal with the case that G is metacyclic.
PubDate: 2021-12-12
DOI: 10.1007/s00026-021-00562-3

• Central Limit Theorem for Peaks of a Random Permutation in a Fixed
Conjugacy Class of $$S_n$$ S n

Abstract: Abstract The number of peaks of a random permutation is known to be asymptotically normal. We give a new proof of this and prove a central limit theorem for the distribution of peaks in a fixed conjugacy class of the symmetric group. Our technique is to apply analytic combinatorics to study a complicated but exact generating function for peaks in a given conjugacy class.
PubDate: 2021-12-07
DOI: 10.1007/s00026-021-00561-4

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