On these pages I have collected turan numbers and the sets of all non-isomorphic
Turan hypergraphs for different hypergraphs, primarily the complete r-uniform
hypergraphs. I will continue to update the pages as new data become
available
Generating these hypergraphs requires large amounts of computer time and I
am grateful for having been given access to the resources of, among others,
the computing centra :C3SE, HPC2N,
NSCand PDC. At the end of the summer of 2008 these computations had used
over 300 CPU-core years.
Definition
The Turan number ex(H,n) is the maximum number of edges in any
r-uniform hypergraph which does not have the r-uniform hypergraph H as a
subgraph.
A hypergraph G on n vertices is a Turan graph for H if G has ex(H,n)
edges and does not have H as a subgraph.
We say that two hypergraphs F and H are isomorphic if F can be mapped to
H by a permutation of 1...n
Covering designs
A Turan hypergraph for the r-uniform Kt is equivalent to
a (n,n-r,n-t)-covering design. On this
page I have collected the complete sets of optimal covering designs based on
the Turan hypergraphs I have available.
Generation
The hypergraphs were generated using integer programming, mainly using glpk, and isomorphism
reduction was done using Brendan McKay's
Nauty. The generation programs
are complete so unless there has been an undetected computer error these
lists should be complete.
For more details see the references below.
File format
The format for the hypergraph files is as follows.
The vertices of a hypergraph on n vertices are numbered 1...n.
Every hypergraph consists of a sequence of lines, each representing
an edge, followed by a line with "---" marking the
end of the hypergraph.
Each edge is described as a sequence of integers separated by
a space, each integer is the number of a vertex in the edge.
References
These are some of my papers relating to these hypergraphs. For abstracts
and actual papers visit my publications page
Klas Markström Turan graphs for 3-uniform complete graphs of small order
Klas Markström Extremal graphs and bounds for the Turan density of the
4-uniform K5
Klas Markström, John Talbot On the density of 2-colourable 3-graphs in which any four
points span at most two edges