In 1940 Fisher famously showed that if there exists a non-trivial (
v,k,λ
)-design, then λ(
v
-1)⩾
k
(
k
-1). Subsequently Bose gave an elegant alternative proof of Fisher’s result. Here, we show ...that the idea behind Bose’s proof can be generalised to obtain new bounds on the number of blocks in (
v,k,λ
)-coverings and -packings with λ(
v
-1)<
k
(
k
-1).
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.
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
n
k 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
(
mod
2
k
) for almost all odd values of
k.
Abstract In situations where every item in a data set must be compared with every other item in the set, it may be desirable to store the data across a number of machines in such a way that any two ...data items are stored together on at least one machine. One way to evaluate the efficiency of such a distribution is by the largest fraction of the data it requires to be allocated to any one machine. The all-to-all comparison (ATAC) data limit for m machines is a measure of the minimum of this value across all possible such distributions. In this paper we further the study of ATAC data limits. We begin by investigating the data limits achievable using various classes of combinatorial designs. In particular, we examine the cases of transversal designs and projective Hjelmslev planes. We then observe relationships between data limits and the previously studied combinatorial parameters of fractional matching numbers and covering numbers . Finally, we prove a lower bound on the ATAC data limit that improves on one of Hall, Kelly and Tian, and examine the special cases where equality in this bound is possible.
In this article we construct uncountably many new homogeneous locally finite Steiner triple systems of countably infinite order as Fraïssé limits of classes of finite Steiner triple systems avoiding ...certain subsystems. The construction relies on a new embedding result: any finite partial Steiner triple system has an embedding into a finite Steiner triple system that contains no nontrivial proper subsystems that are not subsystems of the original partial system. Fraïssé's construction and its variants are rich sources of examples that are central to model-theoretic classification theory, and recently infinite Steiner systems obtained via Fraïssé-type constructions have received attention from the model theory community.
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
)
m
2
+
n ${Z}_{2,t}(m,n)=(t-1)\left(\genfrac{}{}{0.0pt}{}{m}{2}\right)+n$ when n
≥(t
−
1
)
m
2 $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
=
Θ(t
m
2
) $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.
Let F be a family of subsets of a ground set {1,…,n} with |F|=m, and let F↕ denote the family of all subsets of {1,…,n} that are subsets or supersets of sets in F. Here we determine the minimum value ...that |F↕| can attain as a function of n and m. This can be thought of as a ‘two-sided’ Kruskal–Katona style result. It also gives a solution to the isoperimetric problem on the graph whose vertices are the subsets of {1,…,n} and in which two vertices are adjacent if one is a subset of the other. This graph is a supergraph of the n-dimensional hypercube and we note some similarities between our results and Harper’s theorem, which solves the isoperimetric problem for hypercubes. In particular, analogously to Harper’s theorem, we show there is a total ordering of the subsets of {1,…,n} such that, for each initial segment F of this ordering, F↕ has the minimum possible size. Our results also answer a question that arises naturally out of work of Gerbner et al. on cross-Sperner families and allow us to strengthen one of their main results.
Zarankiewicz numbers near the triple system threshold Chen, Guangzhou; Horsley, Daniel; Mammoliti, Adam
Journal of combinatorial designs,
September 2024, 2024-09-00, 20240901, Volume:
32, Issue:
9
Journal Article
Peer reviewed
Open access
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)$.
In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size m exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient ...conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes m1,…,mt. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes m1,…,mt is NP-complete, but that it becomes tractable if we place a strong enough upper bound on max(m1,…,mt). We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes m1,…,mt with specified centres, and a generalisation of Landau's theorem on tournaments.
PDF
