# Constructing Szemerédi partitions on a computer

Are there practical ways to construct the Szemerédi partitions of a given graph (on a computer)? I found this algorithmic version of the lemma (also see the references within), but I was unable to find any implementations, so I am wondering if these algorithms are practical at all.

Please note that I am not a mathematician and I am very new to this topic. I am trying to find out if it this will be useful for me. I was hoping that someone familiar with the field will be able to provide some guidance and help avoid a likely blind alley.

Also, can partitioning the graph like this recursively be used to define/compute a vertex ordering (ordering = labelling by natural numbers), so that the vertices in the same partition will be adjacent in the ordering?

I highly doubt this can be done in a practical way. The algorithm of Frieze and Kannan requires $O\left(\varepsilon^{-45}\right)$ steps, most of which require a nontrivial amount of work (specifically, step 4 requires $O(n)$ time, where $n$ is the number of vertices in your graph.
I think a larger problem is the size of the graphs required to apply the regularity lemma. This paper by Gowers shows a lower bound on M similar to a tower of 2's of height $\log\left(\varepsilon^{-5}\right)$. Since, say, a tower of five 2's is far larger than the number of bits available to a computer for memory, there will be considerable trouble representing a graph with this many vertices in the first place.
• But then apparently one needs a graph of a minimum size for a given $\epsilon$. – Szabolcs Horvát Jul 25 '11 at 13:55