The existence spectrum for overlarge sets of pure directed triple systems

A directed triple system of order v,denoted by DTS(v),is a pair (X,B) where X is a v-set and B is a collection of transitive triples on X such that every ordered pair of X belongs to exactly one triple of B.A DTS(v) (X,A) is called pure and denoted by PDTS(v) if (a,b,c) ∈ A implies (c,b,a) ∈/ A.An overlarge set of PDTS(v),denoted by OLPDTS(v),is a collection {(Y \{yi},Aij) : yi ∈ Y,j ∈ Z3},where Y is a (v+1)-set,each (Y \{yi},Aij) is a PDTS(v) and these Ais form a partition of all transitive triples on Y .In this paper,we shall discuss the existence problem of OLPDTS(v) and give the following conclusion: there exists an OLPDTS(v) if and only if v ≡ 0,1 (mod 3) and v 3.     

The spectrum for overlarge sets of directed triple systems

A directed triple system of order v,denoted by DTS(v,λ),is a pair(X,B)where X is a v- set and B is a collection of transitive triples on X such that every ordered pair of X belongs toλtriples of B.An overlarge set of disjoint DTS(v,λ),denoted by OLDTS(v,λ),is a collection{(Y\{y},A_i)}_i, such that Y is a(v 1)-set,each(Y\{y},A_i)is a DTS(v,λ)and all A_i's form a partition of all transitive triples of Y.In this paper,we shall discuss the existence problem of OLDTS(v,λ)and give the following conclusion:there exists an OLDTS(v,λ)if and only if eitherλ=1 and v≡0,1(mod 3),orλ=3 and v≠2.     

Large sets of pure directed triple systems with index λ

A directed triple system of order v with index λ, briefly by DTS（v,λ）, is a pair （X, B） where X is a v-set and B is a collection of transitive triples （blocks） on X such that every ordered pair of X belongs to λ blocks of B. A simple DTS（v, λ） is a DTS（v, λ） without repeated blocks. A simple DTS（v, ）,） is called pure and denoted by PDTS（v, λ） if （x, y, z） ∈ B implies （z, y, x）, （z, x, y）, （y, x, z）, （y, z, x）, （x, z, y） B. A large set of disjoint PDTS（v, λ）, denoted by LPDTS（v, λ）, is a collection of 3（v - 2）/λ disjoint pure directed triple systems on X. In this paper, some results about the existence for LPDTS（v, λ） are presented. Especially, we determine the spectrum of LPDTS（v, 2）.     

Constructions for overlarge sets of disjoint pure directed triple systems

Let X be a v-set, v≥3. A transitive triple (x,y,z) on X is a set of three ordered pairs (x,y),(y,z) and (x,z) of X. A directed triple system of order v, denoted by DTS(v), is a pair (X,?), where X is a v-set and ? is a collection of transitive triples on X such that every ordered pair of X belongs to exactly one triple of ?. A DTS(v) is called pure and denoted by PDTS(v) if (x,y,z)∈? implies (z,y,x)??. An overlarge set of disjoint PDTS(v) is denoted by OLPDTS(v). In this paper, we establish some recursive constructions for OLPDTS(v), so we obtain some results.     

Handcuffed designs

Handcuffed designs are a particular case of block designs on graphs. A handcuffed design with parametersv, k, λ consists of a system of orderedk-subsets of av-set, called handcuffed blocks. In a block {A ₁,A ₂,?, A _k } each element is assumed to be handcuffed to its neighbours and the block containsk ? 1 handcuffed pairs (A ₁,A ₂), (A ₂,A ₃), ? (A _k?1,A _k ). These pairs are considered unordered. The collection of handcuffed blocks constitute a hundcuffed design if the following are satisfied: (1) each element of thev-set appears amongst the blocks the same number of times (and at most once in a block) and (2) each pair of distinct elements of thev-set are handcuffed in exactly λ of the blocks. If the total number of blocks isb and each element appears inr blocks the following conditions are necessary for the handcuffed design to exist:

1. λv(v?1) = (k?1) b,
2. rv = kb.

We denote byH(v, k, λ) the class of all handcuffed designs with parametersv, k, λ and sayH (v, k, λ) exists if there is a design with parametersv, k, λ. In this paper we prove that the necessary conditions forH (v, k, λ) exist are also sufficient in the following cases: (a)λ = 1 or 2; (b)k = 3; (c)k is evenk = 2h, and (λ, 2h ? 1) = 1; (d)k is odd,k = 2h + 1, and (λ, 4h)=2 or (λ, 4h)=1.     

