János Komlós (mathematician)

The native form of this personal name is Komlós János. This article uses Western name order when mentioning individuals.

János Komlós (born 23 May 1942, in Budapest) is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He has been a professor of mathematics at Rutgers University^[1] since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy of Sciences. Between 1984–1988 he worked at the University of California, San Diego.^[2]

Notable results

• Komlós' theorem: 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)/n → β a.s.
• With Miklós Ajtai and Endre Szemerédi he proved^[3] the ct²/log t upper bound for the Ramsey number R(3,t). 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.^[4]
• Komlós and Szemerédi proved that if G is a random graph on n vertices with

${\displaystyle {\frac {1}{2}}n\log n+{\frac {1}{2}}n\log \log n+cn}$

edges, where c is a fixed real number, then the probability that G has a Hamiltonian circuit converges to

${\displaystyle e^{-e^{-2c}}.}$

• 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.^[5]
• Komlós worked on Heilbronn's problem; he, János Pintz and Szemerédi disproved Heilbronn's conjecture.^[6]
• Komlós also wrote highly cited papers on sums of random variables,^[7] space-efficient representations of sparse sets,^[8] random matrices,^[9] the Szemerédi regularity lemma,^[10] and derandomization.^[11]
• Together with Miklós Ajtai and Gábor Tusnády he proved in 1984 the AKT optimal matching theorem.^[12]

Degrees, awards

Komlós received his Ph.D. in 1967 from Eötvös Loránd University under the supervision of Alfréd Rényi.^[13] In 1975, he received the Alfréd Rényi Prize, a prize established for researchers of the Alfréd Rényi Institute of Mathematics. In 1998, he was elected as an external member to the Hungarian Academy of Sciences.^[14]

See also

• Komlós–Major–Tusnády approximation