We show that for any \varepsilon \gt 0$\varepsilon \gt 0$ and \Delta \in \mathbb{N}$\Delta \in \mathbb{N}$, there exists \alpha \gt 0$\alpha \gt 0$ such that for sufficiently large n$n$, every n$n$-vertex graph G$G$ satisfying that \delta (G)\geq \varepsilon n$\delta (G)\geq \varepsilon n$ and e(X, Y)\gt 0$e(X, Y)\gt 0$ for every pair of disjoint vertex sets X, Y\subseteq V(G)$X, Y\subseteq V(G)$ of size \alpha n$\alpha n$ contains all spanning trees with maximum degree at most \Delta$\Delta$. This strengthens a result of Böttcher, Han, Kohayakawa, Montgomery, Parczyk, and Person.

The well-known Erdős-Hajnal conjecture states that for any graph F$F$, there exists \epsilon \gt 0$\epsilon \gt 0$ such that every n$n$-vertex graph G$G$ that contains no induced copy of F$F$ has a homogeneous set of size at least n^{\epsilon }$n^{\epsilon }$. We consider a variant of the Erdős-Hajnal problem for hypergraphs where we forbid a family of hypergraphs described by their orders and sizes. For graphs, we observe that if we forbid induced subgraphs on m$m$ vertices and f$f$ edges for any positive m$m$ and 0\leq f \leq \binom{m}{2}$0\leq f \leq \binom{m}{2}$, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case m=4$m=4$, for every S \subseteq \{0,1,2,3,4\}$S \subseteq \{0,1,2,3,4\}$, we give bounds on the minimum size of a homogeneous set in a triple system where the number of edges spanned by every four vertices is not in S$S$. In most cases the bounds are essentially tight. We also determine, for all S$S$, whether the growth rate is polynomial or polylogarithmic. Some open problems remain.

Given a fixed graph H$H$ and a constant c \in [0,1]$c \in [0,1]$, we can ask what graphs G$G$ with edge density c$c$ asymptotically maximise the homomorphism density of H$H$ in G$G$. For all H$H$ for which this problem has been solved, the maximum is always asymptotically attained on one of two kinds of graphs: the quasi-star or the quasi-clique. We show that for any H$H$ the maximising G$G$ is asymptotically a threshold graph, while the quasi-clique and the quasi-star are the simplest threshold graphs, having only two parts. This result gives us a unified framework to derive a number of results on graph homomorphism maximisation, some of which were also found quite recently and independently using several different approaches. We show that there exist graphs H$H$ and densities c$c$ such that the optimising graph G$G$ is neither the quasi-star nor the quasi-clique (Day and Sarkar, SIAM J. Discrete Math. 35(1), 294–306, 2021). We also show that for c$c$ large enough all graphs H$H$ maximise on the quasi-clique (Gerbner et al., J. Graph Theory 96(1), 34–43, 2021), and for any c \in [0,1]$c \in [0,1]$ the density of K_{1,2}$K_{1,2}$ is always maximised on either the quasi-star or the quasi-clique (Ahlswede and Katona, Acta Math. Hung. 32(1–2), 97–120, 1978). Finally, we extend our results to uniform hypergraphs.

We consider the minimum spanning tree problem on a weighted complete bipartite graph K_{n_R, n_B}$K_{n_R, n_B}$ whose n=n_R+n_B$n=n_R+n_B$ vertices are random, i.i.d. uniformly distributed points in the unit cube in d$d$ dimensions and edge weights are the p$p$-th power of their Euclidean distance, with p\gt 0$p\gt 0$. In the large n$n$ limit with n_R/n \to \alpha _R$n_R/n \to \alpha _R$ and 0\lt \alpha _R\lt 1$0\lt \alpha _R\lt 1$, we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on d$d$ only. Despite this difference, for p\lt d$p\lt d$, we are able to prove that the total edge costs normalized by the rate n^{1-p/d}$n^{1-p/d}$ converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta.

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class \mathcal{G}$\mathcal{G}$ to be the minimum non-negative integer c$c$ such that, for some function f$f$, for every graph G \in \mathcal{G}$G \in \mathcal{G}$ there is a graph H$H$ with \textrm{tw}(H) \leqslant c$\textrm{tw}(H) \leqslant c$ such that G$G$ is isomorphic to a subgraph of H \boxtimes K_{f(\textrm{tw}(G))}$H \boxtimes K_{f(\textrm{tw}(G))}$. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3$3$; the class of K_{s,t}$K_{s,t}$-minor-free graphs has underlying treewidth s$s$ (for t \geqslant \max \{s,3\}$t \geqslant \max \{s,3\}$); and the class of K_t$K_t$-minor-free graphs has underlying treewidth t-2$t-2$. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no H$H$ subgraph has bounded underlying treewidth if and only if every component of H$H$ is a subdivided star, and that the class of graphs with no induced H$H$ subgraph has bounded underlying treewidth if and only if every component of H$H$ is a star.

We consider bond percolation on high-dimensional product graphs G=\square _{i=1}^tG^{(i)}$G=\square _{i=1}^tG^{(i)}$, where \square$\square$ denotes the Cartesian product. We call the G^{(i)}$G^{(i)}$ the base graphs and the product graph G$G$ the host graph. Very recently, Lichev (J. Graph Theory, 99(4):651–670, 2022) showed that, under a mild requirement on the isoperimetric properties of the base graphs, the component structure of the percolated graph G_p$G_p$ undergoes a phase transition when p$p$ is around \frac{1}{d}$\frac{1}{d}$, where d$d$ is the average degree of the host graph.

In the supercritical regime, we strengthen Lichev’s result by showing that the giant component is in fact unique, with all other components of order o(|G|)$o(|G|)$, and determining the sharp asymptotic order of the giant. Furthermore, we answer two questions posed by Lichev (J. Graph Theory, 99(4):651–670, 2022): firstly, we provide a construction showing that the requirement of bounded degree is necessary for the likely emergence of a linear order component; secondly, we show that the isoperimetric requirement on the base graphs can be, in fact, super-exponentially small in the dimension. Finally, in the subcritical regime, we give an example showing that in the case of irregular high-dimensional product graphs, there can be a polynomially large component with high probability, very much unlike the quantitative behaviour seen in the Erdős-Rényi random graph and in the percolated hypercube, and in fact in any regular high-dimensional product graphs, as shown by the authors in a companion paper (Percolation on high-dimensional product graphs. arXiv:2209.03722, 2022).

For a graph H$H$ and a hypercube Q_n$Q_n$, \textrm{ex}(Q_n, H)$\textrm{ex}(Q_n, H)$ is the largest number of edges in an H$H$-free subgraph of Q_n$Q_n$. If \lim _{n \rightarrow \infty } \textrm{ex}(Q_n, H)/|E(Q_n)| \gt 0$\lim _{n \rightarrow \infty } \textrm{ex}(Q_n, H)/|E(Q_n)| \gt 0$, H$H$ is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise, it has zero Turán density. Determining \textrm{ex}(Q_n, H)$\textrm{ex}(Q_n, H)$ and even identifying whether H$H$ has a positive or zero Turán density remains a widely open question for general H$H$. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of graphs, ones having so-called partite representation, that have zero Turán density. He asked whether this gives a characterisation, that is, whether a graph has zero Turán density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of graphs which have no partite representation, but on the other hand, have zero Turán density. In addition, we show that any graph whose every block has partite representation has zero Turán density in a hypercube.