János Komlós (mathematician)

Notable results

• He proved that every L¹-bounded sequence of real functions contains a subsequence such that the arithmetic means of all its subsequences converge pointwise almost everywhere. In probabilistic terminology, the theorem is as follows. Let ξ₁,ξ₂,... be a sequence of random variables such that E,E,... is bounded. Then there exist a subsequence ξ'₁, ξ'₂,... and a random variable β such that for each further subsequence η₁,η₂,... of ξ'₀, ξ'₁,... we have /n → β a.s.
• With Miklós Ajtai and Endre Szemerédi he proved the ct²/log t upper bound for the Ramsey number R. The corresponding lower bound was established by Jeong Han Kim only in 1995, and this result earned him a Fulkerson Prize.
• The same team of authors developed the optimal Ajtai–Komlós–Szemerédi sorting network.
• Komlós and Szemerédi proved that if G is a random graph on n vertices with

• With Gábor Sárközy and Endre Szemerédi he proved the so-called blow-up lemma which claims that the regular pairs in Szemerédi's regularity lemma are similar to complete bipartite graphs when considering the embedding of graphs with bounded degrees.
• Komlós worked on Heilbronn's problem; he, János Pintz and Szemerédi disproved Heilbronn's conjecture.
• Komlós also wrote highly cited papers on sums of random variables, space-efficient representations of sparse sets, random matrices, the Szemerédi regularity lemma, and derandomization.

  Degrees, awards