Search

We prove that there exists a constant $C$ so that for all $s,k \in \mathbb{N}$, every $K_{s,s}$-free graph with average degree at least $k^{Cs^3}$ contains an induced subgraph which is $C_4$-free and has average degree at least $k$. It was known that some function of $s$ and $k$ suffices, but this is the first explicit bound. Using this theorem, we give short and streamlined proofs of the following three corollaries. First, we show that there exists a constant $C$ so that for all $k \in \mathbb{N}$, every graph with average degree at least $k^{Ck^6}$ contains a bipartite subgraph (not necessarily induced) which is $C_4$-free and has average degree at least $k$. This almost matches the recent bound of $k^{Ck^2}$ due to Montgomery, Pokrovskiy, and Sudakov. Next, we show that there exists a constant $C$ so that for all $s,k \in \mathbb{N}$, every $K_{s,s}$-free graph with average degree at least $k^{Cs^3}$ contains an induced subdivision of $K_k$. This is the first quantitative improvement on a well-known theorem of K\"uhn and Osthus; their proof gives a bound that is triply exponential in both $k$ and $s$. Finally, we show that for any hereditary degree-bounded class $\mathcal{F}$, there exists a constant $C_\mathcal{F}$ so that $(C_\mathcal{F})^{s^3}$ is a degree-bounding function for $\mathcal{F}$. This is the first bound of any type on the rate of growth of such functions. It is open whether there is always a polynomial degree-bounding function., Comment: 18 pages

Erd\H{o}s and Hajnal conjectured that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or a stable set of size at least $|G|^c$ ("$H$-free" means with no induced subgraph isomorphic to $H$). Alon, Pach, and Solymosi reduced the Erd\H{o}s-Hajnal conjecture to the case when $H$ is prime (that is, $H$ cannot be obtained by vertex-substitution from smaller graphs); but until now, it was not shown for any prime graph with more than five vertices. We will provide infinitely many prime graphs that satisfy the conjecture. Let $H$ be a graph with the property that for every prime induced subgraph $G'$ with $|G'|\ge 3$, $G'$ has a vertex of degree one and a vertex of degree $|G'|-2$. We will prove that every graph $H$ with this property satisfies the Erd\H{o}s-Hajnal conjecture, and infinitely many graphs with this property are prime. Our proof method also extends to ordered graphs; and we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths. Indeed, we prove a stronger result, that we can weaken the "$H$-free" hypothesis of the Erd\H{o}s-Hajnal conjecture to one saying that there are not many copies of $H$; and strengthen its conclusion, deducing a "polynomial" version of R\"odl's theorem conjectured by Fox and Sudakov. We also obtain infinitely many new prime tournaments that satisfy the Erd\H{o}s-Hajnal conjecture (in tournament form). Say a tournament is buildable if it can be grown from nothing by repeatedly either adding a vertex of out-degree $\le 1$ or in-degree $\le 1$, or vertex-substitution. All buildable tournaments satisfy the tournament version of the Erd\H{o}s-Hajnal conjecture., Comment: 20 pages, minor updates

A well-known theorem of R\"odl says that for every graph $H$, and every $\epsilon>0$, there exists $\delta>0$ such that if $G$ does not contain an induced copy of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge\delta|G|$ such that one of $G[X],\overline{G}[X]$ has edge-density at most $\epsilon$. But how does $\delta$ depend on $\epsilon$? Fox and Sudakov conjectured that the dependence can be taken to be polynomial: for all $H$ there exists $c>0$ such that for all $\epsilon\in(0,1/2)$, R\"odl's theorem holds with $\delta=\epsilon^c$. This conjecture implies the Erd\H{o}s-Hajnal conjecture, and until now it had not been verified for any non-trivial graphs $H$. Our first result shows that it is true when $H=P_4$ (indeed, we can take $\delta=\epsilon$, and insist that one of $G[X],\overline{G}[X]$ has maximum degree at most $\epsilon^2|G|$).) We will generalize this, and to do so, we need to work with an even stronger property. Let us say $H$ is {\em viral} if there exists $c>0$ such that for all $\epsilon\in(0,1/2)$, if $G$ contains at most $\epsilon^c|G|^{|H|}$ induced copies of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge \epsilon^c|G|$ such that one of $G[X],\overline{G}[X]$ has density at most $\epsilon$. We will show that $P_4$ is viral, using a ``polynomial $P_4$-removal lemma'' of Alon and Fox. We will also show that viral graphs are closed under vertex-substitution, and so all graphs that can be obtained by substitution from copies of $P_4$ are viral. (In a subsequent paper, it will be shown that all graphs currently known to satisfy the Erd\H{o}s-Hajnal conjecture are in fact viral.) Finally, we give a different strengthening of R\"odl's theorem: we show that if $G$ does not contain an induced copy of $P_4$, then its vertices can be partitioned into at most $480\epsilon^{-4}$ subsets $X$ such that one of $G[X],\overline{G}[X]$ has density at most $\epsilon$.

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.

