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.[1]

Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal.[2] 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.[3]

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

Research

Reed's thesis research concerned perfect graphs.[2] With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method.[6] 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.[7] 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.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"\"""\"""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}.
 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.
 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.
 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., 241, Cambridge: Cambridge Univ. Press, pp. 87–162, doi:10.1017/CBO9780511662119.006, 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, 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.
 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, 23, Berlin: Springer-Verlag, ISBN 3-540-42139-4, MR 1869439.

References

1. ^ Chairholders: Bruce A. Reed, Canada Research Chairs, retrieved 2012-10-07.
2. ^ a b
3. ^ Past members, Pacific Institute for the Mathematical Sciences, retrieved 2012-10-07.
4. ^ "Three McGill researchers elected RSC Fellows", McGill Reporter, October 1, 2009
5. ^ Bruce Reed announced as 2013 CRM/Fields/PIMS Prize recipient, Pacific Institute for the Mathematical Sciences, retrieved 2012-12-30.
6. ^ Kayll, P. Mark (2003). Graph Colouring and the Probabilistic Method. Mathematical Reviews, MR1869439.
7. ^ ICM Plenary and Invited Speakers since 1897, International Mathematical Union, retrieved 2015-10-01.