Source author record

Padraic Bartlett

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Triangulating Almost-Complete Graphs

A triangle decomposition of a graph $G$ is a partition of the edges of $G$ into triangles. Two necessary conditions for $G$ to admit such a decomposition are that $|E(G)|$ is a multiple of three and that the degree of any vertex in $G$ is even; we call such graphs tridivisible. Kirkman's work on Steiner triple systems established that for $G \simeq K_n$ , $G$ admits a triangle decomposition precisely when $G$ is tridivisible. In 1970, Nash-Williams conjectured that tridivisiblity is also sufficient for "almost-complete" graphs, which for this talk's purposes we interpret as any graph $G$ on $n$ vertices with $δ(G) \geq (1 -ε)n, E(G) \geq (1 - ξ)\binom{n}{2}$ for some appropriately small constants $ε, ξ$ . Nash-Williams conjectured that $ε= ξ=1/4$ would suffice; in 1991, Gustavsson demonstrated in his dissertation that $ε= ξ< 10^{-24}$ suffices for all $n \equiv 3, 9 \mod 18$ , and in 2015 Keevash's work on the existence conjecture for combinatorial designs established that some value of $ε$ existed for any $n$ . In this paper, we prove that for any $ε< \frac{1}{432}$ , there is a constant $ξ$ such that any $G$ with $δ(G) \geq (1 - ε)n$ and $|E(G)| \geq (1 - ξ)\binom{n}{2}$ admits such a decomposition, and offer an algorithm that explicitly constructs such a triangulation. Moreover, we note that our algorithm runs in polynomial time on such graphs. (This last observation contrasts with Holyer's result that finding triangle decompositions in general is a NP-complete problem.)

preprint2013arXiv

Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial latin square P, when can we complete P to a latin square L? In this paper, we will investigate the class of \leqε-dense partial latin squares: partial latin squares in which each symbol, row, and column contains \leqεn-many nonblank cells. A conjecture of Nash-Williams on triangulations of graphs led Daykin and Häggkvist to conjecture that all \leq(1/4)-dense partial latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random latin squares, and use this technique to study \leqε-dense partial latin squares that contain \leqdn^2 cells. In particular, we establish that all \leq(1/5300)-dense n by n partial latin squares are completable, as well as all \leq(1/13)-dense n by n partial latin squares that contain \leq(8.8*10^(-5)*n^2)-many filled cells. This improves prior results of Gustavsson, which required ε= d \leq 10^(-7), as well as Chetwynd and Haggkvist, which required ε= d \leq 10^(-5) and n even, \leq 10^7.

preprint2013arXiv

Completions of epsilon-dense partial Latin squares; quasirandom k-colorings of graphs

A classical question in combinatorics is the following:\ given a partial Latin square $P$ , when can we complete $P$ to a Latin square $L$ ? In this paper, we investigate the class of \textbf{ $ε$ -dense partial Latin squares}:\ partial Latin squares in which each symbol, row, and column contains no more than $εn$ -many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and Häggkvist conjectured that all $\frac{1}{4}$ -dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ε$ -dense partial Latin squares that contain no more than $δn^2$ filled cells in total. In particular, we construct completions for all $ε$ -dense partial Latin squares containing no more than $δn^2$ filled cells in total, given that $ε< \frac{1}{12}, δ< \frac{ \left(1-12ε\right)^{2}}{10409}$ . In particular, we show that all $9.8 \cdot 10^{-5}$ -dense partial Latin squares are completable. We further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $\left(\frac{1}{2} + ε\right)$ -dense partial Latin square is NP-complete, for any $ε> 0$ . Additional results on triangulations of graphs are found. In an unrelated vein, Chapter 6 explores the class of quasirandom graphs. In specific, we study quasirandom $k$ -edge colorings, and create an analogue of Chung, Graham and Wilson's well-known results for such colorings.

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.