The free semigroup $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the set of all finite words with letters from $\mathcal{A}$ equipped with the operation of concatenation. A subset $S$ of $\mathcal{F}$ is $k$-product-free if no element of $S$ can be obtained by concatenating $k$ words from $S$, and strongly $k$-product-free if no element of $S$ is a (non-trivial) concatenation of at most $k$ words from $S$. We prove that a $k$-product-free subset of $\mathcal{F}$ has upper Banach density at most $1/\rho(k)$, where $\rho(k) = \min\{\ell \colon \ell \nmid k - 1\}$. We also determine the structure of the extremal $k$-product-free subsets for all $k \notin \{3, 5, 7, 13\}$; a special case of this proves a conjecture of Leader, Letzter, Narayanan, and Walters. We further determine the structure of all strongly $k$-product-free sets with maximum density. Finally, we prove that $k$-product-free subsets of the free group have upper Banach density at most $1/\rho(k)$, which confirms a conjecture of Ortega, Ru\'{e}, and Serra., Comment: 31 pages, added density results for the free group

We prove that for every path H, and every integer d, there is a polynomial f such that every graph G with chromatic number greater than f(t) either contains H as an induced subgraph, or contains as a subgraph the complete d-partite graph with parts of cardinality t. For t = 1 and general d this is a classical theorem of Gy\'arf\'as, and for d = 2 and general t this is a theorem of Bonamy et al.

The Gy\'arf\'as-Sumner conjecture says that for every tree $T$ and every integer $t\ge 1$, if $G$ is a graph with no clique of size $t$ and with sufficiently large chromatic number, then $G$ contains an induced subgraph isomorphic to $T$. This remains open, but we prove that under the same hypotheses, $G$ contains a subgraph $H$ isomorphic to $T$ that is ``path-induced''; that is, for some distinguished vertex~$r$, every path of $H$ with one end $r$ is an induced path of $G$.

Let $V$ be a set of $n$ points on the real line. Suppose that each pairwise distance is known independently with probability $p$. How much of $V$ can be reconstructed up to isometry? We prove that $p = (\log n)/n$ is a sharp threshold for reconstructing all of $V$ 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 $1/n$ is a weak threshold for reconstructing a linear proportion of $V$., 13 pages

In 1977, Erd\H{o}s and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $ |G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We prove a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of R\"odl, Nikiforov, and the theorem of Erd\H{o}s and Hajnal mentioned above.

Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge\dotsb\ge d_n\ge 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))4^n/n^{3/4}$ for some constant $c>0$, improving both the previously best upper and lower bounds by a factor of $n^{1/4}$ (up to polylog-factors). Additionally, we answer a question of Royle, extend the values of $n$ for which the exact value of $G(n)$ is known from $n\le290$ to $n\le 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative., 43 pages, 2 figures

The Gyárfás-Sumner conjecture says that for every tree $T$ and every integer $t\ge 1$, if $G$ is a graph with no clique of size $t$ and with sufficiently large chromatic number, then $G$ contains an induced subgraph isomorphic to $T$. This remains open, but we prove that under the same hypotheses, $G$ contains a subgraph $H$ isomorphic to $T$ that is ``path-induced''; that is, for some distinguished vertex~$r$, every path of $H$ with one end $r$ is an induced path of $G$.

Colour the edges of the complete graph with vertex set $\{1, 2, \dotsc, n\}$ with an arbitrary number of colours. What is the smallest integer $f(l,k)$ such that if $n > f(l,k)$ then there must exist a monotone monochromatic path of length $l$ or a monotone rainbow path of length $k$? Lefmann, R\"{o}dl, and Thomas conjectured in 1992 that $f(l, k) = l^{k - 1}$ and proved this for $l \ge (3 k)^{2 k}$. We prove the conjecture for $l \geq k^3 (\log k)^{1 + o(1)}$ and establish the general upper bound $f(l, k) \leq k (\log k)^{1 + o(1)} \cdot l^{k - 1}$. This reduces the gap between the best lower and upper bounds from exponential to polynomial in $k$. We also generalise some of these results to the tournament setting., Comment: 14 pages, improved Theorem 1.3 slightly

