Neil Robertson (mathematician)

Last updated
Neil Robertson
BornNovember 30, 1938 (1938-11-30) (age 80)
Canada
ResidenceUnited States, Canada
NationalityAmerican
Alma mater University of Waterloo, 1969
Known for Robertson–Seymour theorem
Awards Pólya Prize (SIAM) (2004, 2006)
Scientific career
Fields Mathematician
Institutions The Ohio State University
Doctoral advisor William Tutte
Doctoral students

George Neil Robertson (born November 30, 1938) is a mathematician working mainly in topological graph theory, currently a distinguished professor [1] emeritus [2] at the Ohio State University. He earned his B.Sc. from Brandon College in 1959, and his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. [3] [4]

In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs.

Ohio State University public research university in Columbus, Ohio, United States

The Ohio State University (OSU), commonly referred to as Ohio State, is a large public research university in Columbus, Ohio. Founded in 1870 as a land-grant university and the ninth university in Ohio with the Morrill Act of 1862, the university was originally known as the Ohio Agricultural and Mechanical College. The college originally focused on various agricultural and mechanical disciplines but it developed into a comprehensive university under the direction of then-Governor Rutherford B. Hayes, and in 1878 the Ohio General Assembly passed a law changing the name to "The Ohio State University". The main campus in Columbus, Ohio, has since grown into the third-largest university campus in the United States. The university also operates regional campuses in Lima, Mansfield, Marion, Newark, and Wooster.

University of Waterloo public research university in Waterloo, Ontario, Canada

The University of Waterloo is a public research university with a main campus in Waterloo, Ontario, Canada. The main campus is on 404 hectares of land adjacent to "Uptown" Waterloo and Waterloo Park. The university offers academic programs administered by six faculties and ten faculty-based schools. The university also operates three satellite campuses and four affiliated university colleges. Waterloo is a member of the U15, a group of research-intensive universities in Canada. The University of Waterloo is most famous for its co-operative education (co-op) programs, which allow the students to integrate their education with applicable work experiences. The university operates the largest post-secondary co-operative education program in the world, with over 20,000 undergraduate students in over 140 co-operative education programs.

Contents

Biography

In 1969, Robertson joined the faculty of The Ohio State University, where he was promoted to Associate Professor in 1972 and Professor in 1984. He was a consultant with Bell Communications Research from 1984 to 1996. He has held visiting faculty positions in many institutions, most extensively at Princeton University from 1996 to 2001, and at Victoria University of Wellington, New Zealand, in 2002. He also holds an adjunct position at King Abdulaziz University in Saudi Arabia. [2]

King Abdulaziz University university in Jeddah, Saudi Arabia

King Abdulaziz University (KAU) is a public university in Jeddah, Saudi Arabia. It was established in 1967 as a private university, by a group of businessmen led by Muhammad Abu Bakr Bakhashab and including writer Hamza Bogary. In 1974, King Abdulaziz University was converted to a public university by a decision of the Council Ministers of Saudi Arabia under then-King Faisal's orders. In 2016, it was ranked the #1 Arab university by Times Higher Education.

Saudi Arabia Country in Western Asia

Saudi Arabia, officially the Kingdom of Saudi Arabia, is a sovereign state in Western Asia constituting the bulk of the Arabian Peninsula. With a land area of approximately 2,150,000 km2 (830,000 sq mi), Saudi Arabia is geographically the largest sovereign state in the Middle East, the second-largest in the Arab world, the fifth-largest in Asia, and the 12th-largest in the world. Saudi Arabia is bordered by Jordan and Iraq to the north, Kuwait to the northeast, Qatar, Bahrain, and the United Arab Emirates to the east, Oman to the southeast and Yemen to the south; it is separated from Israel and Egypt by the Gulf of Aqaba. It is the only nation with both a Red Sea coast and a Persian Gulf coast, and most of its terrain consists of arid desert, lowland and mountains. As of October 2018, the Saudi economy was the largest in the Middle East and the 18th largest in the world. Saudi Arabia also has one of the world's youngest populations; 50 percent of its 33.4 million people are under 25 years old.

