A seminal result of Komlós, Sárközy, and Szemerédi states that any n-vertex graph G with minimum degree at least (1/2+α)n contains every n-vertex tree T of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result to show that such graphs G in fact support an optimally spread distribution on copies of a given T, which implies, using the recent breakthroughs on the Kahn-Kalai conjecture, the robustness result that T is a subgraph of sparse random subgraphs of G as well. Pham, Sah, Sawhney, and Simkin construct their optimally spread distribution by following closely the original proof of the Komlós-Sárközy-Szemerédi theorem which uses the blow-up lemma and the Szemerédi regularity lemma. We give an alternative, regularity-free construction that instead uses the Komlós-Sárközy-Szemerédi theorem (which has a regularity-free proof due to Kathapurkar and Montgomery) as a black box. Our proof is based on the simple and general insight that, if G has linear minimum degree, almost all constant-sized subgraphs of G inherit the same minimum degree condition that G has.

Given access to the vertex set (Formula presented.) of a connected graph (Formula presented.) and an oracle that given two vertices (Formula presented.), returns the shortest path distance between (Formula presented.) and (Formula presented.), how many queries are needed to reconstruct (Formula presented.) ? Firstly, we show that randomized algorithms need to use at least (Formula presented.) queries in expectation to reconstruct (Formula presented.) -vertex trees of maximum degree (Formula presented.). The best previous lower bound (for graphs of bounded maximum degree) was an information-theoretic lower bound of (Formula presented.). Our randomized lower bound is also the first to break through the information-theoretic barrier for related query models, including distance queries for phylogenetic trees, membership queries for learning partitions, and path queries in directed trees. Secondly, we provide a simple deterministic algorithm to reconstruct trees using (Formula presented.) distance queries. This proves that our lower bound is optimal up to a multiplicative constant. We extend our algorithm to reconstruct graphs without induced cycles of length at least (Formula presented.) using (Formula presented.) queries. Our lower bound is therefore tight for a wide range of tree-like graphs, such as chordal graphs, permutation graphs, and AT-free graphs. The previously best randomized algorithm for chordal graphs used (Formula presented.) queries in expectation, so we improve by a (Formula presented.) -factor for this graph class.

Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat^∗(n,P), is the size of the smallest P-saturated family with ground set [n]. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that sat^∗(n,P)=O(n^c), where c≤|P|²/4+1 is a constant depending on P only. We obtain this result by bounding the VC-dimension of our family.

In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the shortest path distance between u and v in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an n-vertex connected graph G parameterized by maximum degree ∆ and treelength k in O_k∆(nlog² n) queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength.