Some rigid Steiner 5‐designs

Hitherto, all known non‐trivial Steiner systems S(5, k, v) have, as a group of automorphisms, either PSL(2, v−1) or PGL(2, (v−2)/2) × C₂. In this article, systems S(5, 6, 72), S(5, 6, 84) and S(5, 6, 108) are constructed that have only the trivial automorphism group. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:392–400, 2010     

A S(3, {4, 6}, 18) with a subdesign S(3, 4, 8) does not exist

For , a S(t,K,v) design is a pair, , with |V| = v and a set of subsets of V such that each t‐subset of V is contained in a unique and for all . If , , , and is a S(t,K,u) design, then we say has a subdesign on U. We show that a S(3,{4,6},18) design with a subdesign S(3,4,8) does not exist. © 2007 Wiley Periodicals, Inc. J Combin Designs 17: 36–38, 2009     

A Remark on Hamiltonian Cycles

Let G be an undirected and simple graph on n vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of G. G is called a 1-tough graph if ω(G – S) ? |S| for any subset S of V(G) such that ω(G ? S) > 1. Let σ₂ = min {d(v) + d(w)|v and w are nonadjacent}. Note that the difference α - χ in 1-tough graph may be made arbitrary large. In this paper we prove that any 1-tough graph with σ₂ > n + χ - α is hamiltonian.     

A construction for large sets of disjoint Kirkman triple systems

A Steiner system S(t, k, v) is called i-resolvable, 0 < i < t, if its block set can be partitioned into S(i, k, v). In this paper, a 2-resolvable S(3, 4, v) is used to construct a large set of disjoint Kirkman triple systems of order 3v − 3 (briefly LKTS) and some new orders for LKTS are then obtained. Research supported by Tianyuan Mathematics Foundation of NSFC Grant 10526032 and Natural Science Foundation of Universities of Jiangsu Province Grant 05KJB110111.     

Overlarge sets of disjoint Steiner quadruple systems

In this article, we construct overlarge sets of disjoint S(3, 4, 3ⁿ − 1) and overlarge sets of disjoint S(3, 4, 3ⁿ + 1) for all n ≥ 2. Up to now, the only known infinite sequence of overlarge sets of disjoint S(3, 4, v) were the overlarge sets of disjoint S(3, 4, 2ⁿ) obtained from the oval conics of desarguesian projective planes of order 2ⁿ. © 1999 John Wiley & Sons, Inc. J Combin Design 7: 311–315, 1999     

Oriented list colorings of graphs

A 2‐assignment on a graph G = (V,E) is a collection of pairs L(v) of allowed colors specified for all vertices v ∈V. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satisfies the following property: For every 2‐assignment there exists a choice c(v)∈L(v) for all v ∈V such that (i) if c(v) = c(w), then vw ∉ E, and (ii) for every ordered pair (a,b) of colors, if some edge oriented from color a to color b occurs, then no edge is oriented from color b to color a. In this paper we characterize the following subclasses of graphs of oriented choice number 2: matchings; connected graphs; graphs containing at least one cycle. In particular, the first result (which implies that the matching with 11 edges has oriented choice number 2) proves a conjecture of Sali and Simonyi. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 217–229, 2001     

The spectrum of equitable, 4‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly an SQS(v)) is a pair (X, ) with |X| = v and a set of quadruples taken from X such that every triple in X is in a unique quadruple in . Hanani [Canad J Math 12 (1960), 145–157] showed that an SQS(v) exists if and only if v is {admissible}, that is, v = 0,1 or v ≡ 2,4 (mod 6). Each SQS(v) has a chromatic number when considered as a 4‐uniform hypergraph. Here we show that a 4‐chromatic SQS(v) exists for all admissible v ≥ 20, and that no 4‐chromatic SQS(v) exists for v < 20. Each system we construct admits a proper 4‐coloring that is equitable, that is, any two color classes differ in size by at most one. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 369–392, 2007     

