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]

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.^[12] 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.^[13]

See also

• Komlós–Major–Tusnády approximation

References

1. "Komlos, Janos".
2. UCSD Maths Dept history Archived 2008-10-28 at the Wayback Machine
3. M. Ajtai, J. Komlós, E. Szemerédi: A note on Ramsey numbers, J. Combin. Theory Ser. A, 29(1980), 354–360.
4. Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983), "An O(n log n) sorting network", Proc. 15th ACM Symposium on Theory of Computing, pp. 1–9, doi:10.1145/800061.808726, ISBN 0-89791-099-0, S2CID 15311122; Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983), "Sorting in c log n parallel steps", Combinatorica, 3 (1): 1–19, doi:10.1007/BF02579338, S2CID 519246.
5. J. Komlós, G. Sárközy, Szemerédi: Blow-Up Lemma, Combinatorica, 17(1997), 109–123.
6. Komlós, J.; Pintz, J.; Szemerédi, E. (1982), "A lower bound for Heilbronn's problem", Journal of the London Mathematical Society, 25 (1): 13–24, doi:10.1112/jlms/s2-25.1.13
7. Komlós, J.; Major, P.; Tusnády, G. (1975), "An approximation of partial sums of independent RV'-s, and the sample DF. I", Probability Theory and Related Fields, 32 (1–2): 111–131, doi:10.1007/BF00533093, S2CID 8272486.
8. Fredman, Michael L.; Komlós, János; Szemerédi, Endre (1984), "Storing a Sparse Table with O(1) Worst Case Access Time", Journal of the ACM, 31 (3): 538, doi:10.1145/828.1884, S2CID 5399743. A preliminary version appeared in 23rd Symposium on Foundations of Computer Science, 1982, doi:10.1109/SFCS.1982.39.
9. Füredi, Zoltán; Komlós, János (1981), "The eigenvalues of random symmetric matrices", Combinatorica, 1 (3): 233–241, doi:10.1007/BF02579329, S2CID 7847476.
10. Komlós, János; Simonovits, Miklós (1996), Szemeredi's Regularity Lemma and its applications in graph theory, Technical Report: 96-10, DIMACS.
11. Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1987), "Deterministic simulation in LOGSPACE", Proc. 19th ACM Symposium on Theory of Computing, pp. 132–140, doi:10.1145/28395.28410, ISBN 0-89791-221-7, S2CID 15323404.
12. János Komlós at the Mathematics Genealogy Project.
13. Rutgers Mathematics Department – Recent Faculty Honors Archived 2008-12-18 at the Wayback Machine.