Direct construction methods for incomplete perfect Mendelsohn designs with block size four

Let v, k, λ, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by (v,n,k,λ)-IPMD, is a triple (X,Y,B) where X is a v-set (of points), Y is an n-subset of X, and B is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a,b) E (X × X)\(Y × Y) appears t-apart in exactly λ blocks of B and no ordered pair (a,b) E Y × Y appears in any block of B for any t, where 1 ≤ t ≤ k − 1. In this article, we introduce an effective and easy way to construct IPMDs for k = 4 and even v − n, and use it to construct some small examples for λ = 1 and 2. Obviously, these results will play an important role to completely solve the existence of (v,n,4,λ)-IPMDs. Furthermore, we also use this method to construct some small examples for HPMDs. © 1996 John Wiley & Sons, Inc.     

On three-designs of small order

For positive integers t?k?v and λ we define a t-design, denoted B_i[k,λ;v], to be a pair (X,B) where X is a set of points and B is a family, (B_i:i?I), of subsets of X, called blocks, which satisfy the following conditions: (i) |X|=v, the order of the design, (ii) |B_i|=k for each i?I, and (iii) every t-subset of X is contained in precisely λ blocks. The purpose of this paper is to investigate the existence of 3-designs with 3?k?v?32 and λ>0.Wilson has shown that there exists a constant N(t, k, v) such that designs B_t[k,λ;v] exist provided λ>N(t,k,v) and λ satisfies the trivial necessary conditions. We show that N(3,k,v)=0 for most of the cases under consideration and we give a numerical upper bound on N(3, k, v) for all 3?k?v?32. We give explicit constructions for all the designs needed.     

Some infinite families of large sets of Kirkman triple systems

A large set of Kirkman triple systems of order v, denoted by LKTS(v), is a collection {(X, B_i) : 1 ≤ i ≤ v ? 2}, where every (X,B_i) is a KTS(v) and all B_i form a partition of all triples on X. Many researchers have studied the existence of LKTS(v) for a long time. In [13], the author introduced a concept—large set of generalized Kirkman systems (LGKS), which plays an important role in the discussion of LKTS. In this article, we give a new construction for LGKS and obtain some new results of LKTS, that is, there exists an LKTS(6u + 3) for u = qⁿ, where n ≥ 1, q ≡ 7 (mod 12) and q is a prime power. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 202–212, 2008     

t-designs on hypergraphs

A $\text{t-}\text{design}\text{T=(X,}\text{B}\text{)}$, denoted by (λ; t, k, v), is a system $\text{B}$ of subsets of size k from a v-set X, such that each t-subset of X is contained in exactly λ elements of $\text{B}$. A hypergraph $\text{H=(Y,}\text{E}\text{)}$ is a finite set Y where $\text{E}\text{=(E}{}_{\mathrm{i}}\text{: i?I)}$ is a family of subsets (which we assume here are distinct) of Y such that E_i≠Ø, i?l, and ?E_i=Y. Let G be an automorphism group of $\text{H=(Y,}\text{E}\text{)}$ where O^l_i is the ith orbit of l-subsets of $\text{E}$. Let A(G; H; t, k)= (a_ij) be an m by n matrix, where a_ij is the number of copies of O^t_i that occur in the system of all t-subsets of all elements of O^k_j. Then there is a t-design $\text{T=(X,}\text{B}\text{)}$ with $\text{X=}\text{E}$, with parameters (λ; t, k, v), and with G an automorphism groupof T iff there is an m by s submatrix M of A(G; H; t, k) where M has uniform row sums λ. The calculus for applying this theorem is illustrated and numerous t-designs for 10?v?16 are found and presented. Using a theorem of Alltop on our (12; 4, 6, 13) and (60; 4, 7, 15) we obtain a (12; 5, 7, 14) and a (60; 5, 8, 16).     

Self-converse Mendelsohn designs with block size 4t + 2

