New large sets of t‐designs

Abstact: We introduce generalizations of earlier direct methods for constructing large sets of t‐designs. These are based on assembling systematically orbits of t‐homogeneous permutation groups in their induced actions on k‐subsets. By means of these techniques and the known recursive methods we construct an extensive number of new large sets, including new infinite families. In particular, a new series of LS[3](2(2 + m), 8·3^m ? 2, 16·3^m ? 3) is obtained. This also provides the smallest known ν for a t‐(ν, k, λ) design when t ≥ 16. We present our results compactly for ν ≤ 61, in tables derived from Pascal's triangle modulo appropriate primes. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 40–59, 2001     

Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

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 results on the existence of large sets of t‐designs

A set of trivial necessary conditions for the existence of a large set of t‐designs, LS[N](t,k,ν), is for i = 0,…,t. There are two conjectures due to Hartman and Khosrovshahi which state that the trivial necessary conditions are sufficient in the cases N = 2 and 3, respectively. Ajoodani‐Namini has established the truth of Hartman's conjecture for t = 2. Apart from this celebrated result, we know the correctness of the conjectures for a few small values of k, when N = 2 and t ≤ 6, and also when N = 3 and t ≤ 4. In this article, we show that similar results can be obtained for infinitely many values of k. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 144–151, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10027     

On t‐designs and s‐resolvable t‐designs from hyperovals

Hyperovals in projective planes turn out to have a link with t‐designs. Motivated by an unpublished work of Lonz and Vanstone, we present a construction for t‐designs and s‐resolvable t‐designs from hyperovals in projective planes of order $2^n$. We prove that the construction works for $t\le 5$. In particular, for $t=5$ the construction yields a family of 5‐ $\left(2^n+2,8,70\left(2^{n?2}?1\right)\right)$ designs. For $t=4$ numerous infinite families of 4‐designs on $2^n+2$ points with block size $2k$ can be constructed for any $k\ge 4$. The construction assumes the existence of a 4‐ $\left(2^{n?1}+1,k,\lambda \right)$ design, called the indexing design, including the complete 4‐ $\left(2^{n?1}+1,k,\left(\genfrac{}{}{0ex}{}{2^{n?1}?3}{k?4}\right)\right)$ design. Moreover, we prove that if the indexing design is s‐resolvable, then so is the constructed design. As a result, many of the constructed designs are s‐resolvable for $s=2,3$. We include a short discussion on the simplicity or non‐simplicity of the designs from hyperovals.     

New large sets of t‐designs with prescribed groups of automorphisms

In this article, we investigate the existence of large sets of 3‐designs of prime sizes with prescribed groups of automorphisms PSL(2,q) and PGL(2,q) for q < 60. We also construct some new interesting large sets by the use of the computer program DISCRETA. The results obtained through these direct methods along with known recursive constructions are combined to prove more extensive theorems on the existence of large sets. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 210–220, 2007     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

New ‐Edge‐Balanced Graphs from Bipartite Graphs

Let G be a graph of order n satisfying that there exists for which every graph of order n and size t is contained in exactly λ distinct subgraphs of the complete graph isomorphic to G. Then G is called t‐edge‐balanced and λ the index of G. In this article, new examples of 2‐edge‐balanced graphs are constructed from bipartite graphs and some further methods are introduced to obtain more from old.     

New Infinite Families of 2‐Edge‐Balanced Graphs

A graph G of order n is called t‐edge‐balanced if G satisfies the property that there exists a positive λ for which every graph of order n and size t is contained in exactly λ distinct subgraphs of isomorphic to G. We call λ the index of G. In this article, we obtain new infinite families of 2‐edge‐balanced graphs.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

The complete bipartite graphs with a unique edge‐transitive embedding

Jones, Nedela, and Škoviera (2008) showed that a complete bipartite graph has a unique orientably regular embedding if and only if . In this article, we extend this result by proving that a complete bipartite graph has a unique orientably edge‐transitive embedding if and only if .     

