Exponential bounds on the number of designs with affine parameters

It is well‐known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n≥3, grows exponentially. This result was extended recently [D. Jungnickel, V. D. Tonchev, Des Codes Cryptogr, published online: 23 May, 2009] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2≤d≤n−1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n−1, as well as resolvable designs with these parameters. An exponential lower bound is also proved for the number of non‐isomorphic resolvable 3‐designs with the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, 2), for any 2≤d≤n−1. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 475–487, 2010     

α‐Resolvable group divisible designs with block size three

A group divisible design GD(k,λ,t;tu) is α‐resolvable if its blocks can be partitioned into classes such that each point of the design occurs in precisely α blocks in each class. The necessary conditions for the existence of such a design are λt(u ? 1) = r(k ? 1), bk = rtu, k|αtu and α|r. It is shown in this paper that these conditions are also sufficient when k = 3, with some definite exceptions. © 2004 Wiley Periodicals, Inc.     

Resolvable minimum coverings with quadruples

Let V be a finite set of v elements. A covering of the pairs of V by k-subsets is a family F of k-subsets of V, called blocks, such that each pair in V occurs in at least one member of F. For fixed v and k, the covering problem is to determine the number of blocks in any minimum covering. A minimum covering is resolvable if we can partition the blocks into classes (called resolution classes) such that every element is contained in precisely one block of each class. A resolvable minimum covering of the pairs of V by k-subsets is denoted by RC(v, k). In this article, we show that there exist RC(v, 4) for v ≡ 0 (mod 4) except for v = 12 and possibly for v ∈ {104, 108, 116, 132, 156, 164, 204, 212, 228, 276}. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 431–450, 1998     

Correction to: “Exponential bounds on the number of designs with affine parameters”

It is well known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n?3, grows exponentially. This result was extended recently [5] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2?d?n ? 1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n ? 1. Exponential bounds are also proved for the number of resolvable designs with these parameters. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:156‐166, 2011     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

Mixed block designs

Let V_i (i = 1, 2) be a set of size v_i. Let D be a collection of ordered pairs (b₁, b₂) where b_i is a k_i-element subset of V_i. We say that D is a mixed t-design if there exist constants λ _(j,j2), (0 ≤ j_i ≤ k_i, j₁ + j₂ ≤ t) such that, for every choice of a j₁-element subset S₁ of V₁ and every choice of a j₂-element subset S₂ of V₂, there exist exactly λ_(j1,j2) ordered pairs (b₁, b₂) in D satisfying S₁ ⊆ b₁ and S₂ ⊆ b₂. In W. J. Martin [Designs in product association schemes, submitted for publication], Delsarte's theory of designs in association schemes is extended to products of Q-polynomial association schemes. Mixed t-designs arise as a particularly interesting case. These include symmetric designs with a distinguished block and α-resolvable balanced incomplete block designs as examples. The theory in the above-mentioned paper yields results on mixed t-designs analogous to those known for ordinary t-designs, such as the Ray-Chaudhuri/Wilson bound. For example, the analogue of Fisher's inequality gives |D| ≥ v₁ + v₂ − 1 for mixed 2-designs with Bose's condition on resolvable designs as a special case. Partial results are obtained toward a classification of those mixed 2-designs D with |D| = v₁ + v₂ − 1. The central result of this article is Theorem 3.1, an analogue of the Assmus–Mattson theorem which allows us to construct mixed (t + 1 − s)-designs from any t-design with s distinct block intersection numbers. © 1998 John Wiley & Sons, Inc. J Combin Designs 6:151–163, 1998     

-Linked planar graphs

A graph G is (m,n)-linked if for any two disjoint subsets R,BV(G) with |R|m and |B|n, G has two disjoint connected subgraphs containing R and B, respectively. We shall prove that a planar graph with at least six vertices is (3,3)-linked if and only if G is 4-connected and maximal.     

Constructions for near resolvable designs and BIBDs

The purpose of this article is twofold. First, it is shown that classical inversive planes of even order can be used to construct a class of 2—(2²ⁿ + 1, 2ⁿ, 2ⁿ—1) near resolvable designs, in which any two blocks have at most 2 points in common. Secondly, it is shown that a recursive construction method for BIBDs using resolvable BIBDs due to Shrikhande and Raghavarao can be extended by using near resolvable designs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 227–231, 1999     

Quasi-Symmetric Designs with Good Blocks

