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.     

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.     

Minimum Covering for Hexagon Triple Systems

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c,z,a), where a, b, c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b,y,c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kK ⁿ with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kK ⁿ with hexagon triples is a triple (X, H, P) such that: 1.3kK ⁿ has vertex set X. 2.P is a subset of E(λ K ⁿ ) with vertex set X for some λ, and 3.H is an edge disjoint partition of E(3kK ⁿ )∪ P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kK ⁿ with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kK ⁿ with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kK ⁿ with hexagon triples was given recently by the authors [2]. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kK ⁿ with hexagon triples.     

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.     

Cyclic antiautomorphisms of directed triple systems

A transitive triple, (a,b,c), is defined to be the set {(a,b), (b,c), (a,c)} of ordered pairs. A directed triple system of order v, DTS(v), is a pair (D,β), where D is a set of v points and β is a collection of transitive triples of pairwise distinct points of D such that any ordered pair of distinct points of D is contained in precisely one transitive triple of β. An antiautomorphism of a Directed triple system, (D,β), is a permutation of D that maps β to β⁻¹, where β ⁻¹ = {(c,b,a)|(a,b,c) E β}. In this article we give necessary and sufficient conditions for the existence of a Directed triple system of order v admitting an antiautomorphism consisting of a single cycle of length d and having v − d fixed points. Further, we give a more general result for partial Directed triple systems in which the missing ordered pairs are precisely those containing two fixed points. © 1996 John Wiley & Sons, Inc.     

On tortkara triple systems

The commutator [a,b] = ab?ba in a free Zinbiel algebra (dual Leibniz algebra) is an anticommutative operation which satisfies no new relations in arity 3. Dzhumadildaev discovered a relation T(a,b,c,d) which he called the tortkara identity and showed that it implies every relation satisfied by the Zinbiel commutator in arity 4. Kolesnikov constructed examples of anticommutative algebras satisfying T(a,b,c,d) which cannot be embedded into the commutator algebra of a Zinbiel algebra. We consider the tortkara triple product [a,b,c] = [[a,b],c] in a free Zinbiel algebra and use computer algebra to construct a relation TT(a,b,c,d,e) which implies every relation satisfied by [a,b,c] in arity 5. Thus, although tortkara algebras are defined by a cubic binary operad (with no Koszul dual), the corresponding triple systems are defined by a quadratic ternary operad (with a Koszul dual). We use computer algebra to construct a relation in arity 7 satisfied by [a,b,c] which does not follow from the relations of lower arity. It remains an open problem to determine whether there are further new identities in arity n≥9.     

Trails of triples in partial triple systems

Given v, t, and m, does there exist a partial Steiner triple system of order v with t triples whose triples can be ordered so that any m consecutive triples are pairwise disjoint? Given v, t, and m ₁, m ₂, . . . , m _s with ${t = \sum_{i=1}^s m_i}$ , does there exist a partial Steiner triple system with t triples whose triples can be partitioned into partial parallel classes of sizes m ₁, . . . , m _s ? An affirmative answer to the first question gives an affirmative answer to the second when m _i ≤ m for each ${i \in \{1,2,\ldots,s\}}$ . These questions arise in the analysis of erasure codes for disk arrays and that of codes for unipolar communication, respectively. A complete solution for the first problem is given when m is at most ${\frac{1}{3}\left(v-(9v)^{2/3}\right)+{O}\left(v^{1/3}\right)}$ .     

The spectrum for overlarge sets of hybrid triple systems

A hybrid triple system of order v and index λ,denoted by HTS(v,λ),is a pair(X,B) where X is a v-set and B is a collection of cyclic triples and transitive triples on X,such that every ordered pair of X belongs to λ triples of B. An overlarge set of disjoint HTS(v,λ),denoted by OLHTS(v,λ),is a collection {(Y \{y},Ai)}i,such that Y is a(v+1)-set,each(Y \{y},Ai) is an HTS(v,λ) and all Ais form a partition of all cyclic triples and transitive triples on Y.In this paper,we shall discuss the existence problem of OLHTS(v,λ) and give the following conclusion: there exists an OLHTS(v,λ) if and only if λ=1,2,4,v ≡ 0,1(mod 3) and v≥4.     

Some new perfect Steiner triple systems

In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph G_a,b can be defined as follows. The vertices of G_a,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999     

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Let ? = 〈a, b|a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b〉 be the discrete Heisenberg group, equipped with the left-invariant word metric d _W (·, ·) associated to the generating set {a, b, a ^?1, b ^?1}. Letting B _n = {x ∈ ?: d _W (x, e _?) ? n} denote the corresponding closed ball of radius n ∈ ?, and writing c = [a, b] = aba ^?1 b ^?1, we prove that if (X, ‖ · ‖X) is a Banach space whose modulus of uniform convexity has power type q ∈ [2,∞), then there exists K ∈ (0, ∞) such that every f: ? → X satisfies $$\sum\limits_{k = 1}^{{n^2}} {\sum\limits_{x \in {B_n}} {\frac{{\left\| {f(x{c^k}) - f(x)} \right\|_X^q}}{{{k^{1 + q/2}}}}} } \leqslant K\sum\limits_{x \in {B_{21n}}} {(\left\| {f(xa) - f(x)} \right\|_X^q + \left\| {f(xb) - f(x)} \right\|_X^q)} $$ . It follows that for every n ∈ ? the bi-Lipschitz distortion of every f: B _n → X is at least a constant multiple of (log n)^1/q , an asymptotically optimal estimate as n → ∞.     

