A Combinatorial Construction for Perfect Deletion-Correcting Codes

By a T ^*(2, k, v)-code we mean a perfect(k-2)-deletion-correcting code of length k over an alphabet ofsize v, which is capable of correcting any combination of up to(k-2) deletions and insertions of letters occured in transmission ofcodewords. In this paper, we provide a combinatorial construction forT ^*(2, k, v-codes. As an application, we show that aT ^*(2, 6, v-code exists for all positive integersv 3 (mod 5), with at most 12 possible exceptions of v. In theprocedure, a result on incomplete directed BIBDs is also established which is ofinterest in its own right.     

Existence of Perfect 4-Deletion-Correcting Codes with Length Six

By a T ^*(2, k, v)-code we mean a perfect4-deletion-correcting code of length 6 over an alphabet of size v, which is capable of correcting anycombination of up to 4 deletions and/or insertions of letters that occur in transmission of codewords. Thethird author (DCC Vol. 23, No. 1) presented a combinatorial construction for such codes and prove thata T ^*(2, 6, v)-code exists for all positive integers v 3 (mod 5), with 12 possible exceptions of v. In this paper, the notion of a directedgroup divisible quasidesign is introduced and used to show that a T ^*(2, 6,v)-code exists for all positive integers v 3 (mod 5), except possiblyfor v {173, 178, 203, 208}. The 12 missing cases for T ^*(2,6, v)-codes with v 3 (mod 5) are also provided, thereby the existenceproblem for T ^*(2, 6, v)-codes is almost complete.     

Groups and C*‐Algebras from a 4‐Dimensional Anzai Flow

The rotation flow on the circle T gives a concrete representation of the irrational rotation algebra, which is an in finite dimensional simple quotient of the group C*‐algebra of the discrete Heisenberg group H₃ analogously certain 2‐ and 3‐dimensional Anzai flows on T ² and T ³are known to give concrete representations of the corresponding quotients of the group C*‐algebras of the groups H₄ and H_5,5. Considered here is the (minimal, effective) 4‐dimensional Anzai flow F = (ℤ, T ⁴) generated by the homeomorphism (y, x, w, v) ↦ (λy, yx, xw, wv); a group H_6,10 is determined by F the faithful in finite dimensional simple quotients of whose group C*‐algebra C*‐(H_6,10 have concrete representations given by F. Furthermore, the rest of the infinite dimensional simple quotients of C*‐(H_6,10 are identified and displayed as C*‐crossed products generated by minimal effective actions and also as matrix algebras over simple C*‐algebras from groups of lower dimension; these lower dimensional groups are H₃ and subgroups of H₄ and H_5,5.     

Ternary codes of steiner triple systems

The code over a finite field F^q of a design ?? is the space spanned by the incidence vectors of the blocks. It is shown here that if ?? is a Steiner triple system on v points, and if the integer d is such that 3^d ≤ v < 3^d+1, then the ternary code C of ?? contains a subcode that can be shortened to the ternary generalized Reed-Muller code ?_F3(2(d ? 1),d) of length 3^d. If v = 3^d and d ≥ 2, then C_? ? ?_F3(1,d)? ? _F3(2(d ? 1),d) ? C. © 1994 John Wiley & Sons, Inc.     

Random walks on the torus with several generators

Given n vectors {_i} ∈ [0, 1)^d, consider a random walk on the d‐dimensional torus ??^d = ?^d/?^d generated by these vectors by successive addition and subtraction. For certain sets of vectors, this walk converges to Haar (uniform) measure on the torus. We show that the discrepancy distance D(Q*^k) between the kth step distribution of the walk and Haar measure is bounded below by D(Q*^k) ≥ C₁k^?n/2, where C₁ = C(n, d) is a constant. If the vectors are badly approximated by rationals (in a sense we will define), then D(Q*^k) ≤ C₂k^?n/2d for C₂ = C(n, d, _j) a constant. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.     

Generalized Steiner systems GS4 (2, 4, v,g) for g = 2, 3, 6

Generalized Steiner systems GS_d(t, k, v, g) were first introduced by Etzion and used to construct optimal constant‐weight codes over an alphabet of size g + 1 with minimum Hamming distance d, in which each codeword has length v and weight k. Much work has been done for the existence of generalized Steiner triple systems GS(2, 3, v, g). However, for block size four there is not much known on GS_d(2, 4, v, g). In this paper, the necessary conditions for the existence of a GS_d(t, k, v, g) are given, which answers an open problem of Etzion. Some singular indirect product constructions for GS_d(2, k, v, g) are also presented. By using both recursive and direct constructions, it is proved that the necessary conditions for the existence of a GS₄(2, 4, v, g) are also sufficient for g = 2, 3, 6. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 401–423, 2001     

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

The partition of a strong tournament

A digraph T is strong if for every pair of vertices u and v there exists a directed path from u to v and a directed path from v to u. Denote the in-degree and out-degree of a vertex v of T by d^-(v) and d⁺(v), respectively. We define δ^-(T)=min_vV(T){d^-(v)} and δ⁺(T)=min_vV(T){d⁺(v)}. Let T₀ be a 7-tournament which contains no transitive 4-subtournament. In this paper, we obtain some conditions on a strong tournament which cannot be partitioned into two cycles. We show that a strong tournament T with n6 vertices such that TT₀ and max{δ⁺(T),δ^-(T)}3 can be partitioned into two cycles. Finally, we give a sufficient condition for a tournament to be partitioned into k cycles.     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

The number of pancyclic arcs in a k‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D, if it belongs to a cycle of length l, for all 3 ≤ l ≤ |V (D) |. Let p(D) denote the number of pancyclic arcs in a digraph D and let h(D) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D. Note that p(D) ≥ h(D). Moon showed that h(T) ≥ 3 for all strong non‐trivial tournaments, T, and Havet showed that h(T) ≥ 5 for all 2‐strong tournaments T. We will show that if T is a k‐strong tournament, with k ≥ 2, then p(T) ≥ 1/2, nk and h(T) ≥ (k + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α_k, such that p(T) ≥ α_k n, for all k‐strong tournaments, T, with k ≥ 2. Furthermore, the second results gives support for the conjecture h(T) ≥ 2k + 1, which was also stated by Havet. The previously best‐known bounds when k ≥ 2 were p(T) ≥ 2k + 3 and h(T) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory     

4‐*GDDs(3n) and generalized Steiner systems GS(2, 4, v, 3)

Generalized Steiner systems GS(2, k, v, g) were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 2k ? 3, in which each codeword has length v and weight k. As to the existence of a GS(2, k, v, g), a lot of work has been done for k = 3, while not so much is known for k = 4. The notion k‐*GDD was first introduced and used to construct GS(2, 3, v, 6). In this paper, singular indirect product (SIP) construction for GDDs is modified to construct GS(2, 4, v, g) via 4‐*GDDs. Furthermore, it is proved that the necessary conditions for the existence of a 4‐*GDD(3ⁿ), namely, n ≡ 0, 1 (mod 4) and n ≥ 8 are also sufficient. The known results on the existence of a GS(2, 4, v, 3) are then extended. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 381–393, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10047     

Monomorphism Operator and Perpendicular Operator

For a quiver Q, a k-algebra A, and an additive full subcategory 𝒳 of A-mod, the monomorphism category Mon(Q, 𝒳) is introduced. The main result says that if T is an A-module such that there is an exact sequence 0 → T _m  → … → T ₀ → D(A _A ) → 0 with each T _i  ∈ add(T), then Mon(Q, ^⊥ T) =^⊥(kQ ? _k T); and if T is cotilting, then kQ ? _k T is a unique cotilting Λ-module, up to multiplicities of indecomposable direct summands, such that Mon(Q, ^⊥ T) =^⊥(kQ ? _k T).

As applications, the category of the Gorenstein-projective (kQ ? _k A)-modules is characterized as Mon(Q, 𝒢𝒫(A)) if A is Gorenstein; the contravariantly finiteness of Mon(Q, 𝒳) can be described; and a sufficient and necessary condition for Mon(Q, A) being of finite type is given.     

Cyclic k‐cycle systems of order 2kn + k: A solution of the last open cases

We exhibit cyclic (K_v, C_k)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (K_v, C_k)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004.     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

On the square root of a positive B( )-valued function

Let (Ω, , μ) be a measure space, a separable Banach space, and ^* the space of all bounded conjugate linear functionals on . Let f be a weak^* summable positive B( ^*)-valued function defined on Ω. The existence of a separable Hilbert space , a weakly measurable B( )-valued function Q satisfying the relation Q^*(ω)Q(ω) = f(ω) is proved. This result is used to define the Hilbert space L_2,f of square integrable operator-valued functions with respect to f. It is shown that for B⁺( ^*)-valued measures, the concepts of weak^*, weak, and strong countable additivity are all the same. Connections with stochastic processes are explained.     

Prime ideals in the C*-algebra of a nilpotent group

We say that a locally compact groupG hasT ₁ primitive ideal space if the groupC ^*-algebra,C ^*(G), has the property that every primitive ideal (i.e. kernel of an irreducible representation) is closed in the hull-kernel topology on the space of primitive ideals ofC ^*(G), denoted by PrimG. This means of course that every primitive ideal inC ^*(G) is maximal. Long agoDixmier proved that every connected nilpotent Lie group hasT ₁ primitive ideal space. More recentlyPoguntke showed that discrete nilpotent groups haveT ₁ primitive ideal space and a few month agoCarey andMoran proved the same property for second countable locally compact groups having a compactly generated open normal subgroup. In this note we combine the methods used in [3] with some ideas in [9] and show that for nilpotent locally compact groupsG, having a compactly generated open normal subgroup, closed prime ideals inC ^*(G) are always maximal which implies of course that PrimG isT ₁.