Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

Sandpile groups and the coeulerian property for random directed graphs

We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.     

The Arithmetical Hierarchy of Real Numbers

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left (right) computable iff it is the supremum (infimum) of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable (multiple) sequences of rational numbers we introduce a non‐collapsing hierarchy {Σ_n, Π_n, Δ_n : n ∈ ℕ} of real numbers. We characterize the classes Σ₂, Π₂ and Δ₂ in various ways and give several interesting examples.     

Critical groups for homeomorphism classes of graphs

In this paper the weighted fundamental circuits intersection matrix of an edge-labeled graph is introduced for computing the critical groups for homeomorphism classes of graphs. As an application, it is proved that for any given finite connected simple graph there is a homeomorphic graph with cyclic critical group.     

Converse Prime Element Theorems for Arithmetical Semigroups

Conditions are presented which ensure that in an additive (multiplicative) arithmetical semigroup a positive proportion of all elements are prime elements. Under these conditions asymptotics are derived for the average number of elements with a fixed number of prime element factors, counted with and without multiplicity.     

Arithmetical Semigroups Related to Trees and Polyhedra,II — Maps on Surfaces

This paper extends recent investigations by Arnold Knopfmacher and John Knopfmacher [10] of asymptotic enumeration questions concerning finite graphs, trees and polyhedra. The present emphasis is on the counting of non‐isomorphic maps of not necessarily connected finite graphs on arbitrary surfaces. A significant aid towards this goal is provided by an extended abstract prime number theorem, based partly on more delicate tools of analysis due to W. K. Hayman [8].     

Inverse relations in Shapiro’s open questions

As an inverse relation, involution with an invariant sequence plays a key role in combinatorics and features prominently in some of Shapiro’s open questions (Shapiro, 2001). In this paper, invariant sequences are used to provide answers to some of these questions about the Fibonacci matrix and Riordan involutions.     

Ballot matrix as Catalan matrix power and related identities

We use an analytical approach to find the kth power of the Catalan matrix. Precisely, it is proven that the power of the Catalan matrix is a lower triangular Toeplitz matrix which contains the well-known ballot numbers. A result from [H. S. Wilf, Generatingfunctionology, Academic Press, New York, 1990, Free download available from http://www.math.upenn.edu/~wilf/Downld.html.], related to the generating function for Catalan numbers, is extended to the negative integers. Three interesting representations for Catalan numbers by means of the binomial coefficients and the hypergeometric functions are obtained using relations between Catalan matrix powers.     

Graphs whose critical groups have larger rank

The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized.     

Hodge cycles on the jacobian variety of the Catalan curve

The jacobian variety of the Catalan curve yq = xp - 1is shown to be nondegenerate. As an application, a 0-1-matrix whose determinantcomputes the relative class number of the pq-th cyclotomic field is constructed.     

The Universal Embedding Dimension of the Near Polygon on the 1-Factors of a Complete Graph

We sho that the universal embedding dimensions (over F₂) of the near polygons associated ith Sym(2n) (vieed as subgroup of Sp1(2n - 2, 2)) are the Catalan numbers.     

Some identities on the Catalan, Motzkin and Schröder numbers

In this paper, some identities between the Catalan, Motzkin and Schröder numbers are obtained by using the Riordan group. We also present two combinatorial proofs for an identity related to the Catalan numbers with the Motzkin numbers and an identity related to the Schröder numbers with the Motzkin numbers, respectively.     

Arithmetical Rank of Squarefree Monomial Ideals Generated by Five Elements or with Arithmetic Degree Four

Let I be a squarefree monomial ideal of a polynomial ring S. In this article, we prove that the arithmetical rank of I is equal to the projective dimension of S/I when one of the following conditions is satisfied: (1) μ(I) ≤5; (2) arithdeg I ≤ 4.     

Digraphs with at most one trivial critical ideal

Critical ideals generalize the critical group, Smith group and the characteristic polynomials of the adjacency and Laplacian matrices of a graph. We give a complete characterization of the digraphs with at most one trivial critical ideal. Which implies the characterizations of the digraphs whose critical group has one invariant factor equal to one, and the digraphs whose Smith group has one invariant factor equal to one.     

Some identities on Catalan numbers and hypergeometric functions via Catalan matrix power

In this paper we use the Catalan matrix power as a tool for deriving identities involving Catalan numbers and hypergeometric functions. For that purpose, we extend earlier investigated relations between the Catalan matrix and the Pascal matrix by inserting the Catalan matrix power and particulary the squared Catalan matrix in those relations. We also pay attention to some relations between Catalan matrix powers of different degrees, which allows us to derive the simplification formula for hypergeometric function ₃F₂, as well as the simplification formula for the product of the Catalan number and the hypergeometric function ₃F₂. Some identities involving Catalan numbers, proved by the non-matrix approach, are also given.