The article is concerned with a characterization of quasi-symmetric (QS) designs with intersection numbers 0 and y. It uses the idea of a good block. Such a block G has the property that for any block B with |G ∩ B| = y, every point is on a block containing G ∩ B. It is proved that if a QS design II with intersection numbers 0 and y has a good block, then II must (i) be affine, symmetric, a linear space or (ii) have one of two possible exceptional parameter sets. Only one example is known in case (ii). If all blocks of II are good and II is not a linear space, then it is a projective or affine geometry or it is an extension (in a more general sense than usual) of a projective plane of order y² or y³+ y. © 1995 John Wiley & Sons, Inc.     

A hole‐size bound for incomplete t‐wise balanced designs

An incomplete t‐wise balanced design of index λ is a triple (X,H,??) where X is a υ–element set, H is a subset of X called the hole, and B is a collection of subsets of X called blocks, such that, every t‐element subset of X is either in H or in exactly λ blocks, but not both. If H is a hole in an incomplete t‐wise balanced design of order υ and index λ, then |H| ≤ υ/2 if t is odd and |H| ≤ (υ ? 1)/2 if t is even. In particular, this result establishes the validity of Kramer's conjecture that the maximal size of a block in a Steiner t‐wise balanced design is at most υ/2 if t is odd and at most (υ?1)/2 when t is even. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 269–284, 2001     

Some characterization of locally resistant BIB designs of degree one

Summary This paper investigates locally resistant balanced incomplete block (LRBIB) designs of degree one. A new necessary condition for the existence of such an LRBIB design is presented. This condition yields a complete characterization of affine α-resolvable LRBIB designs of degree one. Furthermore, regarding construction methods of LRBIB designs of degree one, it is shown that Shah and Gujarathi's method (1977,Sankhy?, B39, 406–408) yields the same parameters as Hedayat and John's method (1974,Ann. Statist.,2, 148–158), but their block structures are different and interesting. Partially supported by Grants 59540043 (C) and 60530014 (C).     

On the structure of 1-designs with at most two block intersection numbers

We introduce the notion of an unrefinable decomposition of a 1-design with at most two block intersection numbers, which is a certain decomposition of the 1-designs collection of blocks into other 1-designs. We discover an infinite family of 1-designs with at most two block intersection numbers that each have a unique unrefinable decomposition, and we give a polynomial-time algorithm to compute an unrefinable decomposition for each such design from the family. Combinatorial designs from this family include: finite projective planes of order n; SOMAs, and more generally, partial linear spaces of order (s, t) on (s + 1)² points; as well as affine designs, and more generally, strongly resolvable designs with no repeated blocks.      

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

A theorem of the alternatives for the equation Ax + B|x| = b

The following theorem is proved: given square matrices A, D of the same size, D nonnegative, then either the equation Ax?+?B|x|?=?b has a unique solution for each B with |B|?≤?D and for each b, or the equation Ax?+?B ₀|x|?=?0 has a nontrivial solution for some matrix B ₀ of a very special form, |B ₀|?≤?D; the two alternatives exclude each other. Some consequences of this result are drawn. In particular, we define a λ to be an absolute eigenvalue of A if |Ax|?=?λ|x| for some x?≠?0, and we prove that each square real matrix has an absolute eigenvalue.     

Diameter bounds for planar graphs

The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method, we begin by proving the simpler related upper bounds (4(|V|−1)−|E|)/3 and 4|V|²/3|E| on the diameter (for connected planar graphs), which are also tight.     

A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

Some Hadamard designs with parameters (71,35,17)

Up to isomorphisms there are precisely eight symmetric designs with parameters (71, 35, 17) admitting a faithful action of a Frobenius group of order 21 in such a way that an element of order 3 fixes precisely 11 points. Five of these designs have 84 and three have 420 as the order of the full automorphism group G. If |G| = 420, then the structure of G is unique and we have G = (Frob₂₁ × Z5):Z4. In this case Z(G) = 〈1〉, G′ has order 35, and G induces an automorphism group of order 6 of Z7. If |G| = 84, then Z(G) is of order 2, and in precisely one case a Sylow 2‐subgroup is elementary abelian. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 144–149, 2002; DOI 10.1002/jcd.996     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Edge-connectivity in p-partite graphs

Let G = (V, E) be a finite, simple p-partite graph with minimum degree δ and edge-connectivity γ. It is proved that if |V| ? (2pδ)/(p - 1) - 2 or in special cases that if |V| ? (2pδ)/(p - 1) - 1, then λ = δ. It is further shown that this result is best possible.     

Existential closure of block intersection graphs of infinite designs having infinite block size

A graph G is n ‐existentially closed ( n ‐e.c.) if for each pair ( A, B ) of disjoint subsets of V(G) with | A | + | B |≤ n there exists a vertex in V ( G )\( A ∪ B ) which is adjacent to each vertex in A and to no vertex in B . In this paper we study the n ‐existential closure property of block intersection graphs of infinite designs with infinite block size. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:317‐327, 2011