Small Uniformly Resolvable Designs for Block Sizes 3 and 4

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k‐pc and for a given k the number of k‐pcs is denoted r_k. In this paper, we consider the case of block sizes 3 and 4 (both existent). We use v to denote the number of points, in this case the necessary conditions imply that v ≡ 0 (mod 12). We prove that all admissible URDs with v < 200 points exist, with the possible exceptions of 13 values of r₄ over all permissible v. We obtain a URD({3, 4}; 276) with r₄ = 9 by direct construction use it to and complete the construction of all URD({3, 4}; v) with r₄ = 9. We prove that all admissible URDs for v ≡ 36 (mod 144), v ≡ 0 (mod 60), v ≡ 36 (mod 108), and v ≡ 24 (mod 48) exist, with a few possible exceptions. Recently, the existence of URDs for all admissible parameter sets with v ≡ 0 (mod 48) was settled, this together with the latter result gives the existence all admissible URDs for v ≡ 0 (mod 24), with a few possible exceptions.     

Uniformly resolvable designs with index one, block sizes three and five and up to five parallel classes with blocks of size five

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size k (denoted k-pc). The number of k-pcs is denoted r_k. The necessary conditions for URDs with v points, index one, blocks of size 3 and 5, and r₃,r₅>0, are . If r_k>1, then v≥k², and r₃=(v−1−4⋅r₅)/2. For r₅=1 these URDs are known as group divisible designs. We prove that these necessary conditions are sufficient for r₅=3 except possibly v=105, and for r₅=2,4,5 with possible exceptions (v=105,165,285,345) New labeled frames and labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs.     

Uniformly resolvable designs with index one and block sizes three and four — with three or five parallel classes of block size four

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size. A URD with v points and with block sizes three and four means that at least one parallel class has block size three and at least one has block size four. Danziger [P. Danziger, Uniform restricted resolvable designs with r=3, ARS Combin. 46 (1997) 161-176] proved that for all there exist URDs with index one, some parallel classes of block size three, and exactly three parallel classes with block size four, except when v=12 and except possibly when . We extend Danziger’s work by showing that there exists a URD with index one, some parallel classes with block size three, and exactly three parallel classes with block size four if, and only if, , v≠12. We also prove that there exists a URD with index one, some parallel classes of block size three, and exactly five parallel classes with block size four if, and only if, , v≠12. New labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs. Some ingredient URDs are also constructed with difference families.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Double Arrays,Triple Arrays and Balanced Grids with <Emphasis Type="Italic">v</Emphasis>=<Emphasis Type="Italic">r</Emphasis>+<Emphasis Type="Italic">c</Emphasis> −1

In Theorem 6.1 of McSorley et al. [3] it was shown that, when v=r+c−1, every triple array TA(v,k,λ_rr,λ_cc,k:r× c) is a balanced grid BG(v,k,k:r × c). Here we prove the converse of this Theorem. Our final result is: Let v=r+c−1. Then every triple array is a TA(v,k,c−k,r−k,k:r× c) and every balanced grid is a BG(v,k,k:r× c), and they are equivalent.Communicated by: J.D. Key     

Covering arrays of strength 3 and 4 from holey difference matrices

A covering array CA(N; t, k, v) is an N × k array with entries from a set X of v symbols such that every N × t sub-array contains all t-tuples over X at least once, where t is the strength of the array. The minimum size N for which a CA(N; t, k, v) exists is called the covering array number and denoted by CAN(t, k, v). Covering arrays are used in experiments to screen for interactions among t-subsets of k components. One of the main problems on covering arrays is to construct a CA(N; t, k, v) for given parameters (t, k, v) so that N is as small as possible. In this paper, we present some constructions of covering arrays of strengths 3 and 4 via holey difference matrices with prescribed properties. As a consequence, some of known bounds on covering array number are improved. In particular, it is proved that (1) CAN(3, 5, 2v) ≤ 2v ²(4v + 1) for any odd positive integer v with gcd(v, 9) ≠ 3; (2) CAN(3, 6, 6p) ≤ 216p ³ + 42p ² for any prime p > 5; and (3) CAN(4, 6, 2p) ≤ 16p ⁴ + 5p ³ for any prime p ≡ 1 (mod 4) greater than 5.     

