3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\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=10.1.1.102.681 $\endgroup$ Jul 25, 2011 at 13:37
  • $\begingroup$ But then apparently one needs a graph of a minimum size for a given $\epsilon$. $\endgroup$ Jul 25, 2011 at 13:55
  • $\begingroup$ The link to the paper by Gowers at springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ Dec 6, 2022 at 9:42
  • $\begingroup$ The link to CiteSeerX in a comment above is broken; it is supposed to link to the following paper: Alon, N.; Duke, Richard A.; Lefmann, Hanno; Rödl, Vojtěch; Yuster, R., The algorithmic aspects of the regularity lemma, J. Algorithms 16, No. 1, 80–109 (1994). Zbl 0794.05119. $\endgroup$ Dec 6, 2022 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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