Exact sequences for the homology of the matching complex

Building on work by Bouc and by Shareshian and Wachs, we provide a toolbox of long exact sequences for the reduced simplicial homology of the matching complex Mn, which is the simplicial complex of matchings in the complete graph Kn. Combining these sequences in different ways, we prove several results about the 3-torsion part of the homology of Mn. First, we demonstrate that there is nonvanishing 3-torsion in whenever , where . By results due to Bouc and to Shareshian and Wachs, is a nontrivial elementary 3-group for almost all n and the bottom nonvanishing homology group of Mn for all n≠2. Second, we prove that is a nontrivial 3-group whenever . Third, for each k?0, we show that there is a polynomial fk(r) of degree 3k such that the dimension of , viewed as a vector space over Z₃, is at most fk(r) for all r?k+2.     

Path-kipas Ramsey numbers

For two given graphs F and H, the Ramsey number R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers , where P_n is a path on n vertices and is the graph obtained from the join of K₁ and P_m. We determine the exact values of for the following values of n and m: 1?n?5 and m?3; n?6 and (m is odd, 3?m?2n-1) or (m is even, 4?m?n+1); 6?n≤7 and m=2n-2 or m?2n; n?8 and m=2n-2 or m=2n or (q·n-2q+1?m?q·n-q+2 with 3?q?n-5) or m?(n-3)²; odd n?9 and (q·n-3q+1?m?q·n-2q with 3?q?(n-3)/2) or (q·n-q-n+4?m?q·n-2q with (n-1)/2?q?n-4). Moreover, we give lower bounds and upper bounds for for the other values of m and n.     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

Inequalities for the median of the gamma distribution

We provide several new inequalities involving λ_n, the median of the gamma distribution of order n+1 with parameter 1. Among others, we present sharp upper and lower bounds for the arithmetic mean of λ₁,λ₂,…,λ_n. For all integers n?1 we have

     

