Source author record

Endre Szemerédi

Endre Szemerédi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

The approximate Loebl-Komlós-Sós Conjecture

We prove the following version of the Loebl-Komlos-Sos Conjecture: For every alpha>0 there exists a number M such that for every k>M every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: we decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. However, the decomposition given by the Regularity Lemma is not of help when G is sparse. To surmount this shortcoming we use a more general decomposition technique: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and two other objects each exhibiting certain expansion properties.

preprint2012arXiv

A Practical Regularity Partitioning Algorithm and its Applications in Clustering

In this paper we introduce a new clustering technique called Regularity Clustering. This new technique is based on the practical variants of the two constructive versions of the Regularity Lemma, a very useful tool in graph theory. The lemma claims that every graph can be partitioned into pseudo-random graphs. While the Regularity Lemma has become very important in proving theoretical results, it has no direct practical applications so far. An important reason for this lack of practical applications is that the graph under consideration has to be astronomically large. This requirement makes its application restrictive in practice where graphs typically are much smaller. In this paper we propose modifications of the constructive versions of the Regularity Lemma that work for smaller graphs as well. We call this the Practical Regularity partitioning algorithm. The partition obtained by this is used to build the reduced graph which can be viewed as a compressed representation of the original graph. Then we apply a pairwise clustering method such as spectral clustering on this reduced graph to get a clustering of the original graph that we call Regularity Clustering. We present results of using Regularity Clustering on a number of benchmark datasets and compare them with standard clustering techniques, such as $k$-means and spectral clustering. These empirical results are very encouraging. Thus in this paper we report an attempt to harness the power of the Regularity Lemma for real-world applications.

preprint1996arXiv

An Algorithmic Version of the Blow-up Lemma

Recently we have developed a new method in graph theory based on the Regularity Lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, beside the Regularity Lemma, is the so-called Blow-up Lemma. This lemma helps to find bounded degree spanning subgraphs in $\varepsilon$-regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the Blow-up Lemma. The desired subgraph, for an $n$-vertex graph, can be found in time $O(nM(n))$, where $M(n)=O(n^{2.376})$ is the time needed to multiply two $n$ by $n$ matrices with 0,1 entries over the integers. We show that the algorithm can be parallelized and implemented in $NC^5$.