We prove the existence conjecture for combinatorial designs, answering a question of Steiner from 1853. More generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition. As a further generalisation, we obtain the same conclusion only assuming an extendability property and the existence of a robust fractional clique decomposition.
Another relaxation of the conjecture, which will play an important role in this paper, is obtained by considering integral designs', in which one assigns integers to the copies of @math in @math such that for every edge @math the sum of the integers assigned to the copies of @math containing @math is a constant independent of @math . Graver and Jurkat @cite_40 and Wilson @cite_29 showed that the divisibility conditions suffice for the existence of integral designs (this is used in @cite_29 to show the existence for large @math of integral designs with non-negative coefficients). Wilson @cite_7 also characterised the existence of integral @math -decompositions for any @math -graph @math .
@cite_40 @cite_29 @cite_7
1999506309 1588675120
Let @math be a partially ordered set. If the Boolean lattice @math can be partitioned into copies of @math for some positive integer @math , then @math must satisfy the following two trivial conditions: (1) the size of @math is a power of @math , (2) @math has a unique maximal and minimal element. Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well. In this paper, we show that if @math only satisfies condition (2), we can still almost partition @math into copies of @math . We prove that if @math has a unique maximal and minimal element, then there exists a constant @math such that all but at most @math elements of @math can be covered by disjoint copies of @math . Let @math be an induced subgraph of the torus @math . We show that when @math is even and @math divides some power of @math , then for sufficiently large @math the torus @math has a perfect vertex-packing with induced copies of @math . On the other hand, disproving a conjecture of Gruslys, we show that when @math is odd and not a prime power, then there exists @math such that @math divides some power of @math , but there is no @math such that @math has a perfect vertex-packing with copies of @math . We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph @math of the @math -dimensional hypercube @math , such that there is no @math for which @math has a perfect edge-packing with copies of @math . We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . For a pattern graph @math on @math nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of @math in a given large graph @math on @math nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an @math with an independent set of size @math can be computed exactly in @math time and @math space, or in @math time and @math space. (The @math notation omits @math factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a @math matrix over rings and semirings. 2. The number of copies of any @math having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in @math time, where @math is the matrix multiplication exponent and @math is divisible by @math . Similar results hold for other values of @math . Also, the number...