# 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?

-

Most of this information is apparently available through links from Wikipedia, so my apologies if this is not helpful (or useful enough to warrant being an answer).

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.

-
@Calvin Condon, thank you for the pointer. I am not a mathematician, and very new to this topic, but the abstract of this paper gave me the impression that this partitioning should work for any graph, and should be implementable in practice: citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.681 –  Szabolcs Jul 25 '11 at 13:37
But then apparently one needs a graph of a minimum size for a given $\epsilon$. –  Szabolcs Jul 25 '11 at 13:55