A recursive construction of t‐wise uniform permutations

We present a recursive construction of a (2t + 1)‐wise uniform set of permutations on 2n objects using a combinatorial design, a t‐wise uniform set of permutations on n objects and a (2t + 1)‐wise uniform set of permutations on n objects. Using the complete design in this procedure gives a t‐wise uniform set of permutations on n objects whose size is at most t²ⁿ, the first non‐trivial construction of an infinite family of t‐wise uniform sets for . If a non‐trivial design with suitable parameters is found, it will imply a corresponding improvement in the construction. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 531–540, 2015     

The Marčenko‐Pastur law for sparse random bipartite biregular graphs

We prove that the empirical spectral distribution of a (d_L, d_R)‐biregular, bipartite random graph, under certain conditions, converges to a symmetrization of the Mar?enko‐Pastur distribution of random matrix theory. This convergence is not only global (on fixed‐length intervals) but also local (on intervals of increasingly smaller length). Our method parallels the one used previously by Dumitriu and Pal (2012). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 313–340, 2016     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Zero‐sum flows in designs

Let D be a t ‐ ( v, k , λ) design and let N _i (D) , for 1 ≤ i ≤ t , be the higher incidence matrix of D , a ( 0 , 1 )‐matrix of size , where b is the number of blocks of D . A zero‐sum flow of D is a nowhere‐zero real vector in the null space of N ₁ ( D ). A zero‐sum k‐flow of D is a zero‐sum flow with values in { 1 , …, ±( k ? 1 )}. In this article, we show that every non‐symmetric design admits an integral zero‐sum flow, and consequently we conjecture that every non‐symmetric design admits a zero‐sum 5‐flow. Similarly, the definition of zero‐sum flow can be extended to N _i ( D ), 1 ≤ i ≤ t . Let be the complete design. We conjecture that N _t ( D ) admits a zero‐sum 3‐flow and prove this conjecture for t = 2 . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:355‐364, 2011     

Quasi‐symmetric designs with fixed difference of block intersection numbers

The following results for proper quasi‐symmetric designs with non‐zero intersection numbers x,y and λ > 1 are proved.

• (1) Let D be a quasi‐symmetric design with z = y ? x and v ≥ 2k. If x ≥ 1 + z + z³ then λ < x + 1 + z + z³.
• (2) Let D be a quasi‐symmetric design with intersection numbers x, y and y ? x = 1. Then D is a design with parameters v = (1 + m) (2 + m)/2, b = (2 + m) (3 + m)/2, r = m + 3, k = m + 1, λ = 2, x = 1, y = 2 and m = 2,3,… or complement of one of these design or D is a design with parameters v = 5, b = 10, r = 6, k = 3, λ = 3, and x = 1, y = 2.
• (3) Let D be a triangle free quasi‐symmetric design with z = y ? x and v ≥ 2k, then x ≤ z + z².
• (4) For fixed z ≥ 1 there exist finitely many triangle free quasi‐symmetric designs non‐zero intersection numbers x, y = x + z.
• (5) There do not exist triangle free quasi‐symmetric designs with non‐zero intersection numbers x, y = x + 2.

© 2006 Wiley Periodicals, Inc. J Combin Designs 15: 49–60, 2007     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

Mono-multi bipartite Ramsey numbers, designs, and matrices

Eroh and Oellermann defined BRR(G₁,G₂) as the smallest N such that any edge coloring of the complete bipartite graph K_N,N contains either a monochromatic G₁ or a multicolored G₂. We restate the problem of determining BRR(K_1,λ,K_r,s) in matrix form and prove estimates and exact values for several choices of the parameters. Our general bound uses Füredi's result on fractional matchings of uniform hypergraphs and we show that it is sharp if certain block designs exist. We obtain two sharp results for the case r=s=2: we prove BRR(K_1,λ,K_2,2)=3λ-2 and that the smallest n for which any edge coloring of K_λ,n contains either a monochromatic K_1,λ or a multicolored K_2,2 is λ².