A Mendelsohn design MD(v, k, λ) is a pair (X, B) where X is a v-set together with a collection B of cyclic k-tuples from X such that each ordered pair from X, as adjacent entries, is contained in exactly λk-tuples of B. An MD(v, k, λ) is said to be self-converse, denoted by SCMD(v, k, λ) = (X, B, f), if there is an isomorphic mapping from (X, B) to (X, B⁻¹), where B⁻¹ = {B⁻¹ = 〈x_k, x_k−1, … x₂, x₁〉; B = 〈x₁, … ,x_k〉 ∈ B.}. The existence of SCMD(v, 3, λ) and SCMD(v, 4, 1) has been settled by us. In this article, we will investigate the existence of SCMD(v, 4t + 2, 1). In particular, when 2t + 1 is a prime power, the existence of SCMD(v, 4t + 2, 1) has been completely solved, which extends the existence results for MD(v, k, 1) as well. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 283–310, 1999     

Chaos caused by a strong-mixing measure-preserving transformation

The chaos caused by a strong-mixing preserving transformation is discussed and it is shown that for a topological spaceX satisfying the second axiom of countability and for an outer measurem onX satisfying the conditions: (i) every non-empty open set ofX ism-measurable with positivem-measure; (ii) the restriction ofm on Borel σ-algebra ℬ(X) ofX is a probability measure, and (iii) for everyY⊂X there exists a Borel setB⊂ℬ(X) such thatB⊃Y andm(B) =m(Y), iff:X→X is a strong-mixing measure-preserving transformation of the probability space (X, ℬ(X),m), and if {m}, is a strictly increasing sequence of positive integers, then there exists a subsetC⊂X withm (C) = 1, finitely chaotic with respect to the sequence {m _i}, i.e. for any finite subsetA ofC and for any mapF:A→X there is a subsequencer _i such that lim_i→∞ f ^r i(a) =F(a) for anya ∈A. There are some applications to maps of one dimension. the National Natural Science Foundation of China.     

Stabilization of unbounded bilinear control systems in Hilbert space

We consider bilinear control systems of the form y^′(t)=Ay(t)+u(t)By(t) where A generates a strongly continuous semigroup of contraction (etA)_t?0 on an infinite-dimensional Hilbert space Y whose scalar product is denoted by 〈.,.〉. We suppose that this system is unbounded in the sense that the linear operator B is unbounded from the state Y into itself. Tacking into account eventual control saturation, we study the problem of stabilization by (possibly nonquadratic) feedback of the form u(t)=−f(〈By(t),y(t)〉). Applications to the heat equation is considered.     

λ-fold indecomposable large sets of Steiner triple systems

A family (X, B1), (X, B2), . . . , (X, Bq) of q STS(v)s is a λ-fold large set of STS(v) and denoted by LSTSλ(v) if every 3-subset of X is contained in exactly λ STS(v)s of the collection. It is indecomposable and denoted by IDLSTSλ(v) if there exists no LSTSλ (v) contained in the collection for any λ λ. In 1995, Griggs and Rosa posed a problem: For which values of λ 1 and orders v ≡ 1, 3 (mod 6) do there exist IDLSTSλ(v)? In this paper, we use partitionable candelabra systems (PCSs) and holey λ-fold large set of STS(v) (HLSTSλ(v)) as auxiliary designs to establish a recursive construction for IDLSTSλ(v) and show that there exists an IDLSTSλ(v) for λ = 2, 3, 4 and v ≡ 1, 3 (mod 6).     

Indecomposable large sets of Steiner triple systems with indices 5, 6

A family ( X, B1 ), (X, B2 ), . . . , (X, Bq ) of q STS(v)s is a λ-fold large set of STS(v) and denoted by LSTS λ (v) if every 3-subset of X is contained in exactly λ STS(v)s of the collection. It is indecomposable and denoted by IDLSTS λ (v) if there does not exist an LSTS λ'(v) contained in the collection for any λ' λ. In this paper, we show that for λ = 5, 6, there is an IDLSTS λ (v) for v ≡ 1 or 3 (mod 6) with the exception IDLSTS6 (7).     

Perfect dexagon triple systems with given subsystems

The graph consisting of the six triples (or triangles) {a,b,c}, {c,d,e}, {e,f,a}, {x,a,y}, {x,c,z}, {x,e,w}, where a,b,c,d,e,f,x,y,z and w are distinct, is called a dexagon triple. In this case the six edges {a,c}, {c,e}, {e,a}, {x,a}, {x,c}, and {x,e} form a copy of K₄ and are called the inside edges of the dexagon triple. A dexagon triple system of order v is a pair (X,D), where D is a collection of edge disjoint dexagon triples which partitions the edge set of 3K_v. A dexagon triple system is said to be perfect if the inside copies of K₄ form a block design. In this note, we investigate the existence of a dexagon triple system with a subsystem. We show that the necessary conditions for the existence of a dexagon triple system of order v with a sub-dexagon triple system of order u are also sufficient.     

