WikiMili The Free Encyclopedia

Neil Robertson | |
---|---|

Born | November 30, 1938 80) Canada | (age

Residence | United States, Canada |

Nationality | American |

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.

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

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.

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** (**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**, 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 km^{2} (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.

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.

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** 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 *K*_{5} or the complete bipartite graph *K*_{3,3} as minors.

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

- In 1964, Robertson discovered the Robertson graph, the smallest possible 4-regular graph with girth five.
- In 1994, with Seymour and Robin Thomas, Robertson extended the number of colors for which the Hadwiger conjecture relating graph coloring to graph minors is known to be true. As of 2012 this remains the strongest known result on this conjecture.
- In 1996, Robertson, Seymour, Thomas, and Daniel P. Sanders published a new proof of the four color theorem, confirming the Appel–Haken proof which until then had been disputed. Their proof also leads to an efficient algorithm for finding 4-colorings of planar graphs.
- In 2006, Robertson, Seymour, Thomas, and Maria Chudnovsky, proved the long-conjectured strong perfect graph theorem characterizing the perfect graphs by forbidden induced subgraphs.

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.

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

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.

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] }

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.

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** was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.

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.

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.

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.

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 *K _{k}* is a minor of

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

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

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 *K*_{5} or *K*_{3,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*.

- ↑ Neil Robertson awarded the title of Distinguished Professor, David Goss, Ohio State, 2006-09-26.
- 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 . - ↑ The Sickle, Brandon College Year Book 1959 p.30
- ↑ G. Neil (George) Robertson at the Mathematics Genealogy Project
- ↑ Delbert Rey Fulkerson Prize, American Mathematical Society, accessed 2012-01-03.
- ↑ List of Fellows of the American Mathematical Society, retrieved 2013-07-07.

- Neil Robertson's homepage at Ohio State University
- Short conference video. Neil Robertson -
*Some thoughts on Hadwiger's Conjecture*. June 28, 1999. Video produced by Bojan Mohar.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.