Two subgraphs $A,B$ of a graph $G$ are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if $G$ is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erd\H{o}s in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all $t, c\ge 1$ there exists $d\ge 1$ such that if $G$ has chromatic number at least $d$, and does not contain the complete graph $K_t$ as a subgraph, then there are anticomplete subgraphs $A,B$, where $A$ has minimum degree at least $c$ and $B$ has chromatic number at least $c$. Second, we look at what happens if we replace the hypothesis that $G$ has sufficiently large chromatic number with the hypothesis that $G$ has sufficently large minimum degree. This, together with excluding $K_t$, is {\em not} enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of xcluding $K_t$ we exclude the complete bipartite graph $K_{t,t}$. More exactly: for all $t, c\ge 1$ there exists $d\ge 1$ such that if $G$ has minimum degree at least $d$, and does not contain the complete bipartite graph $K_{t,t}$ as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least $c$.

Erdős and Hajnal conjectured that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or a stable set of size at least $|G|^c$ ("$H$-free" means with no induced subgraph isomorphic to $H$). Alon, Pach, and Solymosi reduced the Erdős-Hajnal conjecture to the case when $H$ is prime (that is, $H$ cannot be obtained by vertex-substitution from smaller graphs); but until now, it was not shown for any prime graph with more than five vertices. We will provide infinitely many prime graphs that satisfy the conjecture. Let $H$ be a graph with the property that for every prime induced subgraph $G'$ with $|G'|\ge 3$, $G'$ has a vertex of degree one and a vertex of degree $|G'|-2$. We will prove that every graph $H$ with this property satisfies the Erdős-Hajnal conjecture, and infinitely many graphs with this property are prime. Our proof method also extends to ordered graphs; and we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths. Indeed, we prove a stronger result, that we can weaken the "$H$-free" hypothesis of the Erdős-Hajnal conjecture to one saying that there are not many copies of $H$; and strengthen its conclusion, deducing a "polynomial" version of Rödl's theorem conjectured by Fox and Sudakov. We also obtain infinitely many new prime tournaments that satisfy the Erdős-Hajnal conjecture (in tournament form). Say a tournament is buildable if it can be grown from nothing by repeatedly either adding a vertex of out-degree $\le 1$ or in-degree $\le 1$, or vertex-substitution. All buildable tournaments satisfy the tournament version of the Erdős-Hajnal conjecture., 19 pages

A theorem of R\"odl says that for every graph $H$, and every $\varepsilon>0$, there exists $\delta>0$ such that if $G$ is a graph that has no induced subgraph isomorphic to $H$, then there exists $X\subseteq V(G)$ with $|X|\ge \delta|G|$ such that one of $G[X],\overline{G}[X]$ has at most $\varepsilon\binom{|X|}{2}$ edges. But for fixed $H$, how does $\delta$ depends on $\varepsilon$? If the dependence is polynomial, then $H$ satisfies the Erd\H{o}s-Hajnal conjecture; and Fox and Sudakov conjectured that the dependence is polynomial for {\em every} graph $H$. This conjecture is substantially stronger than the Erd\H{o}s-Hajnal conjecture itself, and until recently it was not known to be true for any non-trivial graphs $H$. The preceding paper of this series showed that it is true for $P_4$, and all graphs obtainable from $P_4$ by vertex-substitution. Here we will show that the Fox-Sudakov conjecture is true for all the graphs $H$ that are currently known to satisfy the Erd\H{o}s-Hajnal conjecture. In other words, we will show that it is true for the bull, and the 5-cycle, and induced subgraphs of them, and all graphs that can be obtained from these by vertex-substitution. There is a strengthening of R\"odl's theorem due to Nikiforov, that replaces the hypothesis that $G$ has no induced subgraph isomorphic to $H$, with the weaker hypothesis that the density of induced copies of $H$ in $G$ is small. We will prove the corresponding ``polynomial'' strengthening of Nikiforov's theorem for the same class of graphs $H$.

For an oriented graph $D$ and a set $X\subseteq V(D)$, the inversion of $X$ in $D$ is the digraph obtained by reversing the orientations of the edges of $D$ with both endpoints in $X$. The inversion number of $D$, $\operatorname{inv}(D)$, is the minimum number of inversions which can be applied in turn to $D$ to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet, we show that for each fixed $k\in\mathbb{N}$ the problem of deciding whether a tournament $T$ has $\operatorname{inv}(T)\leq k$ is solvable in time $O(\lvert V(T)\rvert ^2)$. This exponent is optimal for all $k$. On the other hand, we build on their work to prove their conjecture that for $k\geq 1$ the problem of deciding whether a general oriented graph $D$ has $\operatorname{inv}(D)\leq k$ is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called 'dijoin' digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an $n$-vertex tournament is $(1+o(1))n$., 23 pages

