**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Dániel József Korándi

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related research domains

Courses taught by this person

Related units (3)

No results

No results

People doing similar research

No results

Related publications (5)

Loading

Loading

Loading

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such covering cycles does not depend on the size of K-n but only on the number of colors. We initiate the study of this phenomenon in the case where K-n is replaced by the random graph G(n,p). Given a fixed integer r and p=p(n)>= n-1/r+epsilon, we show that with high probability the random graph G similar to G(n,p) has the property that for every r-coloring of the edges of G, there is a collection of f '(r)=O(r8logr) monochromatic cycles covering all the vertices of G. Our bound on p is close to optimal in the following sense: if pMUCH LESS-THAN(logn/n)1/r, then with high probability there are colorings of G similar to G(n,p) such that the number of monochromatic cycles needed to cover all vertices of G grows with n.

,

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is the union of r comparability (or more generally, perfect) graphs, then either G or its complement contains a clique of size n(1/(r+1)). This bound is known to be tight for r = 1. The question whether it is optimal for r >= 2 was studied by Dumitrescu and Toth. We prove that it is essentially best possible for r = 2, as well: we introduce a probabilistic construction of two comparability graphs on n vertices, whose union contains no clique or independent set of size n(1/3+o(1)). Using similar ideas, we can also construct a graph G that is the union of r comparability graphs, and neither G nor its complement contain a complete bipartite graph with parts of size cn/(log n)(r). With this, we improve a result of Fox and Pach.

Dániel József Korándi, Gábor Tardos, Istvan Tomon

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(