It is a classical result that a random permutation of n elements has, on average, about log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt {\log d} )$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1 + {\mathcal{O}}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

Abstract. Kőnig’s theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of Kőnig’s theorem is that in every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic components needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text]. We prove the following strengthening of Kőnig’s theorem: In every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text].

Abstract. Let [Formula: see text] be a set of [Formula: see text] points on the real line. Suppose that each pairwise distance is known independently with probability [Formula: see text]. How much of [Formula: see text] can be reconstructed up to isometry? We prove that [Formula: see text] is a sharp threshold for reconstructing all of [Formula: see text], which improves a result of Benjamini and Tzalik. This follows from a hitting time result for the random process where the pairwise distances are revealed one by one uniformly at random. We also show that [Formula: see text] is a weak threshold for reconstructing a linear proportion of [Formula: see text].

We introduce a notion of the crux of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalizations of known results about cycles, offering an interesting paradigm of “replacing average degree by crux.” In particular, we prove that every graph contains a cycle of length linear in its crux. Long proved that every subgraph of a hypercube $Q^m$ (resp., discrete torus $C_3^m$) with average degree $d$ contains a path of length $2^{d/2}$ (resp., $2^{d/4}$) and conjectured that there should be a path of length $2^{d}-1$ (resp., $3^{d/2}-1$). As a corollary of our result, together with isoperimetric inequalities, we close these exponential gaps giving asymptotically optimal bounds on long paths in hypercubes, discrete tori, and more generally Hamming graphs. We also consider random subgraphs of $C_4$-free graphs and hypercubes, proving near optimal lower bounds on the lengths of long cycles.

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles, there is a row or a column in the diagram that is used by at least $k+1$ rectangles and prove that this is best possible. This answers two questions by Kim et al. [ European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.

We study the problem of determining sat$(n,k,r)$, the minimum number of edges in a $k$-partite graph $G$ with $n$ vertices in each part such that $G$ is $K_r$-free but the addition of an edge joining any two nonadjacent vertices from different parts creates a $K_r$. Improving recent results of Ferrara, Jacobson, Pfender, and Wenger, and generalizing a recent result of Roberts, we show that sat$(n,k,r) = \alpha(k,r)n + O(1)$ as $n \rightarrow \infty$. Moreover, for every $3 \leq r \leq k$ we prove that $k(2k - 4) \leq \alpha(k,r) \leq (k-1)(4 r - \ell -6),$ where $\ell = \mbox{min}\{k, 2r-3\}$, and show that the lower bound is tight for infinitely many values of $r$ and every $k\geq 2r-1$. This allows us to prove that, for these values, sat$(n,k,r) = k(2r-4)n + O(1)$ as $n \rightarrow \infty$. Along the way, we disprove a conjecture and answer a question of the first set of authors mentioned above.

In this note, we prove that for every integer $k$, there exist constants $g_{1}(k)$ and $g_{2}(k)$ such that the following holds. If $G$ is a graph on $n$ vertices with maximum degree $\Delta$ then it contains an induced subgraph $H$ on at least $n - g_{1}(k)\sqrt{\Delta}$ vertices, such that $H$ contains $k$ vertices of the same degree of order at least $\Delta(H)-g_{2}(k)$. This solves an approximate version of a conjecture of Caro and Yuster which states that $g_2(k)$ can be taken to be $0$ for every $k$. Note that in our result we allow the common degree to be at most an additive constant far from the maximum degree.