Steiner almost self-complementary graphs and halving near-Steiner triple systems

We show that for every admissible order v≡0 or there exists a near-Steiner triple system of order v that can be halved. As a corollary we obtain that a Steiner almost self-complementary graph with n vertices exists if and only if n≡0 or .     

Extended directed triple systems

Let {n;b₂,b₁} denote the class of extended directed triple systems of the order n in which the number of blocks of the form [a,b,a] is b₂ and the number of blocks of the form [b,a,a] or [a,a,b] is b₁. In this paper, we have shown that the necessary and sufficient condition for the existence of the class {n;b₂,b₁} is b₁≠1, 0?b₂+b₁?n and

(1)

for ;

(2)

for .

     

Doyen–Wilson theorem for perfect hexagon triple systems

The graph consisting of the three 3-cycles (or triples) (a,b,c), (c,d,e), and (e,f,a), where a,b,c,d,e and f are distinct is called a hexagon triple. The 3-cycle (a,c,e) is called an inside 3-cycle; and the 3-cycles (a,b,c), (c,d,e), and (e,f,a) are called outside 3-cycles. A hexagon triple system of order v is a pair (X,C), where C is a collection of edge disjoint hexagon triples which partitions the edge set of 3K_v. Note that the outside 3-cycles form a 3-fold triple system. If the hexagon triple system has the additional property that the collection of inside 3-cycles (a,c,e) is a Steiner triple system it is said to be perfect. In 2004, Küçükçifçi and Lindner had shown that there is a perfect hexagon triple system of order v if and only if and v≥7. In this paper, we investigate the existence of a perfect hexagon triple system with a given subsystem. We show that there exists a perfect hexagon triple system of order v with a perfect sub-hexagon triple system of order u if and only if v≥2u+1, and u≥7, which is a perfect hexagon triple system analogue of the Doyen–Wilson theorem.     

Transitive resolvable idempotent quasigroups and large sets of resolvable Mendelsohn triple systems

We first define a transitive resolvable idempotent quasigroup (TRIQ), and show that a TRIQ of order v exists if and only if 3∣v and . Then we use TRIQ to present a tripling construction for large sets of resolvable Mendelsohn triple systems s, which improves an earlier version of tripling construction by Kang. As an application we obtain an for any integer n≥1, which provides an infinite family of even orders.     

Smallest defining sets of directed triple systems

A directed triple system of order v, , is a pair (V,B) where V is a set of v elements and B is a collection of ordered triples of distinct elements of V with the property that every ordered pair of distinct elements of V occurs in exactly one triple as a subsequence. A set of triples in a D is a defining set for D if it occurs in no other on the same set of points. A defining set for D is a smallest defining set for D if D has no defining set of smaller cardinality. In this paper we are interested in the quantity

     

Some relations between rank of a graph and its complement

Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .     

Vanishing of derived limits of non-standard inverse systems

It is proved that for certain non-standard versions of inverse systems G of R-modules, we have for n>0.The result is applied to define a reasonably canonical non-standard resolution for an arbitrary inverse system G of R-modules, such that the application of the inverse limit functor yields a complex whose cohomology groups are isomorphic to the derived limits, limn. Furthermore, the non-standard resolution gives also the maps limng, and the connecting homomorphisms to a reasonable degree.We also prove that for miscellaneous types of inverse systems H of modules, the system H is a direct summand of .     

Super-simple Steiner pentagon systems

A Steiner pentagon system of order v(SPS(v)) is said to be super-simple if its underlying (v,5,2)-BIBD is super-simple; that is, any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary condition for the existence of a super-simple SPS(v); namely, v?5 and v≡1 or is sufficient, except for v=5, 15 and possibly for v=25. In the process, we also improve an earlier result for the spectrum of super-simple (v,5,2)-BIBDs, removing all the possible exceptions. We also give some new examples of Steiner pentagon packing and covering designs (SPPDs and SPCDs).     

On the existence of cycle frames and almost resolvable cycle systems

Suppose H is a complete m-partite graph K_m(n₁,n₂,…,n_m) with vertex set V and m independent sets G₁,G₂,…,G_m of n₁,n₂,…,n_m vertices respectively. Let G={G₁,G₂,…,G_m}. If the edges of λH can be partitioned into a set C of k-cycles, then (V,G,C) is called a k-cycle group divisible design with index λ, denoted by (k,λ)-CGDD. A (k,λ)-cycle frame is a (k,λ)-CGDD (V,G,C) in which C can be partitioned into holey 2-factors, each holey 2-factor being a partition of V?G_i for some G_i∈G. Stinson et al. have resolved the existence of (3,λ)-cycle frames of type g^u. In this paper, we show that there exists a (k,λ)-cycle frame of type g^u for k∈{4,5,6} if and only if , , u≥3 when k∈{4,6}, u≥4 when k=5, and (k,λ,g,u)≠(6,1,6,3). A k-cycle system of order n whose cycle set can be partitioned into (n−1)/2 almost parallel classes and a half-parallel class is called an almost resolvable k-cycle system, denoted by k-ARCS(n). Lindner et al. have considered the general existence problem of k-ARCS(n) from the commutative quasigroup for . In this paper, we give a recursive construction by using cycle frames which can also be applied to construct k-ARCS(n)s when . We also update the known results and prove that for k∈{3,4,5,6,7,8,9,10,14} there exists a k-ARCS(2kt+1) for each positive integer t with three known exceptions and four additional possible exceptions.     

