Source author record

Jonathan A. Noel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Complexity

Catalog footprint

Research overview

11works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Characterization of quasirandom permutations by a pattern sum

It is known that a sequence Pi_i of permutations is quasirandom if and only if the pattern density of every 4-point permutation in Pi_i converges to 1/24. We show that there is a set S of 4-point permutations such that the sum of the pattern densities of the permutations from S in the permutations Pi_i converges to |S|/24 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.

preprint2022arXiv

Density maximizers of layered permutations

A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if $σ$ is a layered permutation, then the density of $σ$ in a permutation of order $n$ is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), R#5] claimed that the density of a layered permutation with layers of sizes $(a,1,b)$ where $a,b\geq2$ is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if $σ$ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of $σ$ . This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.

preprint2020arXiv

Finitely forcible graphons with an almost arbitrary structure

Graphons are analytic objects representing convergent sequences of large graphs. A graphon is said to be finitely forcible if it is determined by finitely many subgraph densities, i.e., if the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Such graphons appear in various scenarios, particularly in extremal combinatorics. Lovasz and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Kral and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every $\varepsilon>0$ that any graphon spans a $1-\varepsilon$ proportion of a finitely forcible graphon.

preprint2016arXiv

A Dichotomy Theorem for Circular Colouring Reconfiguration

The "reconfiguration problem" for circular colourings asks, given two $(p,q)$ -colourings $f$ and $g$ of a graph $G$ , is it possible to transform $f$ into $g$ by changing the colour of one vertex at a time such that every intermediate mapping is a $(p,q)$ -colouring? We show that this problem can be solved in polynomial time for $2\leq p/q <4$ and is PSPACE-complete for $p/q\geq 4$ . This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.

preprint2016arXiv

Weak regularity and finitely forcible graph limits

Graphons are analytic objects representing limits of convergent sequences of graphs. Lovász and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $\varepsilon$ -regular partition with the number of parts bounded by a polynomial in $\varepsilon^{-1}$ . We construct a finitely forcible graphon $W$ such that the number of parts in any weak $\varepsilon$ -regular partition of $W$ is at least exponential in $\varepsilon^{-2}/2^{5\log^*\varepsilon^{-2}}$ . This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.

preprint2015arXiv

Saturation in the Hypercube and Bootstrap Percolation

