Boris Bukh
Professor
Address:
6202 Wean Hall
Department of Mathematical Sciences
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
P: 412-268-6400
Education
Ph.D., Princeton University
Postdoctoral Appointments:
- Herchel Smith Research Fellow, University of Cambridge
- Junior Research Fellow, Churchill College
Awards
- Sloan Research Fellowship
- NSF CAREER Award
Research
I enjoy searching for the largest and best combinatorial objects. Oftentimes the search brings problems of algebraic and geometric flavour, which I especially like.
Below are some of the topics and basic problems that I have played with in the past:
- Turán problems: What is the maximum number of edges in an n-vertex graph containing no copy of a fixed graph G?
- Geometric selection theorems: Given a large cloud of points in Rd, how to best approximate it by a constant-sized set of points?
- Combinatorial number theory: How large does a set of numbers need to be to necessarily contain a solution to a given equation?
- Codes: In a given collection of objects (such as bit strings, or vectors) find a large subcollection of very dissimilar objects.
Select Publications
Bukh, B. (2008). Measurable sets with excluded distances. Geom. and Funct. Analysis, 18 (1), 668-697.
Bukh, B. (2008). Sums of dilates. Combin. Probab. Comput., 17, 627-639.
Bukh. B. (2009). Set families with a forbidden subposet. Electronic J. of Combinatronics, 16, R142.
Bukh, B., Matoušek, J. and Nivasch, G. (2008). Stabbing simplices by points and flats. Discrete Comput. Geom., 43, 321-338.
Bukh, B. andTsimerman, J. (2012). Sum-product estimates for rational functions. Proc., of the London Math. Soc., 104 (1), 1-26.
Bukh, B. and Matoušek, J. (2014). Erdős–Szekeres-type statements: Ramsey function and decidability in dimension 1. Duke Math. Journal, 163 (12), 2243-2270.
Bukh, B. and Jiang, Z. (2017). A bound on the number of edges in graphs without an even cycle. Combin. Probab. Comput., 26(1) 1-15.
Bukh, B. and Conlon, D. (2015). Rational exponents in extremal graph theory. J. of European Math. Society, 20 (7), 1747–1757.
Bukh, B., Guruswami, V., Håstad, J. (2017). An improved bound on the fraction of correctable deletions. SODA '16, 63 (1), 93–103.
Bukh, B. (2017). Ranks of matrices with few distinct entries. Israel Journal of Mathematics, 222 (1), 165–200.
Bukh, B. and Nivasch, G. (2017). One-sided epsilon-approximants. A Journey through Discrete Mathematics: A Tribute to Jiří Matoušek, 343–356.
Bukh, B. and Cox, C. (2017). Nearly orthogonal vectors and small antipodal spherical codes. (Abstract).