Hostname: page-component-6898cfcb55-w5hgh Total loading time: 0 Render date: 2026-11-11T11:03:01.530Z Has data issue: false hasContentIssue false

A Disproof of the Fon-der-Flaass Conjecture

Published online by Cambridge University Press:  03 March 2004

J. ROBERT JOHNSON
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK (e-mail: J.R.Johnson@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Baranyai's partition theorem states that the edges of the complete $r$-graph on $n$ vertices can be partitioned into $1$-factors provided that $r$ divides $n$. Fon-der-Flaass has conjectured that for $r=3$ such a partitioning exists with the property that any two $1$-factors are ‘far apart’ in some natural sense.

Our aim in this note is to prove that the Fon-der-Flaass conjecture is not always true: it fails for $n=12$. Our methods are based on some new ‘auxiliary’ hypergraphs.

Information

Type
Paper
Copyright
2004 Cambridge University Press