Research

Robertson is known for his work in graph theory, and particularly for a long series of papers co-authored with Paul Seymour and published over a span of many years, in which they proved the Robertson–Seymour theorem (formerly Wagner's Conjecture). This states that families of graphs closed under the graph minor operation may be characterized by a finite set of forbidden minors. As part of this work, Robertson and Seymour also proved the graph structure theorem describing the graphs in these families.

Graph theory Area of discrete mathematics

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 which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Paul Seymour (mathematician) American mathematician

Paul Seymour is currently a professor at Princeton University; half in the department of mathematics and half in the program in applied and computational math. His research interest is in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, and claw-free graphs. Many of his recent papers are available from his website.

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.

Additional major results in Robertson's research include the following:

Robertson graph

In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.

Regular graph graph where each vertex has the same number of neighbors

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph of odd degree will contain an even number of vertices.

In graph theory, the girth of a 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.

Awards and honors

Robertson has won the Fulkerson Prize three times, in 1994 for his work on the Hadwiger conjecture, in 2006 for the Robertson–Seymour theorem, and in 2009 for his proof of the strong perfect graph theorem. [5]

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

He also won the Pólya Prize (SIAM) in 2004, the OSU Distinguished Scholar Award in 1997, and the Waterloo Alumni Achievement Medal in 2002. In 2012 he became a fellow of the American Mathematical Society. [6]

American Mathematical Society association of professional mathematicians

The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, advocacy and other programs.

Related Research Articles

Four color theorem Statement in mathematics

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. Since then the proof has gained wide acceptance, although some doubters remain.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Hugo Hadwiger Swiss cryptographer

Hugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.

Perfect graph type of graph (mathematical structure)

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

Snark (graph theory) connected, bridgeless cubic graph with chromatic index equal to 4

In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

Hadwiger conjecture (graph theory) conjecture that all graphs requiring k or more colors contain a k-vertex complete minor

In graph theory, the Hadwiger conjecture states that if G is loopless and has no minor then its chromatic number . It is known to be true for t = 1 to 6. It is also a generalization of the four-color theorem and is considered one of the most challenging open problems in the field.

Hadwiger number

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number k for which the complete graph Kk is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

Klaus Wagner German mathematician

Klaus Wagner was a German mathematician known for his contributions to graph theory.

Maria Chudnovsky Mathematician and engineer

Maria Chudnovsky is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow.

Combinatorica is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorary editor-in-chief. The current editors-in-chief are László Babai, László Lovász, and Alexander Schrijver. The advisory board consists of Ronald Graham, András Hajnal, Gyula O. H. Katona, Miklós Simonovits, and Vera Sós. It is published by the János Bolyai Mathematical Society and Springer Verlag.

Daniel P. Sanders is an American mathematician. He is known for his 1996 efficient proof (algorithm) of proving the Four color theorem. He used to be a guest professor of the department of computer science at Columbia University.

Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

Paul Allen Catlin was a mathematician, professor of mathematics and Doctor of Mathematics, known for his valuable contributions to graph theory and number theory. He wrote one of the most cited papers in the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.

References

  1. Neil Robertson awarded the title of Distinguished Professor, David Goss, Ohio State, 2006-09-26.
  2. 1 2 Bhattacharjee, Yudhijit (9 December 2011), "Saudi Universities offer cash in exchange for academic prestige", Science , 334 (6061): 1344–1345, doi:10.1126/science.334.6061.1344, PMID   22158799 .
  3. The Sickle, Brandon College Year Book 1959 p.30
  4. G. Neil (George) Robertson at the Mathematics Genealogy Project
  5. Delbert Rey Fulkerson Prize, American Mathematical Society, accessed 2012-01-03.
  6. List of Fellows of the American Mathematical Society, retrieved 2013-07-07.