About

Paul Seymour is the Albert Baldwin Dod Professor of Mathematics at Princeton University, holding positions in both the Department of Mathematics and the Program in Applied and Computational Math. His research primarily focuses on discrete mathematics, with an emphasis on graph theory. He is currently working on the structure of graphs with certain induced subgraphs forbidden, and has particular interests in the Erdős-Hajnal conjecture and the various conjectures of Gyarfas about chi-boundedness. Seymour's collaborative work includes joint research with Maria Chudnovsky and Robin Thomas, and he is actively involved in organizing the Princeton Discrete Math Seminar. His professional activities also include overseeing the Barbados graph theory workshops, with records of these events spanning from 2014 to 2026.

Research topics

• Discrete mathematics
• Mathematics
• Combinatorics
• Mathematical analysis

Selected publications

• On prime Cayley graphs

  Journal of Combinatorics · 2026-01-01

  article1st authorCorresponding
  PublisherDOI

• The Vertex Sets of Subtrees of a Tree

  The Electronic Journal of Combinatorics · 2026-04-14

  preprintOpen accessSenior author

  Let $\mathcal{F}$ be a set of subsets of a set $W$. When is there a tree $T$ with vertex set $W$ such that each member of $\mathcal{F}$ is the set of vertices of a subtree of $T$? It is necessary that $\mathcal{F}$ has the Helly property and the intersection graph of $\mathcal{F}$ is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of $W$ belongs to infinitely many infinite sets in $\mathcal{F}$.

  PublisherDOI

• Asymptotic structure. I. Coarse tree-width

  ArXiv.org · 2025-01-16

  preprintOpen accessSenior author

  In this paper, we develop a coarse analogue of treewidth. We prove that a graph $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of balls of bounded radius, if and only if $G$ admits a quasi-isometry to a graph with bounded tree-width. (The ``if'' half is easy, but the ``only if'' half is challenging.) This generalizes a recent result of Berger and Seymour, concerning tree-decompositions when each bag has bounded radius.

  PublisherOA PDFDOI

• Line-width and path-width

  ArXiv.org · 2025-09-20

  preprintOpen accessSenior author

  For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does not work nicely. The simplest extension that works nicely is to allow the indexing set to be any totally-ordered set, and then the corresponding decomposition is called a ``line-decomposition'', and the maximum bag size needed is called ``line-width''. In particular, the indexing set need not be a well-order; but the corresponding decomposition would be easier to use if it was. We show that if a graph has line-width at most $k$, it admits a well-ordered line-decomposition with width at most $2k$, and this is best possible.

  PublisherOA PDFDOI

• Asymptotic structure. VI. Distant paths across a disc

  ArXiv.org · 2025-09-08

  preprintOpen accessSenior author

  Menger's theorem says that, for $k\ge0$, if $S, T$ are sets of vertices in a graph $G$, then either there are $k + 1$ vertex-disjoint paths between $S$ and $T$, or there is a set X of at most $k$ vertices such that every $S$-$T$ path passes through $X$. The ``coarse Menger conjecture'' proposed a generalization of Menger's theorem for paths that are far apart: for all $k, c$ there exists $\ell$, such that for every graph $G$ and subsets $S, T \subset V (G)$, either there are $k + 1$ paths between $S$ and $T$, pairwise with distance more than $c$, or there is a set $X \subset V (G)$ of at most $k$ vertices such that every $S$-$T$ path has distance at most $\ell$ from $X$. This is known to be false, but may be true if $G$ is planar. Here we show that it is true if $G$ is planar and all vertices in $S \cup T$ are on the infinite region. In this case, we also obtain a linear-time algorithm to test for the existence of $k+ 1$ paths between $S$ and $T$, pairwise with distance more than $c$.

  PublisherOA PDFDOI

• Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture

  ArXiv.org · 2025-08-20

  preprintOpen accessSenior author

  Coarse graph theory concerns finding 'coarse' analogues of graph theory theorems, replacing disjointness with being far apart. One of the most interesting open questions is to find a coarse analogue of Menger's theorem, which characterizes when there are $k$ vertex-disjoint paths between two given sets $S,T$ of vertices of a graph. We showed in an earlier paper that the most natural such analogue is false, but a weaker statement remained as a popular open question. Here we show that the weaker statement is also false. More exactly, suppose that $S,T$ are sets of vertices of a graph $G$, and there do not exist $k$ paths between $S,T$, pairwise at distance at least $c$. To make an analogue of Menger's theorem, one would like to prove that there must be a small set $X\subseteq V(G)$ such that every $S-T$ path of $G$ passes close to a member of $X$: but how small and how close? In view of Menger's theorem, one would hope for $|X|

  PublisherOA PDFDOI

• Asymptotic structure. II. Path-width and additive quasi-isometry

  ArXiv.org · 2025-09-10

  preprintOpen accessSenior author

  We show that if a graph $G$ admits a quasi-isometry $ϕ$ to a graph $H$ of bounded path-width, then we can assign a non-negative integer length to each edge of $H$, such that the same function $ϕ$ is a quasi-isometry to this weighted version of $H$, with error only an additive constant.

  PublisherOA PDFDOI

• A counterexample to the coarse Menger conjecture

  Journal of Combinatorial Theory Series B · 2025-02-13 · 2 citations

  articleOpen accessSenior author

  Menger's well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G . Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger's theorem, when the k paths are required to be pairwise at some distance at least d . The result is known for k ≤ 2 , but we will show that it is false for all k ≥ 3 , even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2 .

  PublisherDOI

• Subdivisions and near-linear stable sets

  COMBINATORICA · 2025-07-04 · 1 citations

  articleOpen accessSenior author

  Abstract We prove that for every complete graph $$K_t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>t</mml:mi> </mml:msub> </mml:math> , all graphs G with no induced subgraph isomorphic to a subdivision of $$K_t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>t</mml:mi> </mml:msub> </mml:math> have a stable subset of size at least $$|G|/\operatorname {polylog}|G|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>G</mml:mi> <mml:mo>|</mml:mo> <mml:mo>/</mml:mo> <mml:mo>polylog</mml:mo> <mml:mo>|</mml:mo> <mml:mi>G</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:math> . This is close to best possible, because for $$t\ge 7$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>7</mml:mn> </mml:mrow> </mml:math> , not all such graphs G have a stable set of linear size, even if G is triangle-free.

  PublisherOA PDFDOI

• When all directed cycles have length three

  European Journal of Combinatorics · 2025-04-26

  articleOpen access1st authorCorresponding

  We give a construction to build all digraphs with the property that every directed cycle has length three.

  PublisherDOI

Recent grants

• DMS-EPRSC: Induced Subgraphs and Graph Structure

  NSF · $400k · 2022–2027

• Induced Subgraphs and Coloring

  NSF · $210k · 2018–2021

• FRG: Collaborative Research: The Four-Color Theorem and Beyond

  NSF · $283k · 2004–2008

• Collaborative Research: cliques, stable sets and approximate structure

  NSF · $240k · 2013–2018

• Tournament Immersion and Rao's Conjecture

  NSF · $220k · 2009–2013

Frequent coauthors

• Maria Chudnovsky

  191 shared

• Alex Scott

  University of Oxford

  156 shared

• Neil Robertson

  University of Edinburgh

  112 shared

• Sophie Spirkl

  University of Waterloo

  83 shared

• Robin Thomas

  Shri Jagdishprasad Jhabarmal Tibrewala University

  71 shared

• Rajan M. Thomas

  Children's Hospital of Philadelphia

  40 shared

• Nicolas Trotignon

  Laboratoire de l'Informatique du Parallélisme

  32 shared

• Alexander Schrijver

  Centrum Wiskunde & Informatica

  22 shared