Bruce Reed (mathematician)

Bruce Reed at the Bellairs Research Institute, 2015

Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, the Canada Research Chair in Graph Theory and a professor of computer science at McGill University. His research is primarily in graph theory.

Academic career

Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal. Before returning to McGill as a Canada Research Chair, Reed held positions at the University of Waterloo, Carnegie Mellon University, and the French National Centre for Scientific Research.

Reed was elected as a fellow of the Royal Society of Canada in 2009, and is the recipient of the 2013 CRM-Fields-PIMS Prize.

Research

Reed's thesis research concerned perfect graphs. With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method. Reed has also published highly cited papers on the giant component in random graphs with a given degree sequence,^{[MR95][MR98a]} random satisfiability problems,^[CR92] acyclic coloring,^[AMR91] tree decomposition,^[R92][R97] and constructive versions of the Lovász local lemma.^[MR98b]

He was an invited speaker at the International Congress of Mathematicians in 2002. His talk there concerned a proof by Reed and Benny Sudakov, using the probabilistic method, of a conjecture by Kyoji Ohba that graphs whose number of vertices and chromatic number are (asymptotically) within a factor of two of each other have equal chromatic number and list chromatic number.^[RS02]

Selected publications

Articles

AMR91.

Alon, Noga; McDiarmid, Colin; Reed, Bruce (1991), "Acyclic coloring of graphs", Random Structures & Algorithms, 2 (3): 277–288, doi:10.1002/rsa.3240020303, MR 1109695.

CR92.

Chvátal, V.; Reed, B. (1992), "Mick gets some (the odds are on his side)", Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 620–627, doi:10.1109/SFCS.1992.267789, ISBN 978-0-8186-2900-6, S2CID 5575389.

R92.

Reed, Bruce A. (1992), "Finding approximate separators and computing tree width quickly", Proc. 24th Annual ACM Symposium on Theory of computing, pp. 221–228, doi:10.1145/129712.129734, ISBN 978-0897915113, S2CID 16259988.

MR95.

Molloy, Michael; Reed, Bruce (1995), "A critical point for random graphs with a given degree sequence", Random Structures & Algorithms, 6 (2–3): 161–179, doi:10.1002/rsa.3240060204, MR 1370952.

R97.

Reed, B. A. (1997), "Tree width and tangles: a new connectivity measure and some applications", Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge: Cambridge Univ. Press, pp. 87–162, doi:10.1017/CBO9780511662119.006, ISBN 9780511662119, MR 1477746.

MR98a.

Molloy, Michael; Reed, Bruce (1998), "The size of the giant component of a random graph with a given degree sequence", Combinatorics, Probability and Computing, 7 (3): 295–305, doi:10.1017/S0963548398003526, hdl:1807/9487, MR 1664335.

MR98b.

Molloy, Michael; Reed, Bruce (1998), "Further algorithmic aspects of the local lemma", Proc. 30th Annual ACM Symposium on Theory of computing, pp. 524–529, doi:10.1145/276698.276866, hdl:1807/9484, ISBN 978-0897919623, S2CID 9446727.

RS02.

Reed, Bruce; Sudakov, Benny (2002), "List colouring of graphs with at most (2 − o(1))χ vertices", Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Higher Ed. Press, Beijing, pp. 587–603, arXiv:math/0304467, Bibcode:2003math......4467R, MR 1957563.

Books

MR02.

Molloy, Michael; Reed, Bruce (2002), Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23, Berlin: Springer-Verlag, ISBN 978-3-540-42139-9.

External links

• Home page
• Bruce A. Reed at DBLP Bibliography Server
• Bruce Reed publications indexed by Google Scholar