Let us say a graph is $s\mathcal{O}$-free, where $s\ge 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when $s=2$, is not well understood. For instance, until now we did not know how to test whether a graph is $2\mathcal{O}$-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2\mathcal{O}$-free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all $s\ge 1$, there exists $c>0$ such that every $s\mathcal{O}$-free graph $G$ has at most $|G|^c$ induced paths. This provides a poly-time algorithm to test if a graph is $s\mathcal{O}$-free, for all fixed $s$. The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, D\'epr\'es, Esperet, Geniet, Hilaire, Thomass\'e and Wesolek, that in every $s\mathcal{O}$-free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$. And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.

In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erd\H{o}s-R\'enyi random graph $\mathcal G(n,p)$ from a wide range of values of $r$. We determine the threshold for reconstructibility for each $r\geq 3$, extending and improving substantially on results of Mossel and Ross for $r=3$. For $r=2$, we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $r=1$., Comment: 36 pages, 3 figures

The deck of a graph $G$ is the multiset of cards $\{G-v:v\in V(G)\}$. Myrvold (1992) showed that the degree sequence of a graph on $n\geq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing., 10 pages

Using the TIDieR checklist, synthesize how current exercise-based AT interventions are being designed, implemented, and reported

The river network within anthropogenically modified watersheds conveys water and carbon more readily than in unmodified watersheds. Material conveyance has multiple negative consequences including elevated downstream flood risk and decreased carbon storage. Modern channel designs aim to mitigate these negative consequences by implementing design features such as constructed wetlands and large wood structures that promote water and carbon retention, enhancing watershed conditions. A field campaign was conducted within a low-order, designed channel one to two years post-construction in which design features (constructed wetlands and wood structures) were included to facilitate retention. Water level was measured continuously, and bed sediments were sampled discretely from September 2019 through November 2020. Data were processed to determine daily water presence/absence and particulate organic matter, then used to evaluate retention within design features and channel segments. The major contributions from this research will inform future watershed management initiatives aiming to facilitate retention within low-order channels.

A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\binom{n}2$, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac23 \binom{n}2+O(n\log n)$, and consider some related questions., 23 pages, 5 figures, 1 table

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_1$ and $S_2$, the states of the edges in $S_1$ are independent of the states of the edges in $S_2$. Such a model is said to percolate if the random subgraph has an infinite component with positive probability. In 2012 the first author and Bollob\'as defined $p_{\max}(G)$ to be the supremum of those $p$ for which there exists a 1-independent bond percolation model on $G$ in which each edge is present in the random subgraph with probability at least $p$ but which does not percolate. A fundamental and challenging problem in this area is to determine the value of $p_{\max}(G)$ when $G$ is the lattice graph $\mathbb{Z}^2$. Since $p_{\max}(\mathbb{Z}^n)\leq p_{\max}(\mathbb{Z}^{n-1})$, it is also of interest to establish the value of $\lim_{n\to\infty} p_{\max}(\mathbb{Z}^n)$. In this paper we significantly improve the best known upper bound on this limit and obtain better upper and lower bounds on $p_{\max}(\mathbb{Z}^2)$. In proving these results, we also give an upper bound on the critical probability for a 1-independent model on the hypercube graph to contain a giant component asymptotically almost surely., Comment: 31 pages, 3 figures

We prove that, for every graph $F$ with at least one edge, there is a constant $c_F$ such that there are graphs of arbitrarily large chromatic number and the same clique number as $F$ in which every $F$-free induced subgraph has chromatic number at most $c_F$. This generalises recent theorems of Bria\'{n}ski, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every $r\geq 3$ the class of $K_r$-free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth., Comment: 27 pages; v2: removed Question 17 which was straightforwardly false; v3: we prove related results for tournaments, hypergraphs and infinite families of graphs

The Gy\'arf\'as-Sumner conjecture says that for every forest $H$ and every integer $k$, if $G$ is $H$-free and does not contain a clique on $k$ vertices then it has bounded chromatic number. (A graph is $H$-free if it does not contain an induced copy of $H$.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: R\"odl showed that, for every forest $H$, if $G$ is $H$-free and does not contain $K_{t,t}$ as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened R\"odl's result, showing that for every forest $H$, the bound on chromatic number can be taken to be polynomial in $t$. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$, if $G$ is $H$-free and does not contain as a subgraph the complete $d$-partite graph with parts of cardinality $t$, then its chromatic number is at most polynomial in $t$.

A theorem of Mader shows that every graph with average degree at least eight has a $K_6$ minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have $K_6$ minors, but minimum degree six is certainly not enough. For every $c>0$ there are arbitrarily large graphs with average degree at least $8-c$ and minimum degree at least six, with no $K_6$ minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every $c>0$ there are arbitrarily large bipartite graphs with average degree at least $8-c$ and no $K_6$ minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a $K_6$ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

It takes $n^2/4$ cliques to cover all the edges of a complete bipartite graph $K_{n/2,n/2}$, but how many cliques does it take to cover all the edges of a graph $G$ if $G$ has no $K_{t,t}$ induced subgraph? We prove that $O(|G|^{2-1/(2t)})$ cliques suffice; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon.

A pure pair of size $t$ in a graph $G$ is a pair $A,B$ of disjoint sets of $t$ vertices such that $A$ is either complete or anticomplete to $B$. It is known that, for every forest $H$, every graph on $n\ge2$ vertices that does not contain $H$ or its complement as an induced subgraph has a pure pair of size $\Omega(n)$; furthermore, this only holds when $H$ or its complement is a forest. In this paper, we look at pure pairs of size $n^{1-c}$, where $0c$.

A pure pair in a tournament $G$ is an ordered pair $(A,B)$ of disjoint subsets of $V(G)$ such that every vertex in $B$ is adjacent from every vertex in $A$. Which tournaments $H$ have the property that if $G$ is a tournament not containing $H$ as a subtournament, and $|G|>1$, there is a pure pair $(A,B)$ in $G$ with $|A|,|B|\ge c|G|$, where $c>0$ is a constant independent of $G$? Let us say that such a tournament $H$ has the strong EH-property. As far as we know, it might be that a tournament $H$ has this property if and only if its vertex set has a linear ordering in which its backedges form a forest. Certainly this condition is necessary, but we are far from proving sufficiency. We make a small step in this direction, showing that if a tournament can be ordered with at most three backedges then it has the strong EH-property (except for one case, that we could not decide). In particular, every tournament with at most six vertices has the property, except for three that we could not decide. We also give a seven-vertex tournament that does not have the strong EH-property. This is related to the Erdos-Hajnal conjecture, which in one form says that for every tournament $H$ there exists $τ>0$ such that every tournament $G$ not containing $H$ as a subtournament has a transitive subtournament of cardinality at least $|G|^τ$. Let us say that a tournament $H$ satisfying this has the EH-property. It is known that every tournament with the strong EH-property also has the EH-property; so our result extends work by Berger, Choromanski and Chudnovsky, who proved that every tournament with at most six vertices has the EH-property, except for one that they did not decide.

Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is still an exponential gap between the best known lower and upper bounds. For $k$-uniform hypergraphs, the bounds are of tower-type, where the height grows with $k$. Here, we give a multidimensional generalisation of Ramsey's Theorem to Cartesian products of graphs, proving that a doubly exponential upper bound suffices in every dimension. More precisely, we prove that for every positive integers $r,n,d$, in any $r$-colouring of the edges of the Cartesian product $\square^{d} K_N$ of $d$ copies of $K_N$, there is a copy of $\square^{d} K_n$ such that the edges in each direction are monochromatic, provided that $N\geq 2^{2^{C_drn^{d}}}$. As an application of our approach we also obtain improvements on the multidimensional Erd\H{o}s-Szekeres Theorem proved by Fishburn and Graham $30$ years ago. Their bound was recently improved by Buci\'c, Sudakov, and Tran, who gave an upper bound that is triply exponential in four or more dimensions. We improve upon their results showing that a doubly expoenential upper bounds holds any number of dimensions.

We investigate a generalisation of permutation networks. We say a sequence $T=(T_1,\dots,T_\ell)$ of transpositions in $S_n$ forms a $t$-reachability network if for every choice of $t$ distinct points $x_1, \dots, x_t\in \{1,\dots,n\}$, there is a subsequence of $T$ whose composition maps $j$ to $x_j$ for every $1\leq j\leq t$. When $t=n$, then any permutation in $S_n$ can be created, and $T$ is a permutation network. Waksman [JACM, 1968] showed that the shortest permutation networks have length about $n \log_2n$. In this paper, we investigate the shortest $t$-reachability networks. Our main result settles the case of $t=2$: the shortest $2$-reachability network has length $\lceil 3n/2\rceil-2 $. For fixed $t$, we give a simple randomised construction which shows there exist $t$-reachability networks using $(2+o_t(n))n$ transpositions. We also study the case where all transpositions are of the form $(1, \cdot)$, separating 2-reachability from the related probabilistic variant of 2-uniformity. Many interesting questions are left open., Comment: 15 pages, 1 figure

Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.

Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in-the-loop to label the data. The process of determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other one where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required to cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose as a conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions to handle errors or inconsistencies in the experts' answers., Accepted at Neurips 2021. The main part is 14 pages long, the rest is an appendix containing the long version of the proofs

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very dense or very sparse. More precisely, let us say that a graph F on n vertices is c-restricted if either F or its complement has maximum degree at most cn. Rodl proved that for every graph H, and every c>0, every H-free graph G has a linear-sized set of vertices inducing a c-restricted graph. We strengthen Rodl's result as follows: for every graph H, and all c>0, every H-free graph can be partitioned into a bounded number of subsets inducing c-restricted graphs.