Let $Q_d$ denote the hypercube of dimension $d$ . Given $d\geq m$ , a spanning subgraph $G$ of $Q_d$ is said to be $(Q_d,Q_m)$ -saturated if it does not contain $Q_m$ as a subgraph but adding any edge of $E(Q_d)\setminus E(G)$ creates a copy of $Q_m$ in $G$ . Answering a question of Johnson and Pinto, we show that for every fixed $m\geq2$ the minimum number of edges in a $(Q_d,Q_m)$ -saturated graph is $Θ(2^d)$ . We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of $Q_d$ is said to be weakly $(Q_d,Q_m)$ -saturated if the edges of $E(Q_d)\setminus E(G)$ can be added to $G$ one at a time so that each added edge creates a new copy of $Q_m$ . Answering another question of Johnson and Pinto, we determine the minimum number of edges in a weakly $(Q_d,Q_m)$ -saturated graph for all $d\geq m\geq1$ . More generally, we determine the minimum number of edges in a subgraph of the $d$ -dimensional grid $P_k^d$ which is weakly saturated with respect to `axis aligned' copies of a smaller grid $P_r^m$ . We also study weak saturation of cycles in the grid.

preprint2014arXiv

A Proof of a Conjecture of Ohba

We prove a conjecture of Ohba which says that every graph $G$ on at most $2χ(G)+1$ vertices satisfies $χ_\ell(G)=χ(G)$ .

preprint2014arXiv

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices

Let $\text{ch}(G)$ denote the choice number of a graph $G$ (also called "list chromatic number" or "choosability" of $G$ ). Noel, Reed, and Wu proved the conjecture of Ohba that $\text{ch}(G)=χ(G)$ when $|V(G)|\le 2χ(G)+1$ . We extend this to a general upper bound: $\text{ch}(G)\le \max\{χ(G),\lceil({|V(G)|+χ(G)-1})/{3}\rceil\}$ . Our result is sharp for $|V(G)|\le 3χ(G)$ using Ohba's examples, and it improves the best-known upper bound for $\text{ch}(K_{4,\dots,4})$ .

preprint2014arXiv

Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings

This work brings together ideas of mixing graph colourings, discrete homotopy, and precolouring extension. A particular focus is circular colourings. We prove that all the $(k,q)$ -colourings of a graph $G$ can be obtained by successively recolouring a single vertex provided $k/q\geq 2col(G)$ along the lines of Cereceda, van den Heuvel and Johnson's result for $k$ -colourings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colourings coincide. As a corollary, we obtain an Albertson-type extension theorem for $(k,q)$ -precolourings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs $G$ for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role.

preprint2014arXiv

On Saturated $k$ -Sperner Systems

Given a set $X$ , a collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be $k$ -Sperner if it does not contain a chain of length $k+1$ under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. conjectured that, if $|X|$ is sufficiently large with respect to $k$ , then the minimum size of a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is $2^{k-1}$ . We disprove this conjecture by showing that there exists $\varepsilon>0$ such that for every $k$ and $|X| \geq n_0(k)$ there exists a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ with cardinality at most $2^{(1-\varepsilon)k}$ . A collection $\mathcal{F}\subseteq \mathcal{P}(X)$ is said to be an oversaturated $k$ -Sperner system if, for every $S\in\mathcal{P}(X)\setminus\mathcal{F}$ , $\mathcal{F}\cup\{S\}$ contains more chains of length $k+1$ than $\mathcal{F}$ . Gerbner et al. proved that, if $|X|\geq k$ , then the smallest such collection contains between $2^{k/2-1}$ and $O\left(\frac{\log{k}}{k}2^k\right)$ elements. We show that if $|X|\geq k^2+k$ , then the lower bound is best possible, up to a polynomial factor.

preprint2013arXiv

Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond

The \emph{choice number} of a graph $G$ , denoted $\ch(G)$ , is the minimum integer $k$ such that for any assignment of lists of size $k$ to the vertices of $G$ , there is a proper colouring of $G$ such that every vertex is mapped to a colour in its list. For general graphs, the choice number is not bounded above by a function of the chromatic number. In this thesis, we prove a conjecture of Ohba which asserts that $\ch(G)=χ(G)$ whenever $|V(G)|\leq 2χ(G)+1$ . We also prove a strengthening of Ohba's Conjecture which is best possible for graphs on at most $3χ(G)$ vertices, and pose several conjectures related to our work.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jonathan A. Noel

Research overview

Is this your work?

11 publications

Characterization of quasirandom permutations by a pattern sum

Density maximizers of layered permutations

Finitely forcible graphons with an almost arbitrary structure

A Dichotomy Theorem for Circular Colouring Reconfiguration

Weak regularity and finitely forcible graph limits

Saturation in the Hypercube and Bootstrap Percolation

A Proof of a Conjecture of Ohba

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices

Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings

On Saturated $k$ -Sperner Systems

Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond

See the researcher in context

Building this map preview

Jonathan A. Noel

Research overview

Is this your work?

11 publications

Characterization of quasirandom permutations by a pattern sum

Density maximizers of layered permutations

Finitely forcible graphons with an almost arbitrary structure

A Dichotomy Theorem for Circular Colouring Reconfiguration

Weak regularity and finitely forcible graph limits

Saturation in the Hypercube and Bootstrap Percolation

A Proof of a Conjecture of Ohba

Beyond Ohba's Conjecture: A bound on the choice number of kkk-chromatic graphs with nnn vertices

Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings

On Saturated kkk-Sperner Systems

Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond

See the researcher in context

Building this map preview

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices

On Saturated $k$ -Sperner Systems