Source author record

E. R. Vaughan

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

4works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2011arXiv

An analogue of Ryser's Theorem for partial Sudoku squares

In 1956 Ryser gave a necessary and sufficient condition for a partial latin rectangle to be completable to a latin square. In 1990 Hilton and Johnson showed that Ryser's condition could be reformulated in terms of Hall's Condition for partial latin squares. Thus Ryser's Theorem can be interpreted as saying that any partial latin rectangle $R$ can be completed if and only if $R$ satisfies Hall's Condition for partial latin squares. We define Hall's Condition for partial Sudoku squares and show that Hall's Condition for partial Sudoku squares gives a criterion for the completion of partial Sudoku rectangles that is both necessary and sufficient. In the particular case where $n=pq$ , $p|r$ , $q|s$ , the result is especially simple, as we show that any $r \times s$ partial $(p,q)$ -Sudoku rectangle can be completed (no further condition being necessary).

preprint2011arXiv

Gerechte Designs with Rectangular Regions

A \emph{gerechte framework} is a partition of an $n \times n$ array into $n$ regions of $n$ cells each. A \emph{realization} of a gerechte framework is a latin square of order $n$ with the property that when its cells are partitioned by the framework, each region contains exactly one copy of each symbol. A \emph{gerechte design} is a gerechte framework together with a realization. We investigate gerechte frameworks where each region is a rectangle. It seems plausible that all such frameworks have realizations, and we present some progress towards answering this question. In particular, we show that for all positive integers $s$ and $t$ , any gerechte framework where each region is either an $s \times t$ rectangle or a $t\times s$ rectangle is realizable.

preprint2011arXiv

Hall's Condition for Partial Latin Squares

Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability. We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.

preprint2010arXiv

An Asymptotic Version of the Multigraph 1-Factorization Conjecture

We give a self-contained proof that for all positive integers $r$ and all $ε> 0$ , there is an integer $N = N(r, ε)$ such that for all $n \ge N$ any regular multigraph of order $2n$ with multiplicity at most $r$ and degree at least $(1+ε)rn$ is 1-factorizable. This generalizes results of Perkovi{ć} and Reed, and Plantholt and Tipnis.

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.

E. R. Vaughan

Research overview

Is this your work?

4 publications

An analogue of Ryser's Theorem for partial Sudoku squares

Gerechte Designs with Rectangular Regions

Hall's Condition for Partial Latin Squares

An Asymptotic Version of the Multigraph 1-Factorization Conjecture

See the researcher in context

Building this map preview