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.

  • $\begingroup$ @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= $\endgroup$ – Szabolcs Horvát Jul 25 '11 at 13:37
  • $\begingroup$ But then apparently one needs a graph of a minimum size for a given $\epsilon$. $\endgroup$ – Szabolcs Horvát Jul 25 '11 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.