On the Stabilizer of the Automorphism Group of a 4—valent Vertex—transitive Graph with Odd—prime—power Order

Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^κ（κ≥1） and let A be the full automorphism group of X.In this paper,we prove that the stabilizer Av of a vertex v in A is a 2-group if p≠5,or a {2,3}-group if p=5.Furthermore,if p=5|Av| is not divisible by 3^2.As a result ,we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p^κ(κ≥1） is at most 1-arc-transitive for p≠5 and 2-arc-transitive for p=5.     

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     

A regularity criterion for axially symmetric solutions to the Navier–Stokes equations

The axially symmetric solutions to the Navier–Stokes equations are studied. Assume that either the radial component (v _r ) of the velocity belongs to L _∞(0, T;L ₃(Ω₀)) or v _r /r belongs to L _∞(0, T;L _3/2(Ω₀)), where Ω₀ is a neighborhood of the axis of symmetry. Assume additionally that there exist subdomains Ω _k , k = 1, . . . , N, such that W₀ ì è_{k = 1}^N W_k {\Omega_0} \subset \bigcup\limits_{k = 1}^N {{\Omega_k}} , and assume that there exist constants α ₁, α ₂ such that either || v_r ||_{L￥ ( 0,T;L3( Wk ) )} ￡ a₁ or  || \fracv_rr ||_{L￥ ( 0,T;L3/2( Wk ) )} ￡ a₂ {\left\| {{v_r}} \right\|_{{L_\infty }\left( {0,T;{L_3}\left( {{\Omega_k}} \right)} \right)}} \leq {\alpha_1}\,or\;{\left\| {\frac{{{v_r}}}{r}} \right\|_{{L_\infty }\left( {0,T;{L_{3/2}}\left( {{\Omega_k}} \right)} \right)}} \leq {\alpha_2} for k = 1, . . . , N. Then the weak solution becomes strong ( v ? W₂^2,1( W×( 0,T ) ),?p ? L₂( W×( 0,T ) ) ) \left( {v \in W_2^{2,1}\left( {\Omega \times \left( {0,T} \right)} \right),\nabla p \in {L_2}\left( {\Omega \times \left( {0,T} \right)} \right)} \right) . Bibliography: 28 titles.     

Further results on overlarge sets of Kirkman triple systems

In this paper, we introduce a new concept -- overlarge sets of generalized Kirkman systems （OLGKS）, research the relation between it and OLKTS, and obtain some new results for OLKTS. The main conclusion is： If there exist both an OLKF（6^k） and a 3-OLGKS（6^k-1,4） for all k ∈{6,7,...,40}／{8,17,21,22,25,26}, then there exists an OLKTS（v） for any v ≡ 3 （mod 6）, v ≠ 21. As well, we obtain the following result： There exists an OLKTS（6u ＋ 3） for u = 2^2n-1 - 1, 7^n, 31^n, 127^n, 4^r25^s, where n ≥ 1,r＋s≥ 1.     

Existence of a-fold Perfect （v, {5, 8}, 1）-Mendelsohn Designs

Let v be a positive integer and let K be a set of positive integers. A （v, K, 1）-Mendelsohn design, which we denote briefly by （v, K, 1）-MD, is a pair （X, B） where X is a v-set （of points） and B is a collection of cyclically ordered subsets of X （called blocks） with sizes in the set K such that every ordered pair of points of X are consecutive in exactly one block of B. If for all t =1, 2,..., r, every ordered pair of points of X are t-apart in exactly one block of B, then the （v, K, 1）-MD is called an r-fold perfect design and denoted briefly by an r-fold perfect （v, K, 1）-MD. If K = {k） and r = k - 1, then an r-fold perfect （v, （k）, 1）-MD is essentially the more familiar （v, k, 1）-perfect Mendelsohn design, which is briefly denoted by （v, k, 1）-PMD. In this paper, we investigate the existence of 4-fold perfect （v, （5, 8}, 1）-Mendelsohn designs.     

The game for the speed of convergence in repeated games of incomplete information

We consider an infinitely repeated two-person zero-sum game with incomplete information on one side, in which the maximizer is the (more) informed player. Such games have value v _∞ (p) for all 0≤p≤1. The informed player can guarantee that all along the game the average payoff per stage will be greater than or equal to v _∞ (p) (and will converge from above to v _∞ (p) if the minimizer plays optimally). Thus there is a conflict of interest between the two players as to the speed of convergence of the average payoffs-to the value v _∞ (p). In the context of such repeated games, we define a game for the speed of convergence, denoted SG _∞ (p), and a value for this game. We prove that the value exists for games with the highest error term, i.e., games in which v _n (p)− v _∞ (p) is of the order of magnitude of . In that case the value of SG _∞ (p) is of the order of magnitude of . We then show a class of games for which the value does not exist. Given any infinite martingale 𝔛^∞={X _k }^∞ _k=1, one defines for each n : V _n (𝔛^∞) ≔E∑ⁿ _k=1 |X _k+1 − X _k|. For our first result we prove that for a uniformly bounded, infinite martingale 𝔛^∞, V _n (𝔛^∞) can be of the order of magnitude of n ^1/2−ε, for arbitrarily small ε>0. Received January 1999/Final version April 2002     

2-Colored triangles in edge-colored complete graphs, II

The largest number n = n(k) for which there exists a k-coloring of the edges of k_n with every triangle 2-colored is found to be n(k) = 2^r5^m, where k = 2m + r and r = 0 or 1, and all such colorings are given. We also prove the best possible result that a k-colored K_p satisfying 1 < k < 1 + √p contains at most k − 2 vertices not in a bichromatic triangle.     

The minimal number of circuits in a finite set inR 2k−1

The minimal number of circuits (i.e., minimal affinely dependent subsets) in a set ofs points inR ^2k−1 isr( ₃ ⁴ )+(k−r)( ₃ ^4⋅1 ) as conjectured by J.-P. Doignon, wheres=qk+r, 0≦r<q.     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

A bound for Wilson's theorem (II)

In this article we prove the following theorem. For any k ≥ 3, let c(k, 1) = exp{exp{k^k2}}. If v(v − 1) ≡ 0 (mod k(k −1)) and v − 1 ≡ 0 (mod k−1) and v > c(k, 1), then a B(v,k, 1) exists. © 1996 John Wiley & Sons, Inc.     

On symmetric ��-configurations with small ��

In this paper, we focus on the existence of symmetric λ-configurations with λ = 2, 3, and 4. Three new spatial configurations (v ₈)₂ for v = 30, 31, and 32 are constructed. The existence of a spatial configuration (v _k )₂ are updated for k ⩽ 10. The existence tables for symmetric λ-configurations for λ = 3, 4, and small k are also given.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Schur–Weyl duality over finite fields

We prove a version of the Schur–Weyl duality over finite fields. We prove that for any field k, if k has at least r + 1 elements, the Schur–Weyl duality holds for the rth tensor power of a finite dimensional vector space V. Moreover, if the dimension of V is at least r + 1, the natural map ${{k\mathfrak{S}_r \to \mathsf{End}_{{\rm GL}(V)}(V^{\otimes r})}}We prove a version of the Schur–Weyl duality over finite fields. We prove that for any field k, if k has at least r + 1 elements, the Schur–Weyl duality holds for the rth tensor power of a finite dimensional vector space V. Moreover, if the dimension of V is at least r + 1, the natural map k\mathfrakS_r ? End_GL(V)(V^?r){{k\mathfrak{S}_r \to \mathsf{End}_{{\rm GL}(V)}(V^{\otimes r})}} is an isomorphism. This isomorphism may fail if dim _k V is not strictly larger than r.     

P4k?1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k−1-factorization of λK _m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer.