4,424 results on '"Scott, Alex"'
Search Results
2. The Moderating Effect of COVID-19 on the Relationship between Spot Market Prices and Capital Investment in the Motor-Carrier Sector
- Author
-
Miller, Jason W., Darby, Jessica L., and Scott, Alex
- Published
- 2022
3. Lower bounds for graph reconstruction with maximal independent set queries
- Author
-
Michel, Lukas and Scott, Alex
- Subjects
Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics - Abstract
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $\Omega(\Delta^2 \log(n / \Delta) / \log \Delta)$ queries to reconstruct $n$-vertex graphs of maximum degree $\Delta$ with success probability at least $1/2$, and we further improve this lower bound to $\Omega(\Delta^2 \log(n / \Delta))$ for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least $\Omega(\Delta^3 \log n / \log \Delta)$ queries. This improves bounds of Konrad, O'Sullivan, and Traistaru, and answers one of their questions. The proof of the lower bound for deterministic non-adaptive algorithms relies on a connection to cover-free families, for which we also improve known bounds., Comment: 12 pages
- Published
- 2024
4. Graphs without a 3-connected subgraph are 4-colorable
- Author
-
Bonnet, Édouard, Feghali, Carl, Nguyen, Tung, Scott, Alex, Seymour, Paul, Thomassé, Stéphan, and Trotignon, Nicolas
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,05C15, 05C40 ,G.2.2 - Abstract
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible., Comment: 13 pages
- Published
- 2024
5. A note on graphs of $k$-colourings
- Author
-
Hogan, Emma, Scott, Alex, Tamitegama, Youri, and Tan, Jane
- Subjects
Mathematics - Combinatorics ,05C31 (Primary) 05C15 (Secondary) - Abstract
For a graph $G$, the $k$-colouring graph of $G$ has vertices corresponding to proper $k$-colourings of $G$ and edges between colourings that differ at a single vertex. The graph supports the Glauber dynamics Markov chain for $k$-colourings, and has been extensively studied from both extremal and probabilistic perspectives. In this note, we show that for every graph $G$, there exists $k$ such that $G$ is uniquely determined by its $k$-colouring graph, confirming two conjectures of Asgarli, Krehbiel, Levinson and Russell. We further show that no finite family of generalised chromatic polynomials for $G$, which encode induced subgraph counts of its colouring graphs, uniquely determine $G$., Comment: 10 pages, 3 figures
- Published
- 2024
6. Non-Homotopic Drawings of Multigraphs
- Author
-
Girão, António, Illingworth, Freddie, Scott, Alex, and Wood, David R.
- Subjects
Mathematics - Combinatorics - Abstract
A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex, and is $k$-crossing if every pair of edges (self-)intersects at most $k$ times. We prove that the number of edges in an $n$-vertex non-homotopic $k$-crossing multigraph is at most $6^{13 n (k + 1)}$, which is a big improvement over previous upper bounds. We also study this problem in the setting of monotone drawings where every edge is an x-monotone curve. We show that the number of edges, $m$, in such a drawing is at most $2 \binom{2n}{k + 1}$ and the number of crossings is $\Omega\bigl(\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr)$. For fixed $k$ these bounds are both best possible up to a constant multiplicative factor., Comment: 19 pages
- Published
- 2024
7. A counterexample to the coarse Menger conjecture
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics ,05C12, 05C38 - Abstract
It was conjectured, independently by two sets of authors, that for all integers $k,d\ge 1$ there exists $\ell>0$, such that if $S,T$ are subsets of vertices of a graph $G$, then either there are $k$ paths between $S,T$, pairwise at distance at least $d$, or there is a set $X\subseteq V(G)$ with $|X|\le k-1$ such that every path between $S,T$ contains a vertex with distance at most $\ell$ from some member of $X$. The result is known for $k\le 2$, but we will show that it is false for all $k\ge 3$, even if $G$ is constrained to have maximum degree at most three. We also give a proof of the result when $k=2$ that is simpler than the previous proofs.
- Published
- 2024
8. Reconstruction of shredded random matrices
- Author
-
Balister, Paul, Kronenberg, Gal, Scott, Alex, and Tamitegama, Youri
- Subjects
Mathematics - Combinatorics - Abstract
A matrix is given in ``shredded'' form if we are presented with the multiset of rows and the multiset of columns, but not told which row is which or which column is which. The matrix is reconstructible if it is uniquely determined by this information. Let $M$ be a random binary $n\times n$ matrix, where each entry independently is $1$ with probability $p=p(n)\le\frac12$. Atamanchuk, Devroye and Vicenzo introduced the problem and showed that $M$ is reconstructible with high probability for $p\ge (2+\varepsilon)\frac{1}{n}\log n$. Here we find that the sharp threshold for reconstructibility is at $p\sim\frac{1}{2n}\log n$., Comment: 17 pages
- Published
- 2024
9. Pure Pairs. VIII. Excluding a Sparse Graph
- Author
-
Scott, Alex, Seymour, Paul, and Spirkl, Sophie
- Published
- 2024
- Full Text
- View/download PDF
10. Induced subgraph density. VI. Bounded VC-dimension
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
We confirm a conjecture of Fox, Pach, and Suk, that for every $d>0$, there exists $c>0$ such that every $n$-vertex graph of VC-dimension at most $d$ has a clique or stable set of size at least $n^c$. This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erd\H{o}s-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lov\'asz and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper., Comment: 11 pages, minor revisions
- Published
- 2023
11. Induced subgraph density. VII. The five-vertex path
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
We prove the Erd\H{o}s-Hajnal conjecture for the five-vertex path $P_5$; that is, there exists $c>0$ such that every $n$-vertex graph with no induced $P_5$ has a clique or stable set of size at least $n^c$. This completes the verification of the Erd\H{o}s-Hajnal property of all five-vertex graphs. Indeed, we show a stronger statement, that $P_5$ satisfies the polynomial version of a theorem of R\"odl. To achieve this, we combine simple probabilistic and structural ideas with the iterative sparsification framework introduced in the series., Comment: 15 pages
- Published
- 2023
12. Graphs with arbitrary Ramsey number and connectivity
- Author
-
Ahme, Isabel and Scott, Alex
- Subjects
Mathematics - Combinatorics - Abstract
The Ramsey number $r(G)$ of a graph $G$ is the minimum number $N$ such that any red-blue colouring of the edges of $K_N$ contains a monochromatic copy of $G$. Pavez-Sign\'e, Piga and Sanhueza-Matamala proved that for any function $n\leq f(n) \leq r(K_n)$, there is a sequence of connected graphs $(G_n)_{n\in \mathbb{N}}$ with $|V(G_n)|=n$ such that $r(G_n)=\Theta(f(n))$ and conjectured that $G_n$ can additionally have arbitrarily large connectivity. In this note we prove their conjecture.
- Published
- 2023
13. Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
- Author
-
Michel, Lukas and Scott, Alex
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity - Abstract
Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective approach to understanding this: a substantial literature shows that when a small amount of random noise is added to input data, local search algorithms typically run in polynomial or quasi-polynomial time. In this paper, we provide the first example where a local search algorithm for the Max-Cut problem fails to be efficient in the framework of smoothed analysis. Specifically, we construct a graph with $n$ vertices where the smoothed runtime of the 3-FLIP algorithm can be as large as $2^{\Omega(\sqrt{n})}$. Additionally, for the setting without random noise, we give a new construction of graphs where the runtime of the FLIP algorithm is $2^{\Omega(n)}$ for any pivot rule. These graphs are much smaller and have a simpler structure than previous constructions., Comment: 19 pages, 3 figures, changes to the abstract, introduction, and conclusion
- Published
- 2023
14. Flashes and Rainbows in Tournaments
- Author
-
Girão, António, Illingworth, Freddie, Michel, Lukas, Savery, Michael, and Scott, Alex
- Published
- 2024
- Full Text
- View/download PDF
15. Game Connectivity and Adaptive Dynamics
- Author
-
Johnston, Tom, Savery, Michael, Scott, Alex, and Tarbush, Bassel
- Subjects
Economics - Theoretical Economics ,Computer Science - Computer Science and Game Theory ,Mathematics - Combinatorics - Abstract
We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that almost every game that is 'generic' (without indifferences) and has a pure Nash equilibrium and a 'large' number of players is connected, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in almost every large generic game that has one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in every generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity., Comment: 39 pages; v3: improved the introduction and added more discussion of our results. Other minor changes
- Published
- 2023
16. Boundary rigidity of 3D CAT(0) cube complexes
- Author
-
Haslegrave, John, Scott, Alex, Tamitegama, Youri, and Tan, Jane
- Subjects
Mathematics - Combinatorics ,Mathematics - Geometric Topology ,57M15 - Abstract
The boundary rigidity problem is a classical question from Riemannian geometry: if $(M, g)$ is a Riemannian manifold with smooth boundary, is the geometry of $M$ determined up to isometry by the metric $d_g$ induced on the boundary $\partial M$? In this paper, we consider a discrete version of this problem: can we determine the combinatorial type of a finite cube complex from its boundary distances? As in the continuous case, reconstruction is not possible in general, but one expects a positive answer under suitable contractibility and non-positive curvature conditions. Indeed, in two dimensions Haslegrave gave a positive answer to this question when the complex is a finite quadrangulation of the disc with no internal vertices of degree less than $4$. We prove a $3$-dimensional generalisation of this result: the combinatorial type of a finite CAT(0) cube complex with an embedding in $\mathbb{R}^3$ can be reconstructed from its boundary distances. Additionally, we prove a direct strengthening of Haslegrave's result: the combinatorial type of any finite 2-dimensional CAT(0) cube complex can be reconstructed from its boundary distances., Comment: 30 pages, 10 figures
- Published
- 2023
17. Induced subgraph density. V. All paths approach Erdos-Hajnal
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
The Erd\H{o}s-Hajnal conjecture says 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 $2^{c\log|G|}$ (a graph is ``$H$-free'' if no induced subgraph is isomorphic to $H$). The conjecture is known when $H$ is a path with at most four vertices, but remains open for longer paths. For the five-vertex path, Blanco and Buci\'c recently proved a bound of $2^{c(\log |G|)^{2/3}}$; for longer paths, the best existing bound is $2^{c(\log|G|\log\log|G|)^{1/2}}$. We prove a much stronger result: for any path $P$, every $P$-free graph $G$ has a clique or stable set of size at least $2^{(\log |G|)^{1-o(1)}}$. We strengthen this further, weakening the hypothesis that $G$ is $P$-free by a hypothesis that $G$ does not contain ``many'' copies of $P$, and strengthening the conclusion, replacing the large clique or stable set outcome with a ``near-polynomial'' version of Nikiforov's theorem.
- Published
- 2023
18. Induced $C_4$-free subgraphs with large average degree
- Author
-
Du, Xiying, Girão, António, Hunter, Zach, McCarty, Rose, and Scott, Alex
- Subjects
Mathematics - Combinatorics - Abstract
We prove that there exists a constant $C$ so that, for all $s,k \in \mathbb{N}$, if $G$ has average degree at least $k^{Cs^3}$ and does not contain $K_{s,s}$ as a subgraph then it 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. We give several applications of this result, including short and streamlined proofs of the following two corollaries. We show that there exists a constant $C$ so that, for all $s,k \in \mathbb{N}$, if $G$ has average degree at least $k^{Cs^3}$ and does not contain $K_{s,s}$ as a subgraph then it 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$. We also show that for any hereditary degree-bounded class $\mathcal{F}$, there exists a constant $C=C_\mathcal{F}$ so that $C^{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: 19 pages. Submitted
- Published
- 2023
19. Induced subgraphs density. IV. New graphs with the Erd\H{o}s-Hajnal property
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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$ (a graph is $H$-free if it has no induced subgraph isomorphic to $H$). Alon, Pach, and Solymosi reduced the Erd\H{o}s-Hajnal conjecture to the case when $H$ is {\em 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. More generally, say a graph is {\em buildable} if every prime induced subgraph with at least three vertices has a vertex of degree one. We prove that if $H_1$ and $\overline{H_2}$ are buildable, there exists $c>0$ such that every graph $G$ that is both $H_1$-free and $H_2$-free has a clique or a stable set of size at least $|G|^c$. Our proof uses a new technique of ``iterative sparsification'', where we pass to a sequence of successively more restricted induced subgraphs. This approach also extends to ordered graphs and to tournaments. For ordered graphs, we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths; and for tournaments, we obtain infinitely many new prime tournaments that satisfy the Erd\H{o}s-Hajnal conjecture (in tournament form).
- Published
- 2023
20. Induced subgraph density. III. Cycles and subdivisions
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics ,05C35, 05C42, 05C69 - Abstract
We show that for every two cycles $C,D$, there exists $c>0$ such that if $G$ is both $C$-free and $\overline{D}$-free then $G$ has a clique or stable set of size at least $|G|^c$. ("$H$-free" means with no induced subgraph isomorphic to $H$, and $\overline{D}$ denotes the complement graph of $D$.) Since the five-vertex cycle $C_5$ is isomorphic to its complement, this extends the earlier result that $C_5$ satisfies the Erd\H{o}s-Hajnal conjecture. It also unifies and strengthens several other results. The results for cycles are special cases of results for subdivisions, as follows. Let $H,J$ be obtained from smaller graphs by subdividing every edge exactly twice. We will prove that there exists $c>0$ such that if $G$ is both $H$-free and $\overline{J}$-free then $G$ has a clique or stable set of size at least $|G|^c$. And the same holds if $H$ and/or $J$ is obtained from a graph bychoosing a forest $F$ and subdividing every edge not in $F$ at least five times. Our proof uses the framework of iterative sparsification developed in other papers of this series. Along the way, we will also give a short and simple proof of a celebrated result of Fox and Sudakov, that says that for all $H$, every $H$-free graph contains either a large stable set or a large complete bipartite subgraph., Comment: 20 pages
- Published
- 2023
21. Induced subgraph density. II. Sparse and dense sets in cographs
- Author
-
Fox, Jacob, Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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$.
- Published
- 2023
22. Some results and problems on tournament structure
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2023
23. Flashes and rainbows in tournaments
- Author
-
Girão, António, Illingworth, Freddie, Michel, Lukas, Savery, Michael, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,05C55, 05C35, 05C38 - Abstract
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
- Published
- 2023
24. The structure and density of $k$-product-free sets in the free semigroup
- Author
-
Illingworth, Freddie, Michel, Lukas, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Mathematics - Group Theory ,20M05, 05D05 - Abstract
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
- Published
- 2023
25. Publisher Erratum: Flashes and Rainbows in Tournaments
- Author
-
Girão, António, Illingworth, Freddie, Michel, Lukas, Savery, Michael, and Scott, Alex
- Published
- 2024
- Full Text
- View/download PDF
26. MRGPRX2-mediated mast cell activation by substance P from overloaded human tenocytes induces inflammatory and degenerative responses in tendons
- Author
-
Mousavizadeh, Rouhollah, Waugh, Charlie M., McCormack, Robert G., Cairns, Brian E., and Scott, Alex
- Published
- 2024
- Full Text
- View/download PDF
27. Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
- Author
-
Girão, António, Illingworth, Freddie, Powierski, Emil, Savery, Michael, Scott, Alex, Tamitegama, Youri, and Tan, Jane
- Published
- 2024
- Full Text
- View/download PDF
28. On a problem of El-Zahar and Erdoos
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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$.
- Published
- 2023
29. Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2023
30. A note on the Gy\'arf\'as-Sumner conjecture
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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$.
- Published
- 2023
31. Reconstructing a point set from a random subset of its pairwise distances
- Author
-
Girão, António, Illingworth, Freddie, Michel, Lukas, Powierski, Emil, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,05C80 - Abstract
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$., Comment: 13 pages
- Published
- 2023
32. Induced subgraph density. I. A loglog step towards Erdos-Hajnal
- Author
-
Bucić, Matija, Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2023
33. Counting graphic sequences via integrated random walks
- Author
-
Balister, Paul, Donderwinkel, Serte, Groenland, Carla, Johnston, Tom, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
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., Comment: 43 pages, 2 figures
- Published
- 2023
34. A Note on the Gyárfás–Sumner Conjecture
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Published
- 2024
- Full Text
- View/download PDF
35. Invertibility of digraphs and tournaments
- Author
-
Alon, Noga, Powierski, Emil, Savery, Michael, Scott, Alex, and Wilmer, Elizabeth
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics - Abstract
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$, $\textrm{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 $k\in\mathbb{N}$ and tournament $T$, the problem of deciding whether $\textrm{inv}(T)\leq k$ is solvable in time $O_k(|V(T)|^2)$, which is tight for all $k$. In particular, the problem is fixed-parameter tractable when parameterised by $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 $\textrm{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$., Comment: 25 pages; v3: corrected abstract formatting; v2: minor changes incorporating referees' comments, and addition of Conjecture 3
- Published
- 2022
- Full Text
- View/download PDF
36. Induced paths in graphs without anticomplete cycles
- Author
-
Nguyen, Tung, Scott, Alex, and Seymour, Paul
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2022
37. Shotgun assembly of random graphs
- Author
-
Johnston, Tom, Kronenberg, Gal, Roberts, Alexander, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,Mathematics - Probability - Abstract
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
- Published
- 2022
38. Clique covers of H-free graphs
- Author
-
Nguyen, Tung, Scott, Alex, Seymour, Paul, and Thomasse, Stephan
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2022
39. A multidimensional Ramsey Theorem
- Author
-
Girão, António, Kronenberg, Gal, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics - Abstract
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.
- Published
- 2022
40. Perfect shuffling with fewer lazy transpositions
- Author
-
Groenland, Carla, Johnston, Tom, Radcliffe, Jamie, and Scott, Alex
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
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., Comment: 23 pages, 5 figures, 1 table
- Published
- 2022
41. Short reachability networks
- Author
-
Groenland, Carla, Johnston, Tom, Radcliffe, Jamie, and Scott, Alex
- Subjects
Mathematics - Combinatorics - Abstract
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$, 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: 13 pages, 1 figure
- Published
- 2022
42. Defective Colouring of Hypergraphs
- Author
-
Girão, António, Illingworth, Freddie, Scott, Alex, and Wood, David R.
- Subjects
Mathematics - Combinatorics ,05C15 - Abstract
We prove that the vertices of every $(r + 1)$-uniform hypergraph with maximum degree $\Delta$ may be coloured with $c(\frac{\Delta}{d + 1})^{1/r}$ colours such that each vertex is in at most $d$ monochromatic edges. This result, which is best possible up to the value of the constant $c$, generalises the classical result of Erd\H{o}s and Lov\'asz who proved the $d = 0$ case., Comment: 11 pages; revised argument in section 2.2, results unchanged
- Published
- 2022
43. Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path
- Author
-
Scott, Alex, Seymour, Paul, and Spirkl, Sophie
- Published
- 2023
- Full Text
- View/download PDF
44. A notion in motion
- Author
-
Scott, Alex
- Published
- 2016
45. Improved bounds for 1-independent percolation on $\mathbb{Z}^n$
- Author
-
Balister, Paul, Johnston, Tom, Savery, Michael, and Scott, Alex
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
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
- Published
- 2022
46. Balancing connected colourings of graphs
- Author
-
Illingworth, Freddie, Powierski, Emil, Scott, Alex, and Tamitegama, Youri
- Subjects
Mathematics - Combinatorics ,05C02 - Abstract
We show that the edges of any graph $G$ containing two edge-disjoint spanning trees can be blue/red coloured so that the blue and red graphs are connected and the blue and red degrees at each vertex differ by at most four. This improves a result of H\"orsch. We discuss variations of the question for digraphs, infinite graphs and a computational question, and resolve two further questions of H\"orsch in the negative., Comment: 23 pages, 22 figures
- Published
- 2022
- Full Text
- View/download PDF
47. Bipartite graphs with no $K_6$ minor
- Author
-
Chudnovsky, Maria, Scott, Alex, Seymour, Paul, and Spirkl, Sophie
- Subjects
Mathematics - Combinatorics - Abstract
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.
- Published
- 2022
48. Use of Augmented Reality (AR) to Aid Bioscience Education and Enrich Student Experience
- Author
-
Reeves, Laura E., Bolton, Edward, Bulpitt, Matthew, Scott, Alex, Tomey, Ian, Gates, Micah, and Baldock, Robert A.
- Abstract
In recent years, development of new technologies designed to enhance user experience have accelerated, often being used in modern media such as in films and games. Specifically, immersive experiences, such as virtual reality (VR) and augmented reality (AR), have redefined how digital media can be delivered, encouraging us to interact with and explore our environment. Reciprocally, as the power of these technologies has advanced, the associated costs to implement them have decreased, making them more cost-effective and feasible to deliver in a variety of settings. Despite the cost reduction, several issues remain with accessibility due to the knowledge base required to generate, optimise and deliver three-dimensional (3D)-digital content in both AR and VR. Here, we sought to integrate an AR-based experience into a level-4 biochemistry module in order to support the delivery of university lectures on protein structure and function. Traditionally, this topic would comprise two-dimensional still images of complex 3D structures. By combining a breadth of subject-specific and technological expertise from across the university, we developed an AR-enhanced learning experience hosted on the Zapworks AR platform. AR enabled full illustration of the complexity of these 3D structures, while promoting collaboration through a shared user experience. Assessing the impact of the AR experience via a formative test and survey revealed that despite only a modest increase in test performance, students overwhelmingly reported positively on the engaging nature and interactivity of AR. Critically, expanding our repertoire of content delivery formats will support the forward-thinking blended learning environments adopted across the higher education sector.
- Published
- 2021
49. Induced subgraphs of induced subgraphs of large chromatic number
- Author
-
Girão, António, Illingworth, Freddie, Powierski, Emil, Savery, Michael, Scott, Alex, Tamitegama, Youri, and Tan, Jane
- Subjects
Mathematics - Combinatorics ,Primary: 05C15, 05C55, Secondary: 05C20, 05C65 - Abstract
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: 26 pages; v4: final version incorporating the suggestions of referees and Jarik Ne\v{s}et\v{r}il, including simplified constructions and a new open question
- Published
- 2022
50. Pure pairs. X. Tournaments and the strong Erdos-Hajnal property
- Author
-
Chudnovsky, Maria, Scott, Alex, Seymour, Paul, and Spirkl, Sophie
- Subjects
Mathematics - Combinatorics - Abstract
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 $\tau>0$ such that every tournament $G$ not containing $H$ as a subtournament has a transitive subtournament of cardinality at least $|G|^\tau$. 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., Comment: Accepted manuscript; see DOI for journal version
- Published
- 2022
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.