Steiner centers and Steiner medians of graphs

Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by d_G(S) or d(S). The Steiner n-eccentricity e_n(v) and Steiner n-distance d_n(v) of a vertex v in G are defined as e_n(v)=max{d(S)| SV(G), |S|=n and vS} and d_n(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center C_n(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median M_n(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that C_n(T) is contained in C_n+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that M_n(T) is contained in M_n+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which C_n(G)C_n+1(G). We also show that for each n2 there is a distance–hereditary graph G such that M_n(G)M_n+1(G). Despite these negative examples, we prove that if G is a block graph then M_n(G) is contained in M_n+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

Pasch trades with a negative block

A Steiner triple system of order v, STS(v), may be called equivalent to another STS(v) if one can be converted to the other by a sequence of three simple operations involving Pasch trades with a single negative block. It is conjectured that any two STS(v)s on the same base set are equivalent in this sense. We prove that the equivalence class containing a given system S on a base set V contains all the systems that can be obtained from S by any sequence of well over one hundred distinct trades, and that this equivalence class contains all isomorphic copies of S on V. We also show that there are trades which cannot be effected by means of Pasch trades with a single negative block.     

Degree-bounded coloring of graphs: Variations on a theme by brooks

A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db-colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db-colorable graphs, as well as a nonalgorithmic characterization of db-colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db-colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.     

Quasi‐embeddings of Steiner triple systems,or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

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.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

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     

Halving Steiner 2-designs

A Steiner 2-design S(2,k,v) is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on v vertices into K_ks. The obvious necessary condition of those orders v for which there exists a halvable S(2,k,v) is that v admits the existence of an S(2,k,v) with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any k?5 or any Mersenne prime k, there is a constant number v₀ such that if v>v₀ and v satisfies the above necessary condition, then there exists a halvable S(2,k,v). We also show that a halvable S(2,2ⁿ,v) exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented.     

The Fine Intersection Problem for Steiner Triple Systems

The intersection of two Steiner triple systems and is the set . The fine intersection problem for Steiner triple systems is to determine for each v, the set I(v), consisting of all possible pairs (m, n) such that there exist two Steiner triple systems of order v whose intersection satisfies and . We show that for v ≡ 1 or 3 (mod 6), |I(v)| = Θ(v ³), where previous results only imply that |I(v)| = Ω(v ²). Received: January 23, 2006. Final Version received: September 2, 2006     

The design of the century

We construct a 2-chromatic Steiner system S(2, 4, 100) in which every block contains three points of one colour and one point of the other colour. The existence of such a design has been open for over 25 years.      

Velocity averaging,kinetic formulations,and regularizing effects in quasi‐linear PDEs

We prove in this paper new velocity‐averaging results for second‐order multidimensional equations of the general form ??(?_x, v)f(x, v) = g(x, v) where ??(?_x, v) := a (v) · ?_x ? ? ${}_{\text{x}}^{\text{?}}$ · b (v)?_x. These results quantify the Sobolev regularity of the averages, ∫_v f(x, v)?(v)dv, in terms of the nondegeneracy of the set {v: |??(iξ, v)| ≤ δ} and the mere integrability of the data, (f, g) ∈ (L, L). Velocity averaging is then used to study the regularizing effect in quasi‐linear second‐order equations, ??(?_x, ρ)ρ = S(ρ), which use their underlying kinetic formulations, ??(?_{x, v})χ_ρ = g_S. In particular, we improve previous regularity statements for nonlinear conservation laws, and we derive completely new regularity results for convection‐diffusion and elliptic equations driven by degenerate, nonisotropic diffusion. © 2007 Wiley Periodicals, Inc.     

Proper S(t,K,v)'s for t ≥ 3,v ≤ 16, |K| > 1 and Their Extensions

We characterize the proper t-wise balanced designs t-(v,K,1) for t ≥ 3, λ = 1 and v ≤ 16 with at least two block sizes. While we do not examine extensions of S(3,4,16)'s, we do determine all other possible extensions of S(3,K,v)'s for v ≤ 16. One very interesting extension is an S(4, {5,6}, 17) design.©1995 John Wiley & Sons, Inc.