This paper shows that $K_t$-minor-free (and $K_{s, t}$-minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_m$. Our results include optimal bounds on the treewidth of $H$ and optimal bounds (to within a constant factor) on $m$ in terms of the number of vertices of $G$ and the treewidth of $G$. These results follow from a more general theorem whose corollaries include a strengthening of the celebrated separator theorem of Alon, Seymour, and Thomas [J. Amer. Math. Soc. 1990] and the Planar Graph Product Structure Theorem of Dujmovi\'c et al. [J. ACM 2020]., Comment: Main results are not in v1. Theorem 4 is new in v3. v5 is a major update, now with a proof of the Planar Graph Product Structure Theorem. v6 includes applications to p-centred colouring and appendix on simple treewidth

The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. In 1976, Giles proved that any tree on $n\geq 6$ vertices can be reconstructed from its $\ell$-deck for $\ell \geq n-2$. Our main theorem states that it is enough to have $\ell\geq (8/9+o(1))n$, making substantial progress towards a conjecture of N\'ydl from 1990. In addition, we can recognise connectedness from the $\ell$-deck if $\ell\geq 9n/10$, and reconstruct the degree sequence from the $\ell$-deck if $\ell\ge \sqrt{2n\log(2n)}$. All of these results are significant improvements on previous bounds., Comment: 24 pages, fixed several typos

Background Lateral wedge insoles (LWI), standalone or with medial arch support (supported-LWI), have been thoroughly investigated for their effects on modifying gait biomechanics for people with knee osteoarthritis. However, plantar pressure distribution between these insole types has not been investigated and could provide insight towards insole prescription with concomitant foot symptoms taken into consideration. Methods In a sample of healthy individuals (n = 40), in-shoe plantar pressure was measured during walking with LWI, with or without medial arch support (variable- and uniform-stiffness designs), and a flat control insole condition. Pressure data from the plantar surface of the foot were divided into seven regions: medial/lateral rearfoot, midfoot, medial/central/lateral forefoot, hallux. Plantar pressure outcomes assessed were the medial-lateral pressure index (MLPI) for the whole foot, and the peak pressure, pressure-time integral (PTI), and contact area in each plantar region. Comfort in each insole condition was rated as a change relative to the flat control insole condition. Repeated-measures analyses of variance were calculated to compare the plantar pressure outcomes between insole conditions. Results Regionally, medial rearfoot and forefoot pressure were reduced by all wedged insoles, with the variable-stiffness supported-wedge showing greater reductions than the standalone wedge. Lateral rearfoot and forefoot pressure were reduced by both supported-LWI, but unchanged by the standalone wedge. In the midfoot, the standalone wedge maintained pressure but reduced regional contact area, while both supported-LWI increased midfoot pressure and contact area. All LWI increased the MLPI, indicating a lateral shift in plantar pressure distribution throughout the weightbearing phase of gait. Comfort ratings were not significantly different between insole conditions. Conclusions Regional differences in plantar pressure may help determine an appropriate lateral wedge insole variation to avoid exacerbation of concomitant foot symptoms by minimizing pressure in symptomatic regions. Lateral shifts in plantar pressure distribution were observed in all laterally wedged conditions, including one supported-LWI that was previously shown to be biomechanically ineffective for modifying knee joint load distribution. Thus, shifts in foot centre of pressure may not be a primary mechanism by which LWI can modify knee joint load distribution for people with knee osteoarthritis.

We show that for every positive integer $k$, any tournament can be partitioned into at most $2^{ck}$ $k$-th powers of paths. This result is tight up to the exponential constant. Moreover, we prove that for every $\varepsilon>0$ and every integer $k$, any tournament on $n\ge \varepsilon^{-Ck}$ vertices which is $\varepsilon$-far from being transitive contains the $k$-th power of a cycle of length $\Omega(\varepsilon n)$; both bounds are tight up to the implied constants., Comment: 17 pages

Additional file 1.

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours., Comment: This paper is essentially a combination of arXiv:2007.03582 and the non-algorithmic part of arXiv:2007.08771, where some results in arXiv:2007.03582 are strengthened. v2: fix the authors names. v3: update based on referees' comments, improve the bound for layered treewidth in Theorem 1.12 from 12 to 1, and simplify the proof without the use of fat bananas

The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner recently showed that, for $n\geq29$, the number of edges of a graph $G$ can be computed from any deck missing 2 cards. We show that, for sufficiently large $n$, the number of edges can be computed from any deck missing at most $\frac1{20}\sqrt{n}$ cards., Comment: 15 pages

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each monochromatic component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with monochromatic components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal., Comment: 35 pages, 4 figures - v3: correction of the statements of Theorem 5.2, Corollary 5.3 and Theorem 5.9. Most of the results in this paper have been merged to arXiv:2012.02435

Tur��n's Theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of Erd��s and Simonovits shows that if a $K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges, then it is close to being $r$-partite. In this paper we determine exactly the $K_{r+1}$-free graphs with at least $m$ edges that are farthest from being $r$-partite, for any $m\ge t_r(n) - ��_r n^2$. This extends work by Erd��s, Gy��ri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidick�� and Pfender., 17 pages, 2 figures

Models of parking in which cars are placed randomly and then move according to a deterministic rule have been studied since the work of Konheim and Weiss in the 1960s. Recently, Damron, Gravner, Junge, Lyu, and Sivakoff introduced a model in which cars are both placed and move at random. Independently at each point of a Cayley graph $G$, we place a car with probability $p$, and otherwise an empty parking space. Each car independently executes a random walk until it finds an empty space in which to park. In this paper we introduce three new techniques for studying the model, namely the space-based parking model, and the strategies for parking and for car removal. These allow us to study the original model by coupling it with models where parking behaviour is easier to control. Applying our methods to the one-dimensional parking problem in $\mathbb{Z}$, we improve on previous work, showing that for $p, Comment: 28 pages

Background Phenytoin is the recommended second-line intravenous anticonvulsant for treatment of paediatric convulsive status epilepticus in the UK; however, some evidence suggests that levetiracetam could be an effective and safer alternative. This trial compared the efficacy and safety of phenytoin and levetiracetam for second-line management of paediatric convulsive status epilepticus.Methods This open-label, randomised clinical trial was undertaken at 30 UK emergency departments at secondary and tertiary care centres. Participants aged 6 months to under 18 years, with convulsive status epilepticus requiring second-line treatment, were randomly assigned (1:1) using a computer-generated randomisation schedule to receive levetiracetam (40 mg/kg over 5 min) or phenytoin (20 mg/kg over at least 20 min), stratified by centre. The primary outcome was time from randomisation to cessation of convulsive status epilepticus, analysed in the modified intention-to-treat population (excluding those who did not require second-line treatment after randomisation and those who did not provide consent). This trial is registered with ISRCTN, number ISRCTN22567894.Findings Between July 17, 2015, and April 7, 2018, 1432 patients were assessed for eligibility. After exclusion of ineligible patients, 404 patients were randomly assigned. After exclusion of those who did not require second-line treatment and those who did not consent, 286 randomised participants were treated and had available data: 152 allocated to levetiracetam, and 134 to phenytoin. Convulsive status epilepticus was terminated in 106 (70%) children in the levetiracetam group and in 86 (64%) in the phenytoin group. Median time from randomisation to cessation of convulsive status epilepticus was 35 min (IQR 20 to not assessable) in the levetiracetam group and 45 min (24 to not assessable) in the phenytoin group (hazard ratio 1·20, 95% CI 0·91–1·60; p=0·20). One participant who received levetiracetam followed by phenytoin died as a result of catastrophic cerebral oedema unrelated to either treatment. One participant who received phenytoin had serious adverse reactions related to study treatment (hypotension considered to be immediately life-threatening [a serious adverse reaction] and increased focal seizures and decreased consciousness considered to be medically significant [a suspected unexpected serious adverse reaction]). Interpretation Although levetiracetam was not significantly superior to phenytoin, the results, together with previously reported safety profiles and comparative ease of administration of levetiracetam, suggest it could be an appropriate alternative to phenytoin as the first-choice, second-line anticonvulsant in the treatment of paediatric convulsive status epilepticus.

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erd\H{o}s-R\'enyi random graph $G(n,m)$. Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model., Comment: 77 pages

We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. Using initial monomials, projections of the underlying vector space onto subspaces, and the interior product, we find analogues of local and global LYM inequalities, the Erd��s-Ko-Rado theorem, and the Ahlswede-Khachatrian bound for $t$-intersecting hypergraphs. Using these tools, we prove a new extension of the Two Families Theorem of Bollob��s, giving a weighted bound for subspace configurations satisfying a skew cross-intersection condition. We also verify a recent conjecture of Gerbner, Keszegh, Methuku, Abhishek, Nagy, Patk��s, Tompkins, and Xiao on pairs of set systems satisfying both an intersection and a cross-intersection condition., 29 pages, substantial revision: new results in sections 2.5 (exterior downwards local LYM), 2.6 (exterior Ahslwede-Khachatrian bound), and 5 (proof of a conjecture of Gerbner et al, arxiv:1910.04666[math.CO])

The Internet of Things and the lure of smart cities are poised to revolutionize the urban areas of North America. Digital technology has introduced ubiquitous communication and influenced the organization of urban areas in North America, and together this has changed the ways in which people use urban public spaces. Now, the possibilities of the integration of digital technology into the physical infrastructure of the city has technology companies eager to partner with municipalities to realize the economic and managerial benefits of big data. The realities of the implementation of the smart city concept, however, has raised myriad concern around the role of private interests in public life with regards to privacy, ownership, control, and inequality. Many of these concerns play out in public spaces, as they are integral to the enactment of public life in cities while also increasingly funded, and therefore influenced, by private interests. What, then, are future programmatic and technological possibilities for urban public space that seize the opportunities while addressing the concerns? This project proposal first seeks to understand the historical and contemporary roles and functions of urban public space and real estate development, as well as big data. Then, it explores the influence of technology on the human understanding and organization of space to unpack the influence of the Internet of Things. Finally, a design project is proposed for the public space in Sidewalk Toronto’s Quayside development that seeks to address these phenomena through the thinking of the philosopher Hannah Arendt.

INTRODUCTION: There is a paucity of literature comparing the views and perceptions of medical students and surgical faculty regarding the surgical curriculum. Additionally, little evidence is available illustrating the prevalence of surgical mentors and role models, as well astheirspecific characteristics. Comparing the learning climates and current state of mentorship during undergraduate surgical training between developing and developed countries may offer insight into curricular improvement, and may shed light on methods to improve and stimulate surgical interest amongst medical students globally. METHODOLOGY: An electronic, online questionnaire was anonymously distributed to medical students and surgical faculty at the University of Cape Town, South Africa, and Karolinska Institutet, Sweden. The questionnaire explored the perceptions of medical students and surgical faculty regarding the current undergraduate surgical curriculum, existing clinical and theoretical instructional methods, as well as mentorship and role models within the surgical discipline. RESULTS: A total of 120 students (response rate of 24.4%) and 41 faculty (response rate of 74.5%) responded. Compared to South African faculty, Swedish faculty were predominantly male and were significantly older (p=0.009). Medical students desired more hours of instruction compared to faculty (p=0.017). South African students expected to study more hours compared to Swedish students (p=0.029). There was general agreement that ‘small-group tutorials’ was the area students learn the most from, whereas students reported ‘lectures’ least helpful. Registrars were reported as the first person students should consult regarding patient care. A large proportion (42.5%) of medical students believed that faculty viewed students as an inconvenience, and 35.0% of students believed that faculty would rather not have students on the clinical team. Faculty believed the current surgical curriculum was less adequate compared to medical students (p=0.010). A total of 41 (34.2%) students stated they had a mentor during their surgical training, which was significantly different to the perception of faculty that students ought to have a mentor during their undergraduate surgical training (p< 0.001). A significant difference was found between students from South Africa and Sweden in the number reported to have had a mentor (p< 0.001). The majority of respondents believed that registrars were the best role model. With regards to the most important qualities of a mentor, students rated encouragement, adequate supervision, setting of fair expectations, and teaching skills significantly higher compared to faculty (p=0.037, p=0.007, p=0.002, and p=0.010 respectively). CONCLUSIONS: Significant differences exist between surgical faculty and medical student perceptions of undergraduate surgical training and mentorship, as assessed in cohorts from a developing and a developed country. In order to increase surgical interest amongst undergraduate medical students, it is imperative for surgical educators to be aware of these differences, and to find specific strategies to bridge this gap.