Embedding partial triple systems

The main result of this paper is that any partial triple system (S, B) of index λ on n points can be embedded in a triple system of any odd λ-admissible order greater than 4n. Furthermore, if the minimum degree, maximum degree and total number of edges in the missing-edge graph of (S, B) satisfy certain bounds, then (S, B) can be embedded in a triple system of order 2n + 1, provided 2n + 1 is λ-admissible. It is also shown that there exists an equitable partial triple system of index λ containing ν triples on n points for any ν ⩽ μ(n, λ).     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

On Olaleru’s open problem on Gregus fixed point theorem

Let (X, d) be a complete metric space and ${TX \longrightarrow X }$ be a mapping with the property d(Tx, Ty) ≤ ad(x, y) + bd(x, Tx) + cd(y, Ty) + ed(y, Tx) + fd(x, Ty) for all ${x, y \in X}$ , where 0 < a < 1, b, c, e, f ≥ 0, a + b + c + e + f = 1 and b + c > 0. We show that if e + f > 0 then T has a unique fixed point and also if e + f ≥ 0 and X is a closed convex subset of a complete metrizable topological vector space (Y, d), then T has a unique fixed point. These results extend the corresponding results which recently obtained in this field. Finally by using our main results we give an answer to the Olaleru’s open problem.     

Directed triple systems

Directed triple systems are an example of block designs on directed graphs. A block design on a directed graph can be defined as follows. Let G be a directed graph of k vertices which contain no loops. Let S be a set of υ elements. A collection of k-subsets of S with an assignment of the elements of each k-subset to the vertices of G is called a block design on G of order υ if the following is satisfied. Any ordered pair of elements of S is assigned λ times to an edge of G.For example, if S = {a, b, c, d, e} and

and bae; cad; abc; dbe; acd; bce; adb; cde; aed; bec; is a collection of 3-subsets so written that in each subset the first element is assigned to the vertex 1, the second to 2, and the third to 3, then the collection is a block design on G with λ = 1.In this paper, it is shown that for the graph

if λ = 1, then the graph exists for all υ such that ν ? 2 mod 3.     

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 .

     

Probabilities of dominant candidates based on first-place votes

Suppose each of an odd number n of voters has a strict preference order on the three ‘candidates’ in {1,2,3} and votes for his most preferred candidate on a plurality ballot. Assume that a voter who votes for i is equally likely to have ijk and ikj as his preference order when {i,j,k} = {1,2,3}.Fix an integer m between $\text{1}\text{2}$(n + 1) and n inclusive. Then, given that n_i of the n voters vote for i, let f_m(n₁,n₂,n₃) be the probability that one of the three candidates is preferred by m or more voters to each of the other two.This paper examines the behavior of f_m over the lattice points in L_n, the set of triples of non-negative integers that sum to n. It identifies the regions in L_n where f_m is 1 and where f_m is 0, then shows that f_m(a,b + 1, c)>f_m(a + 1,b,c) whenever a + b + c + 1 = n, a≤c≤b, a<c<m and c≤n ? m. These results are used to partially identify the points in L_n where f_m is minimized subject to f_m>0. It is shown that at least two of the n_i are equal at minimizing points.     

Hanani triple systems

Hanani triple systems onv≡1 (mod 6) elements are Steiner triple systems having (v−1)/2 pairwise disjoint almost parallel classes (sets of pairwise disjoint triples that spanv−1 elements), and the remaining triples form a partial parallel class. Hanani triple systems are one natural analogue of the Kirkman triple systems onv≡3 (mod 6) elements, which form the solution of the celebrated Kirkman schoolgirl problem. We prove that a Hanani triple system exists for allv≡1 (mod 6) except forv ∈ {7, 13}.     

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.     

A note on random walk in random scenery

We consider a random walk in random scenery {Xn=η(S₀)+?+η(Sn),n∈N}, where a centered walk {Sn,n∈N} is independent of the scenery {η(x),x∈Zd}, consisting of symmetric i.i.d. with tail distribution P(η(x)>t)∼exp(−cαtα), with 1?α<d/2. We study the probability, when averaged over both randomness, that {Xn>ny} for y>0, and n large. In this note, we show that the large deviation estimate is of order exp(−ca(ny)), with a=α/(α+1).     

On Non-Essential Edges in 3-Connected Graphs

 An edge e in a simple 3-connected graph is deletable (simple-contractible) if the deletion G\e (contraction G/e) is both simple and 3-connected. Suppose a, b, and c are three non-negative integers. If there exists a simple 3-connected graph with exactly a edges which are deletable but not simple-contractible, exactly b edges which are simple-contractible but not deletable, and exactly c edges which are both deletable and simple-contractible, then we call the triple (a, b, c) realizable, and such a graph is said to be an (a, b, c)-graph. Tutte's Wheels Theorem says the only (0, 0, 0)-graphs are the wheels. In this paper, we characterize the (a, b, c) realizable triples for which at least one of a + b≤2, c=0, and c≥16 holds. Received: February 12, 1997 Revised: February 13, 1998