A Completion of the Spectrum for the Overlarge Sets of Pure Mendelsohn Triple Systems

A pure Mendelsohn triple system of order v, denoted by PMTS(v), is a pair \((X,\mathcal {B})\) where X is a v-set and \(\mathcal {B}\) is a collection of cyclic triples on X such that every ordered pair of X belongs to exactly one triple of \(\mathcal {B}\) and if \(\langle a,b,c\rangle \in \mathcal {B}\) implies \(\langle c,b,a\rangle \notin \mathcal {B}\). An overlarge set of PMTS(v), denoted by OLPMTS(v), is a collection \(\{(Y{\setminus }\{y_i\},{\mathcal {A}}_i)\}_i\), where Y is a \((v+1)\)-set, \(y_i\in Y\), each \((Y{\setminus }\{y_i\},{\mathcal {A}}_i)\) is a PMTS(v) and these \({\mathcal {A}}_i\)s form a partition of all cyclic triples on Y. It is shown in [3] that there exists an OLPMTS(v) for \(v\equiv 1,3\) (mod 6), \(v>3\), or \(v \equiv 0,4\) (mod 12). In this paper, we shall discuss the existence problem of OLPMTS(v)s for \(v\equiv 6,10\) (mod 12) and get the following conclusion: there exists an OLPMTS(v) if and only if \(v\equiv 0,1\) (mod 3), \(v>3\) and \(v\ne 6\).     

Embedding of a pseudo-residual design into a Möbius plane

Let $\text{U}$ be a class of subsets of a finite set X. Elements of $\text{U}$ are called blocks. Let v, t and λ₁, 0 ? i ? t, be nonnegative integers, and K be a subset of nonnegative integers such that every member of K is at most v. A pair (X, U) is called a (λ₀, λ₁,…, λ_t; K, υ)t-design if (1) |X| = υ, (2) every i-subset of X is contained in exactly λ_t blocks, 0 ? i ? t, and (3) for every block A in $\text{U}$, |A| ?K. It is well-known that if K consists of a singleton k, then λ₀,…, λ_{t ? 1} can be determined from υ, t, k and λ_t. Hence, we shall denote a (λ₀,…, λ_t; {k}, υ)t-design by S_λ(t, k, υ), where λ = λ_t. A Möbius plane M is an S₁(3, q + 1, q² + 1), where q is a positive integer. Let A be a fixed block in M. If A is deleted from M together with the points contained in A, then we obtain a residual design M′ with parameters λ₀ = q³ + q ? 1, λ₁ = q² + q, λ₂ = q + 1, λ₃ = 1, K = {q + 1, q, q ? 1}, and υ = q² ? 1. We define a design to be a pseudo-block-residual design of order q (abbreviated by PBRD(q)) if it has these parameters. We consider the reconstruction problem of a Möbius plane from a given PBRD(q). Let B and B′ be two blocks in a residual design M′. If B and B′ are tangent to each other at a point x, and there exists a block C of size q + 1 such that C is tangent to B at x and is secant to B′, then we say B is r-tangent to B′ at x. A PBRD(q) is said to satisfy the r-tangency condition if for every block B of size q, and any two points x and y not in B, there exists at most one block which is r-tangent to B and contains x and y. We show that any PBRD(q)D can be uniquely embedded into a Möbius plane if and only if D satisfies the r-tangency condition.     

Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

The characteristic polynomial of a principal subpencil of a Hermitian matrix pencil

Given n-square Hermitian matrices A,B, let A_i,B_i denote the principal (n?1)- square submatrices of A,B, respectively, obtained by deleting row i and column i. Let μ, λ be independent indeterminates. The first main result of this paper is the characterization (for fixed i) of the polynomials representable as det(μA_i?λB_i) in terms of the polynomial det(μA?λB) and the elementary divisors, minimal indices, and inertial signatures of the pencil μA?λB. This result contains, as a special case, the classical interlacing relationship governing the eigenvalues of a principal sub- matrix of a Hermitian matrix. The second main result is the determination of the number of different values of i to which the characterization just described can be simultaneously applied.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.