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, structure, space, models, and change. History On ...

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 (al ...

, 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 conne ...

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

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). It may refer to: Surname * Anton Vašek (1905–1946), Slovak Holocaust perpetrator * Petr Vašek (born 1979), Czech footballer * Radomír Vašek (born 1972), Czech te ...

. 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 Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...

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,637 ...

. Reed was elected as a fellow of the

Royal Society of Canada The Royal Society of Canada (RSC; french: Société royale du Canada, SRC), also known as the Academies of Arts, Humanities and Sciences of Canada (French: ''Académies des arts, des lettres et des sciences du Canada''), is the senior national, bil ...

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

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

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

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

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

, 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) Graph coloring, vertex coloring in which every 2-chromatic subgraph is Glossary of graph theory, acyclic. The acyclic chromatic number of a Graph (discrete mathematics), graph is the fewest col ...

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

. 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 Benny Sudakov (born October 1969) is an Israeli mathematician, who works mainly on Hungarian-style combinatorics. He was born in Tbilissi, Georgia, and completed his undergraduate studies at Tbilisi State University in 1990. After emigrating to ...

, 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