Bruce Alan Reed FRSC is a

Canadian Canadians (french: Canadiens) are people identified with the country of Canada. This connection may be residential, legal, historical or cultural. For most Canadians, many (or all) of these connections exist and are collectively the source of ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

, a former

Canada Research Chair Canada Research Chair (CRC) is a title given to certain Canadian university research professors by the Canada Research Chairs Program. Program goals The Canada Research Chair program was established in 2000 as a part of the Government of Canada ...

in Graph Theory at

McGill University McGill University (french: link=no, Université McGill) is an English-language public research university located in Montreal, Quebec, Canada. Founded in 1821 by royal charter granted by King George IV,Frost, Stanley Brice. ''McGill Universit ...

. His research is primarily in

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

.Chairholders: Bruce A. Reed
Canada Research Chairs, retrieved 2012-10-07. He is a distinguished research fellow of the Institute of Mathematics in the

Academia Sinica Academia Sinica (AS, la, 1=Academia Sinica, 3=Chinese Academy; ), headquartered in Nangang, Taipei, is the national academy of Taiwan. Founded in Nanking, the academy supports research activities in a wide variety of disciplines, ranging from ...

, Taiwan, and an adjunct professor at the

University of Victoria The University of Victoria (UVic or Victoria) is a public research university located in the municipalities of Oak Bay and Saanich, British Columbia, Canada. The university traces its roots to Victoria College, the first post-secondary insti ...

in Canada.

Academic career

Reed earned his Ph.D. in 1986 from McGill, under the supervision of

Vašek Chvátal Vašek is both a Czech surname and masculine given name (diminutive of Václav Václav () is a Czech male first name of Slavic origin, sometimes translated into English as Wenceslaus or Wenceslas. These forms are derived from the old Slavic/Czech ...

. Before returning to McGill as a Canada Research Chair, Reed held positions at the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario, Canada. The main campus is on of land adjacent to "Uptown" Waterloo and Waterloo Park. The university also operates ...

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...

, and the

French National Centre for Scientific Research The French National Centre for Scientific Research (french: link=no, Centre national de la recherche scientifique, CNRS) is the French state research organisation and is the largest fundamental science agency in Europe. In 2016, it employed 31,63 ...

. 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 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 instit ...

. In 2021 he left McGill, and subsequently became a researcher at the Academia Sinica and an adjunct professor at the University of Victoria.

Research

Reed's thesis research concerned

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

s. With Michael Molloy, he is the author of a book on

graph coloring 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 ...

and the

probabilistic method The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...

. Reed has also published highly cited papers on the

giant component In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices. Giant component in Erdős–Rényi model Giant components are a prominent feature of the Erdő ...

random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...

s with a given

degree sequence In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted ...

, random

satisfiability problem In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...

acyclic coloring In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number of a graph is the fewest colors needed in any acyclic coloring of . Acyclic coloring is often asso ...

tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees ...

, and constructive versions of the

Lovász local lemma In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows on ...

. He was an

invited speaker at the International Congress of Mathematicians This is a list of International Congresses of Mathematicians Plenary and Invited Speakers. Being invited to talk at an International Congress of Mathematicians has been called "the equivalent, in this community, of an induction to a hall of fame." ...

in 2002.. His talk there concerned a proof by Reed and Benny Sudakov, using the

, of a conjecture by Kyoji Ohba that graphs whose number of vertices and

chromatic number 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 o ...

are (asymptotically) within a factor of two of each other have equal chromatic number and list chromatic number.

Selected publications

Articles

Books

References

External links

Home page
* * {{DEFAULTSORT:Reed, Bruce Year of birth missing (living people) Living people Canadian computer scientists Canadian mathematicians Graph theorists McGill University Faculty of Science alumni Academic staff of the University of Waterloo Carnegie Mellon University faculty Academic staff of McGill University