Projects per year
Abstract
For positive integers n and k with n \geqslant k, an (n, k, 1)design is a pair (V, \scrB ), where V is a set of n points and \scrB is a collection of ksubsets of V called blocks such that each pair of points occur together in exactly one block. If we weaken this condition to demand only that each pair of points occur together in at most one block, then the resulting object is a partial (n, k, 1)design. A completion of a partial (n, k, 1)design (V, \scrA ) is a (complete) (n, k, 1)design (V, \scrB ) such that \scrA \subseteq \scrB . Here, for all sufficiently large n, we determine exactly the minimum number of blocks in an uncompletable partial (n, k, 1)design. This result is reminiscent of Evans' nowproved conjecture on completions of partial Latin squares. We also prove some related results concerning edge decompositions of almost complete graphs into copies of K_{k}
Original language  English 

Pages (fromto)  4763 
Number of pages  17 
Journal  SIAM Journal on Discrete Mathematics 
Volume  36 
Issue number  1 
DOIs  
Publication status  Published  2022 
Keywords
 almost complete graph
 completion
 embedding
 Kdecomposition
 partial block design
Projects
 2 Finished

Edge decomposition of dense graphs
Australian Research Council (ARC)
30/06/17 → 31/10/22
Project: Research

Matchings in Combinatorial Structures
Wanless, I., Bryant, D. & Horsley, D.
Australian Research Council (ARC), Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research