Search

For positive integers m $m$ and n $n$, the Zarankiewicz number Z2,2(m,n) ${Z}_{2,2}(m,n)$ can be defined as the maximum total degree of a linear hypergraph with m $m$ vertices and n $n$ edges. Guy determined Z2,2(m,n) ${Z}_{2,2}(m,n)$ for all n⩾m2∕3+O(m) $n\geqslant \left(\genfrac{}{}{0.0pt}{}{m}{2}\right)\unicode{x02215}3+O(m)$. Here, we extend this by determining Z2,2(m,n) ${Z}_{2,2}(m,n)$ for all n⩾m2∕3 $n\geqslant \left(\genfrac{}{}{0.0pt}{}{m}{2}\right)\unicode{x02215}3$ and, when m $m$ is large, for all n⩾m2∕6+O(m) $n\geqslant \left(\genfrac{}{}{0.0pt}{}{m}{2}\right)\unicode{x02215}6+O(m)$. [ABSTRACT FROM AUTHOR]

For positive integers s $s$, t $t$, m $m$ and n $n$, the Zarankiewicz number Zs,t(m,n) ${Z}_{s,t}(m,n)$ is defined to be the maximum number of edges in a bipartite graph with parts of sizes m $m$ and n $n$ that has no complete bipartite subgraph containing s $s$ vertices in the part of size m $m$ and t $t$ vertices in the part of size n $n$. A simple argument shows that, for each t≥2 $t\ge 2$, Z2,t(m,n)=(t−1)m2+n ${Z}_{2,t}(m,n)=(t-1)\left(\genfrac{}{}{0.0pt}{}{m}{2}\right)+n$ when n≥(t−1)m2 $n\ge (t-1)\left(\genfrac{}{}{0.0pt}{}{m}{2}\right)$. Here, for large m $m$, we determine the exact value of Z2,t(m,n) ${Z}_{2,t}(m,n)$ in almost all of the remaining cases where n=Θ(tm2) $n={\rm{\Theta }}(t{m}^{2})$. We establish a new family of upper bounds on Z2,t(m,n) ${Z}_{2,t}(m,n)$ which complement a family already obtained by Roman. We then prove that the floor of the best of these bounds is almost always achieved. We also show that there are cases in which this floor cannot be achieved and others in which determining whether it is achieved is likely a very hard problem. Our results are proved by viewing the problem through the lens of linear hypergraphs and our constructions make use of existing results on edge decompositions of dense graphs. [ABSTRACT FROM AUTHOR]

The cyclic matching sequenceability of a simple graph G, denoted cms(G), is the largest integer s for which there exists a cyclic ordering of the edges of G so that every set of s consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of k‐regular graphs. We completely determine this for 2‐regular graphs, and give bounds for k⩾3. [ABSTRACT FROM AUTHOR]

An (n,k)‐Sperner partition system is a set of partitions of some n‐set such that each partition has k nonempty parts and no part in any partition is a subset of a part in a different partition. The maximum number of partitions in an (n,k)‐Sperner partition system is denoted SP(n,k). In this paper we introduce a new construction for Sperner partition systems based on a division of the ground set into many equal‐sized parts. We use this to asymptotically determine SP(n,k) in many cases where nk is bounded as n becomes large. Further, we show that this construction produces a Sperner partition system of maximum size for numerous small parameter sets (n,k). By extending a separate existing construction, we also establish the asymptotics of SP(n,k) when n≡k±1(mod2k) for almost all odd values of k. [ABSTRACT FROM AUTHOR]

An induced path factor of a graph G is a set of induced paths in G with the property that every vertex of G is in exactly one of the paths. The induced path numberρ(G) of G is the minimum number of paths in an induced path factor of G. We show that if G is a connected cubic graph on n>6 vertices, then ρ(G)⩽(n−1)/3. Fix an integer k⩾3. For each n, define ℳn to be the maximum value of ρ(G) over all connected k‐regular graphs G on n vertices. As n→∞ with nk even, we show that ck=lim(ℳn/n) exists. We prove that 5/18⩽c3⩽1/3 and 3/7⩽c4⩽1/2 and that ck=12−O(k−1) for k→∞. [ABSTRACT FROM AUTHOR]

A partial Steiner triple system of order u is a pair (U,A), where U is a set of u elements and A is a set of triples of elements of U such that any two elements of U occur together in at most one triple. If each pair of elements occur together in exactly one triple it is a Steiner triple system. An embedding of a partial Steiner triple system (U,A) is a (complete) Steiner triple system (V,B) such that U⊆V and A⊆B. For a given partial Steiner triple system of order u it is known that an embedding of order v⩾2u+1 exists whenever v satisfies the obvious necessary conditions. Determining whether "small" embeddings of order v<2u+1 exist is a more difficult task. Here we extend a result of Colbourn on the NP‐completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist. [ABSTRACT FROM AUTHOR]

Abstract: Youden square designs, or Youden rectangles, are classical objects in design theory. Extensions of these were introduced in 1958 by Kiefer and in 1981 by Cheng, in the form of generalized Youden designs (GYDs) and pseudo Youden designs (PYDs), respectively. In this paper, we introduce a common generalization of both these objects, which we call a pseudo generalized Youden design (PGYD). PGYDs share the statistically desirable optimality properties of GYDs and PYDs, and we show that they exist in situations where neither GYDs nor PYDs do. We determine some numerical necessary conditions for the existence of PGYDs, classify their existence for small parameter sets, and provide constructions for families of PGYDs using patchwork methods based on affine planes. [ABSTRACT FROM AUTHOR]

Abstract: Fisher proved in 1940 that any 2‐ ( v , k , λ ) design with v > k has at least v blocks. In 1975, Ray‐Chaudhuri and Wilson generalized this result by showing that every t‐ ( v , k , λ ) design with v ⩾ k + ⌊ t / 2 ⌋ has at least v ( ⌊ t / 2 ⌋ ) blocks. By combining methods used by Bose and Wilson in proofs of these results, we obtain new lower bounds on the size of t‐ ( v , k , λ ) coverings. Our results generalize lower bounds on the size of 2‐ ( v , k , λ ) coverings recently obtained by the first author. [ABSTRACT FROM AUTHOR]

For each odd [ABSTRACT FROM AUTHOR]

It was proved in 2009 that any partial Steiner triple system of order u has an embedding of order v for each admissible [ABSTRACT FROM AUTHOR]

We show that the complete graph on n vertices can be decomposed into t cycles of specified lengths m1, …, mt if and only if n is odd, 3≤mi≤n for i=1, …, t, and . We also show that the complete graph on n vertices can be decomposed into a perfect matching and t cycles of specified lengths m1, …, mt if and only if n is even, 3≤mi≤n for i=1, …, t, and . [ABSTRACT FROM PUBLISHER]

The problem of decomposing complete graphs into cycles of arbitrary specified lengths has attracted much attention, but remains largely unsolved. In this paper, the problem is settled in the case where the specified cycle lengths are each more than about half the order of the complete graph. The proof is based on a result that modifies certain existing cycle decompositions to produce new ones in which the lengths of two of the cycles are altered. [ABSTRACT FROM PUBLISHER]