Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, a former Canada Research Chair in Graph Theory at McGill University. [1] [2] His research is primarily in graph theory. [2] He is a distinguished research fellow of the Institute of Mathematics in the Academia Sinica, Taiwan, [3] and an adjunct professor at the University of Victoria in Canada. [4]
Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal. [5] 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. [6]
Reed was elected as a fellow of the Royal Society of Canada in 2009, [7] and is the recipient of the 2013 CRM-Fields-PIMS Prize. [8]
In 2021 he left McGill, and subsequently became a researcher at the Academia Sinica and an adjunct professor at the University of Victoria. [1] [3] [4]
Reed's thesis research concerned perfect graphs. [5] With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method. [9] 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. [10] 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]
| 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, S2CID 3712019 . |
| 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 . |
| 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 . [11] |
In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.
Fan-Rong King Chung Graham, known professionally as Fan Chung, is an American mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular in generalizing the Erdős–Rényi model for graphs with general degree distribution.
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.
Robert C. Myers is a Canadian theoretical physicist who specializes in black holes, string theory and quantum entanglement.
Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.
Thomas C. Hull is an associate professor of applied mathematics at Franklin & Marshall College and is known for his expertise in the mathematics of paper folding.
The CRM-Fields-PIMS Prize is the premier Canadian research prize in the mathematical sciences. It is awarded in recognition of exceptional research achievement in the mathematical sciences and is given annually by three Canadian mathematics institutes: the Centre de Recherches Mathématiques (CRM), the Fields Institute, and the Pacific Institute for the Mathematical Sciences (PIMS).
In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.
Geoffrey Richard GrimmettOLY is an English mathematician known for his work on the mathematics of random systems arising in probability theory and statistical mechanics, especially percolation theory and the contact process. He is the Professor of Mathematical Statistics in the Statistical Laboratory, University of Cambridge, and was the Master of Downing College, Cambridge, from 2013 to 2018.
Stevo Todorčević, is a Yugoslavian mathematician specializing in mathematical logic and set theory. He holds a Canada Research Chair in mathematics at the University of Toronto, and a director of research position at the Centre national de la recherche scientifique in Paris.
Christian Genest is a professor in the Department of Mathematics and Statistics at McGill University, where he holds a Canada Research Chair. He is the author of numerous research papers in multivariate analysis, nonparametric statistics, extreme-value theory, and multiple-criteria decision analysis.
Donald Andrew Dawson is a Canadian mathematician, specializing in probability.
Niky Kamran is a Belgian-Canadian mathematician whose research concerns geometric analysis, differential geometry, and mathematical physics. He is a James McGill Professor in the Department of Mathematics and Statistics at McGill University.
Ping Zhang is a mathematician specializing in graph theory. She is a professor of mathematics at Western Michigan University and the author of multiple textbooks on graph theory and mathematical proof.
The Department of Mathematics and Statistics is an academic department at McGill University. It is located in Burnside Hall at McGill's downtown campus in Montreal.
Wen-Yi Wendy Lou is a biostatistician who works as a professor in the Dalla Lana School of Public Health of the University of Toronto. Her research interests include the theory of runs and patterns in sequence data and applications of statistics to health care.
Amanda G. Chetwynd is a British mathematician and statistician specializing in combinatorics and spatial statistics. She is Professor of Mathematics and Statistics and Provost for Student Experience, Colleges and the Library at Lancaster University, and a Principal Fellow of the Higher Education Academy.
Ann Natalie Trenk is an American mathematician interested in graph theory and the theory of partially ordered sets, and known for her research on proper distinguishing colorings of graphs and on tolerance graphs. She is the Lewis Atterbury Stimson Professor of Mathematics at Wellesley College.
{{citation}}: CS1 maint: untitled periodical (link){{citation}}: CS1 maint: untitled periodical (link){{citation}}: CS1 maint: untitled periodical (link)| International | |
|---|---|
| National | |
| Academics | |
| Other | |