The hyperelliptic limit cycles of the Liénard systems

For Liénard systems , with fm and gn real polynomials of degree m and n respectively, in [H. Zoladek, Algebraic invariant curves for the Liénard equation, Trans. Amer. Math. Soc. 350 (1998) 1681-1701] the author showed that if m?3 and m+1<n<2m there always exist Liénard systems which have a hyperelliptic limit cycle. Llibre and Zhang [J. Llibre, Xiang Zhang, On the algebraic limit cycles of Liénard systems, Nonlinearity 21 (2008) 2011-2022] proved that the Liénard systems with m=3 and n=5 have no hyperelliptic limit cycles and that there exist Liénard systems with m=4 and 5<n<8 which do have hyperelliptic limit cycles. So, it is still an open problem to characterize the Liénard systems which have an algebraic limit cycle in cases m>4 and m+1<n<2m. In this paper we will prove that there exist Liénard systems with m=5 and m+1<n<2m which have hyperelliptic limit cycles.     

On the log-Sobolev constant for the simple random walk on the n-cycle: the even cases

Consider the simple random walk on the n-cycle . For this example, Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996) 695) have shown that the log-Sobolev constant α is of the same order as the spectral gap λ. However the exact value of α is not known for n>4. (For n=2, it is a well known result of Gross (Amer. J. Math. 97 (1975) 1061) that α is . For n=3, Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996) 695) showed that . For n=4, the fact that follows from n=2 by tensorization.) Based on an idea that goes back to Rothaus (J. Funct. Anal. 39 (1980) 42; 42 (1981) 110), we prove that if n?4 is even, then the log-Sobolev constant and the spectral gap satisfy . This implies that when n is even and n?4.     

On colorings of graph powers

In this paper, some results concerning the colorings of graph powers are presented. The notion of helical graphs is introduced. We show that such graphs are hom-universal with respect to high odd-girth graphs whose (2t+1)th power is bounded by a Kneser graph according to the homomorphism order. Also, we consider the problem of existence of homomorphism to odd cycles. We prove that such homomorphism to a (2k+1)-cycle exists if and only if the chromatic number of the (2k+1)th power of is less than or equal to 3, where is the 3-subdivision of G. We also consider Nešet?il’s Pentagon problem. This problem is about the existence of high girth cubic graphs which are not homomorphic to the cycle of size five. Several problems which are closely related to Nešet?il’s problem are introduced and their relations are presented.     

Spectral radius of graphs with given matching number

In this paper, we show that of all graphs of order n with matching number β, the graphs with maximal spectral radius are K_n if n = 2β or 2β + 1; if 2β + 2 ? n < 3β + 2; or if n = 3β + 2; if n > 3β + 2, where is the empty graph on t vertices.     

Stable solutions of linear systems involving long chain of matrix multiplications

This paper is concerned with solving linear system (I_n+B_L?B₂B₁)x=b arising from the Green’s function calculation in the quantum Monte Carlo simulation of interacting electrons. The order of the system and integer L are adjustable. Also adjustable is the conditioning of the coefficient matrix to give rise an extreme ill-conditioned system. Two numerical methods based on the QR decomposition with column pivoting and the singular value decomposition, respectively, are studied in this paper. It is proved that the computed solution by each of the methods is weakly backward stable in the sense that the computed is close to the exact solution of a nearby linear system

     

Tamari lattices and noncrossing partitions in type B

The usual, or type A_n, Tamari lattice is a partial order on , the triangulations of an (n+3)-gon. We define a partial order on , the set of centrally symmetric triangulations of a (2n+2)-gon. We show that it is a lattice, and that it shares certain other nice properties of the A_n Tamari lattice, and therefore that it deserves to be considered the B_n Tamari lattice. We also define a bijection between and the noncrossing partitions of type B_n defined by Reiner.     

Note on the Markus-Yamabe conjecture for gradient dynamical systems

Let be a C¹ vector field which has a singular point O and its linearization is asymptotically stable at every point of Rn. We say that the vector field v satisfies the Markus-Yamabe conjecture if the critical point O is a global attractor of the dynamical system . In this note we prove that if v is a gradient vector field, i.e. v=∇f (f∈C²), then the basin of attraction of the critical point O is the whole Rn, thus implying the Markus-Yamabe conjecture for this class of vector fields. An analogous result for discrete dynamical systems of the form xm+1=∇f(xm) is proved.     

Sufficient conditions for the existence of at least n or exactly n limit cycles for the Liénard differential systems

In this paper we study the limit cycles of the Liénard differential system of the form , or its equivalent system , . We provide sufficient conditions in order that the system exhibits at least n or exactly n limit cycles.