Solution to a conjecture on the maximal energy of bipartite bicyclic graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let C_n denote the cycle of order n and the graph obtained from joining two cycles C₆ by a path P_n-12 with its two leaves. Let B_n denote the class of all bipartite bicyclic graphs but not the graph R_a,b, which is obtained from joining two cycles C_a and C_b (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class B_n. However, they could not determine which of the two graphs R_a,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of R_a,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open.     

Symplectic duality of symmetric spaces

Let M⊂Cn be a complex n-dimensional Hermitian symmetric space endowed with the hyperbolic form ωhyp. Denote by (M^∗,ωFS) the compact dual of (M,ωhyp), where ωFS is the Fubini-Study form on M^∗. Our first result is Theorem 1.1 where, with the aid of the theory of Jordan triple systems, we construct an explicit symplectic duality, namely a diffeomorphism satisfying and for the pull-back of ΨM, where ω₀ is the restriction to M of the flat Kähler form of the Hermitian positive Jordan triple system associated to M. Amongst other properties of the map ΨM, we also show that it takes (complete) complex and totally geodesic submanifolds of M through the origin to complex linear subspaces of Cn. As a byproduct of the proof of Theorem 1.1 we get an interesting characterization (Theorem 5.3) of the Bergman form of a Hermitian symmetric space in terms of its restriction to classical complex and totally geodesic submanifolds passing through the origin.     

Reduction of derived Hochschild functors over commutative algebras and schemes

We study functors underlying derived Hochschild cohomology, also called Shukla cohomology, of a commutative algebra S essentially of finite type and of finite flat dimension over a commutative noetherian ring K. We construct a complex of S-modules D, and natural reduction isomorphisms for all complexes of S-modules N and all complexes M of finite flat dimension over K whose homology H(M) is finitely generated over S; such isomorphisms determine D up to derived isomorphism. Using Grothendieck duality theory we establish analogous isomorphisms for any essentially finite-type flat map of noetherian schemes, with f^!OY in place of D.     

Complete solution to a problem on the maximal energy of unicyclic bipartite graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Denote by C_n the cycle, and the unicyclic graph obtained by connecting a vertex of C₆ with a leaf of P_n-6. Caporossi et al. conjectured that the unicyclic graph with maximal energy is for n=8,12,14 and n≥16. In Hou et al. (2002) [Y. Hou, I. Gutman, C. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36], the authors proved that is maximal within the class of the unicyclic bipartite n-vertex graphs differing from C_n. And they also claimed that the energies of C_n and is quasi-order incomparable and left this as an open problem. In this paper, by utilizing the Coulson integral formula and some knowledge of real analysis, especially by employing certain combinatorial techniques, we show that the energy of is greater than that of C_n for n=8,12,14 and n≥16, which completely solves this open problem and partially solves the above conjecture.     

Heteroclinic solutions for a class of the second order Hamiltonian systems

We shall be concerned with the existence of heteroclinic orbits for the second order Hamiltonian system , where q∈Rn and V∈C¹(R×Rn,R), V?0. We will assume that V and a certain subset M⊂Rn satisfy the following conditions. M is a set of isolated points and #M?2. For every sufficiently small ε>0 there exists δ>0 such that for all (t,z)∈R×Rn, if d(z,M)?ε then −V(t,z)?δ. The integrals , z∈M, are equi-bounded and −V(t,z)→∞, as |t|→∞, uniformly on compact subsets of Rn?M. Our result states that each point in M is joined to another point in M by a solution of our system.     

Finiteness of graded local cohomology modules

Let R=?_n∈N0R_n be a Noetherian homogeneous ring with local base ring (R₀,m₀) and irrelevant ideal R₊, let M be a finitely generated graded R-module. In this paper we show that is Artinian and is Artinian for each i in the case where R₊ is principal. Moreover, for the case where , we prove that, for each i∈N₀, is Artinian if and only if is Artinian. We also prove that is Artinian, where and c is the cohomological dimension of M with respect to R₊. Finally we present some examples which show that and need not be Artinian.     

Likelihood ratio orderings of spacings of heterogeneous exponential random variables

Let X₁,X₂,…,X_n be independent exponential random variables such that X_i has failure rate λ for i=1,…,p and X_j has failure rate λ^* for j=p+1,…,n, where p≥1 and q=n-p≥1. Denote by D_i:n(p,q)=X_i:n-X_i-1:n the ith spacing of the order statistics , where X_0:n≡0. It is shown that D_i:n(p,q)?_lrD_i+1:n(p,q) for i=1,…,n-1, and that if λ?λ^* then , and for i=1,…,n, where ?_lr denotes the likelihood ratio order. The main results are used to establish the dispersive orderings between spacings.     

The third homology of the special linear group of a field

We prove that for any infinite field F, the map is an isomorphism for all n≥3. When n=2 the cokernel of this map is naturally isomorphic to , where is the nth Milnor K-group of F. We deduce that the natural homomorphism from to the indecomposable K₃ of F, , is surjective for any infinite field F.     

Long paths with endpoints in given vertex-subsets of graphs

Let G=(V,E) be a connected graph of order n, t a real number with t?1 and M⊆V(G) with . In this paper, we study the problem of some long paths to maintain their one or two different endpoints in M. We obtain the following two results: (1) for any vertex v∈V(G), there exists a vertex u∈M and a path P with the two endpoints v and u to satisfy , , d_G(u)+1-t}; (2) there exists either a cycle C to cover all vertices of M or a path P with two different endpoints u₀ and u_p in M to satisfy , where .     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

Monoid generalizations of the Richard Thompson groups

The groups G_k,1 of Richard Thompson and Graham Higman can be generalized in a natural way to monoids, that we call M_k,1, and to inverse monoids, called ; this is done by simply generalizing bijections to partial functions or partial injective functions. The monoids M_k,1 have connections with circuit complexity (studied in other papers). Here we prove that M_k,1 and are congruence-simple for all k. Their Green relations J and D are characterized: M_k,1 and are J-0-simple, and they have k−1 non-zero D-classes. They are submonoids of the multiplicative part of the Cuntz algebra O_k. They are finitely generated, and their word problem over any finite generating set is in P. Their word problem is coNP-complete over certain infinite generating sets.