János Komlós (mathematician)
From Wikipedia, the free encyclopedia
János Komlós (Budapest, 23 May 1942) is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is 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 at San Diego.[2]
Contents |
[edit] Notable results
- He proved that every L1-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 ξ1,ξ2,... be a sequence of random variables such that E[ξ1],E[ξ2],... is bounded. Then there exist a subsequence ξ'1, ξ'2,... and a random variable β such that for each further subsequence η1,η2,... of ξ'0, ξ'1,... we have (η1+...+ηn)/n → β a.s.
- With Ajtai and Szemerédi he proved[3] the ct2/log t upper bound for the Ramsey number R(3,t). The corresponding lower bound was proved by Kim only in 1995, 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
- edges, where c is a fixed real number, then the probability that G has a Hamiltonian circuit converges to
- 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 also wrote highly-cited papers on sums of random variables,[6] space-efficient representations of sparse sets,[7] random matrices,[8] the Szemerédi regularity lemma,[9] and derandomization.[10]
[edit] 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.[11] 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.[12]
[edit] See also
[edit] References
- ^ Rutgers faculty profile for Komlós.
- ^ UCSD Maths Dept history
- ^ M. Ajtai, J. Komlós, E. Szemerédi: A note on Ramsey numbers, J. Combin. Theory Ser. A, 29(1980), 354–360.
- ^ 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; 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.
- ^ J. Komlós, G. Sárközy, Szemerédi: Blow-Up Lemma, Combinatorica, 17(1997), 109–123.
- ^ 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.
- ^ 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. A preliminary version appeared in 23rd Symposium on Foundations of Computer Science, 1982, DOI:10.1109/SFCS.1982.39.
- ^ Füredi, Zoltán; Komlós, János (1981), "The eigenvalues of random symmetric matrices", Combinatorica 1 (3): 233–241, doi:10.1007/BF02579329.
- ^ Komlós, János; Simonovits, Miklós (1996), Szemeredi's Regularity Lemma and its applications in graph theory, Technical Report: 96-10, DIMACS, http://dimacs.rutgers.edu/TechnicalReports/abstracts/1996/96-10.html.
- ^ 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.
- ^ János Komlós at the Mathematics Genealogy Project..
- ^ Rutgers Mathematics Department – Recent Faculty Honors.
