We study the problem of partitioning the edges of a d-uniform hypergraph H into a family F of complete d-partite hypergraphs (d-cliques). We show that there is a partition F in which every vertex v ∈ V(H) belongs to at most (1/d! + od(1))nd−1/lgn members of F. This settles the central question of a line of research initiated by Erdős and Pyber (1997) for graphs, and more recently by Csirmaz, Ligeti, and Tardos (2014) for hypergraphs. The d=2 case of this theorem answers a 40-year-old question of Chung, Erdős, and Spencer (1983). An immediate corollary of our result is an improved upper bound for the maximum share size for binary secret sharing schemes on uniform hypergraphs.

In this work, we address vertex partitioning problems in digraphs. We study whether it is possible to colour the vertices of a digraph with large out-degree so that every vertex has many out-neighbours of the same colour (related to conjectures by Bermond-Thomassen and questions of Alon), as well as the opposite question: whether it is possible to colour the vertices so that no vertex has many out-neighbours of the same colour (related to the majority colouring conjecture of Kreutzer et al.). We study both problems in detail for concave-round digraphs, a class introduced by Bang-Jensen, Huang, and Yeo. We also make progress on the majority colouring conjecture for tournaments.

A set V is separated by a family of sets F if for every pair of elements in V, there exists F ε f which contains exactly one of the elements of the pair. Given a tree T , we wish to separate V(T) only using sets of the form V(P) , where P is a path in T. We give closed formulas for sp (T) (the least size of such a separating family) in various classes of trees, including all trees without vertices of degree two. The formula we find depends on local parameters of the tree, such as its number of leaves. This parallels previous results for the edge-separation version of the problem. On the other hand, we give constructions of trees showing that as soon as we allow vertices of degree two, the local parameters we consider are not sufficient to describe sp( T ), thus uncovering a surprising and unexpected difference from previous results.

Abstract. We study conditions under which an edge-colored hypergraph has a particular substructure that contains more than the trivially guaranteed number of monochromatic edges. Our main result solves this problem for perfect matchings under minimum degree conditions. This answers recent questions of Gishboliner, Glock, and Sgueglia and of Balogh, Treglown, and Zárate-Guerén.

We show that 3-graphs whose codegree is at least (2/3 + o(1))n can be decomposed into tight cycles and admit Euler tours, subject to the trivial necessary divisibility conditions. We also provide a construction showing that our bounds are best possible up to the o(1) term. All together, our results answer in the negative some recent questions of Glock, Joos, Kühn and Osthus.

Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the \tt Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.