User:David Eppstein

I'm a computer science professor at UC Irvine, in Orange County, California. See my home page or blog or even my Wikipedia article for more about me.

Much of my Wikipedia editing is on mathematics articles, but I've also edited articles on computer science, academic biography, the arts, and California geography. I've also contributed many diagrams and photographs to Wikipedia and Wikimedia Commons.

Did you know?[edit]

... that James Colliander, Gigliola Staffilani, and Terence Tao are part of a collaborative group of mathematicians called the I-team? (15.01)
... that mathematician Linda Preiss Rothschild settled for graduate study at MIT after Princeton rejected her for being female? (15.01)
... that Ioana Dumitriu began taking graduate mathematics courses as a college freshman, and became the first female Putnam Fellow the following year? (15.01)
... that Fermat's only complete proof shows there is no integer right triangle with square area, pair of integer right triangles sharing two sides, or square gap between three equally spaced squares? (15.01)
... that the Laves graph (pictured), a highly symmetrical three-dimensional structure that forms one of the several crystal structures of carbon, is named after German crystallographer Fritz Laves? (14.12)
... that René Just Haüy modeled octahedral crystals mathematically as polycubes made of a centered octahedral number of cubes (pictured)? (14.09)
... that Northwest Coast artist Jim Hart is a hereditary chief of the Haida Nation? (14.08)
... that 19th-century French geometer Olry Terquem, writing as "Tsarphati", was an outspoken advocate of the Reform movement in Judaism? (14.07)
... that mathematician and author C. Stanley Ogilvy was an avid sailor who frequently competed in the Star World Championships? (14.07)
... that book embeddings of graphs have been used to model fault-tolerant computer systems, the phases of traffic lights, and pseudoknots in RNA molecules? (14.06)
... that a photograph (pictured) taken by Elena Mrozovskaya at the 1903 Ball in the Winter Palace in Saint Petersburg, Russia, was exhibited in the Hermitage Rooms in London 100 years later?(13.11)
... that every knotted polygon in three-dimensional space can be touched at four points by a quadrisecant line (pictured)? (13.07)
... that the subjects of Marjorie Senechal's books include quasicrystals, Albania, and silk? (13.07)
... that according to the Gilbert–Shannon–Reeds model of probability distribution, a deck of playing cards should be riffled seven times in order to thoroughly randomize it? (13.07)
... that M. C. Escher's woodcut Circle Limit III was inspired by an illustration of a hyperbolic tessellation (example pictured) in a paper by H. S. M. Coxeter? (13.07)
... that mathematician Andrew Gleason liked to say that proofs "really aren't there to convince you that something is true—they're there to show you why it is true"? (13.04)
... that Latvian-American mathematician Lipman Bers was also a human rights activist and a founder of the Committee on Human Rights of the National Academy of Sciences? (13.04)
... that circular layouts, in which the nodes of a graph are drawn on a circle, have been used to visualize the cyclic parts of metabolic networks? (13.03)
... that William Allen Whitworth was the first mathematician to publish Bertrand's ballot theorem, one of many misnamed mathematical theorems? (13.03)
... that because of the possibility of dead heats, the number of possible outcomes of a horse race is not a factorial, but an ordered Bell number? (13.03)
... that in the square of a graph, all vertices with a distance of no more than two in the original graph are adjacent? (13.03)
... that Karl Beth is considered one of the founding fathers of the psychology of religion? (12.10)
... that William W. Cooper, a pioneer of management science, dropped out of high school and worked as a professional boxer before becoming an academic? (12.10)
... that Andrew Vázsonyi became past president of The Institute of Management Sciences without ever having been its president? (12.10)
... that Pieter Nieuwland (pictured), an 18th-century child prodigy and polymath who died a year after becoming a professor, has been called the Dutch Isaac Newton? (12.09)
... that a tomahawk may be used to split an angle into three equal parts, despite the impossibility of doing so with compass and straightedge? (12.09)
... that John Hilliard's Cause of Death (1974) suggested four different interpretations of one photographic negative? (12.09)
... that Prince Rupert's cube, named for Prince Rupert of the Rhine, can pass through a square hole drilled into a smaller cube (pictured)? (12.09)
... that Nicolas de Bruijn was inspired to prove De Bruijn's theorem on packing bricks into boxes by his seven-year-old son's inability to pack some bricks into a box without wasted space? (12.09)
... that the shape that encloses two given volumes and has the minimum possible surface area is the double bubble commonly formed by soap bubbles? (12.07)
... that the success of the multi-language wall poems (pictured) in Leiden, South Holland, inspired similar projects in Sofia, Bulgaria, and in Paris, France? (12.06)
... that Albert Brahms kept the first known records of the tide levels on the North Sea coast of Germany? (12.05)
... that artist Tina Mion, of Winslow, Arizona, grew up visiting the museums of her birthplace, Washington, D.C., whose National Portrait Gallery now holds two of her works in its permanent collection? (12.05)
... that the number of ways to place n diagonally symmetric rooks on an n × n chessboard in such a way that no two rooks attack each other is a telephone number? (12.04)
... that swarms of Japanese soldier crabs of the species Mictyris guinotae, named after French biologist Danièle Guinot, can be used in place of the billiard balls in billiard-ball computers? (12.04)
... that the Latvian mathematician Emanuels Grīnbergs lost his job and his doctoral degree for serving in the German Army during World War II, but then regained both by writing a new thesis? (12.04)
... that the Healdsburg Memorial Bridge in Healdsburg, California, was the first steel bridge across the Russian River? (12.01)
... that the Temple of Kwan Tai in Mendocino, California (pictured) was founded by a survivor from a fleet of seven Chinese junks, two of which landed on the California coast in 1854? (12.01)
... that Hendy Woods State Park, an old-growth coast redwood forest in the Anderson Valley of northern California, is scheduled to be closed in 2012 because of state budget cuts? (12.01)
... that the central chameleon cage in M. C. Escher's 1948 woodcut Stars has the shape of a compound of three octahedra (pictured)? (11.12)
... that the Pythagorean tiling, a pattern of squares of two sizes that can be used to prove the Pythagorean theorem, appears in a painting (pictured) by Dutch Golden Age artist Jacob Ochtervelt? (11.10)
... that despite leaving school at age 14, Thomas Kirkman became one of 19th-century England's leading mathematicians and helped found combinatorial design theory? (11.10)
... that the Sint Servaasbrug in Maastricht has been called the oldest bridge in the Netherlands, and was built in the 13th century to replace a Roman bridge that gave its name to the city? (11.10)
... that Michel Demazure, a mathematician from the pseudonymous Nicolas Bourbaki group, led two French science museums, the Palais de la Découverte and the Cité des Sciences et de l'Industrie? (11.08)
... that the De Bruijn–Erdős theorem may be used to extend the four-color theorem from finite planar graphs to planar graphs with infinitely many vertices? (11.07)
... that the Theil–Sen estimator can accurately fit a line to a set of sample points even when up to 29% of the points have been arbitrarily corrupted? (11.07)
... that the Malfatti circles, three tangent circles inside a triangle, are named after Malfatti because of an incorrect conjecture he made, and were studied earlier by Ajima and di Cecco? (11.06)
... that the widest path problem forms the algorithmic basis of the Schulze method used by Wikimedia to decide the winners of multiway elections? (11.05)
... that according to Kawasaki's theorem, an origami crease pattern with one vertex may be folded flat (pictured) if and only if the sum of every other angle between consecutive creases is 180º? (11.04)
... that John R. Isbell was the primary contributor to the mathematical theory of uniform spaces? (11.04)
... that Edgar Gilbert investigated the mathematics of shuffling playing cards? (11.03)
... that, in the Rule 90 cellular automaton, any finite pattern eventually fills the whole array of cells with copies of itself? (11.02)
... that The Princeton Companion to Mathematics is the 2011 winner of the Mathematical Association of America's Euler Book Prize? (11.02)
... that block cellular automata, invented by Norman Margolus, can be used to simulate lattice gases, sand piles, and billiard-ball computers? (11.02)
... that Charles Fletcher, the first European settler in what is now Navarro River Redwoods State Park, built an inn in 1865 that remained open until the 1970s? (11.02)
... that Andreu Mas-Colell, currently the Minister of Economy and Knowledge of Catalonia, Spain, has studied general equilibrium theory by using differential topology? (11.01)
... that Graciela Chichilnisky, who proposed the Kyoto Protocol's market for carbon credit trading, obtained her PhDs in mathematics and economics without ever having been an undergraduate? (11.01)
... that Starr's corollary to the Shapley–Folkman lemma was proved by an undergraduate student of Kenneth Arrow? (10.10)
... that Paul Erdős challenged Jon Folkman to solve mathematical problems immediately after Folkman's surgery for brain cancer? (10.10)
... that every round-robin tournament either has a set of players who win all games against players outside the set, or its graph of wins and losses is pancyclic, having directed cycles of all lengths? (10.09)
... that the Albion River Bridge, the only wooden bridge on California State Route 1, has been proposed for replacement by the California Department of Transportation? (10.08)
... that Coretta Scott King called African-American civil rights activist Randolph Blackwell an "unsung giant" of nonviolent social change? (10.08)
... that the number of coho salmon spawning on the Ten Mile River in Mendocino County, California, has dropped precipitously since the 1960s? (10.08)
... that Konocti Harbor, a now-closed resort and music venue in Lake County, California, was originally founded in 1959 as low-cost vacation housing for members of a plumbers union? (10.08)
... that Mendocino, California, artist Bill Zacha learned to paint left-handed after injuring his right hand in a fall? (10.06)
... that Canadian astrophysicist Victoria Kaspi was one of the first to observe the cosmic recycling of pulsars? (10.02)
... that, according to the pizza theorem, a circular pizza that is sliced off-center into eight equal-angled wedges can still be divided equally between two people? (09.12)
... that the clique problem of programming a computer to find complete subgraphs in an undirected graph was first studied as a way to find groups of people who all know each other in social networks? (09.12)
... that psychiatrist Marie Nyswander, who developed the methadone treatment for heroin addicts, was herself addicted to cigarettes? (09.12)
... that Matthew T. Dickerson is a computational geometer, scholar of J. R. R. Tolkien and the Inklings, novelist, blues musician, fly fisherman, maple sugar farmer, and beekeeper? (09.11)
... that the Herschel graph (pictured) is the smallest possible polyhedral graph that does not have a Hamiltonian cycle? (09.10)
... that Yreka phlox, an endangered flowering plant that grows in serpentine soil, is the official city flower of Yreka, California? (09.09)
... that a casket discovered by Anant Sadashiv Altekar near Vaishali, on display at the Patna Museum, is said to contain the remains of the Buddha? (09.09)
... that Martin Demaine founded the first one-man art glass studio in Canada and home-schooled his son Erik to become MIT‍ 's youngest ever professor despite not having a college degree himself? (09.09)
... that the Frederick W. Panhorst Bridge (pictured), a concrete open-spandrel arch bridge in Russian Gulch State Park near Mendocino, California, replaced an earlier wooden trestle bridge in 1940? (09.08)
... that the Life without Death cellular automaton, a mathematical model of pattern formation, is a variant of Conway's Game of Life in which cells, once brought to life, never die? (09.06)
... that Donald G. Fink, later to become a prominent electrical engineer, was selected as the best orator in his county at a high school competition? (09.06)
... that one can list every positive rational number without repetition by breadth-first traversal of the Calkin–Wilf tree? (09.05)
... that the first textbook in Hungarian, an encyclopedia by János Apáczai Csere, was written and published in The Netherlands? (09.03)
... that the Hadwiger conjecture (diagram pictured) implies that the surface of any three-dimensional convex body can be illuminated by only eight light sources, but the best proven bound is that 16 lights are sufficient? (09.03)
... that an equitable coloring of a graph (pictured), in which the numbers of vertices of each color are as nearly equal as possible, may require far more colors than a graph coloring without this constraint? (09.03)
... that no matter how biased a coin one uses, flipping a coin to determine whether each edge is present or absent in a countably infinite graph will always produce the same graph, the Rado graph? (09.03)
... that Victor Vacquier escaped Russia by sleigh across the frozen Gulf of Finland and went on to pioneer the use of submarine detectors for investigating plate tectonics? (09.02)
... that there are 115,200 solutions to the ménage problem of permuting six couples at a twelve-person table so that men and women alternate and are seated away from their partners? (09.01)
... that mathematician Paul Erdős called the Hadwiger conjecture, a still-open generalization of the four-color problem, "one of the deepest unsolved problems in graph theory"? (08.05)
...that Dutch topologist Johannes De Groot is the academic grandfather, great-grandfather, and great-great-grandfather of his namesake via four different paths of academic supervision? (08.04)
...that Carl Størmer, "the acknowledged authority" on aurorae and the motion of charged particles in the magnetosphere, began his academic career inventing formulae for π? (08.03)
...that Scripps marine chemist Edward D. Goldberg suggested using mussels to measure the amount of pollution in the oceans? (08.03)
...that television pioneer Thomas T. Goldsmith, Jr. became the inventor of the video game when he took out a video game patent in 1948? (08.03)
...that in Floyd's algorithm for cycle detection, the tortoise and hare move at very different speeds, but always finish at the same spot? (07.10)
...that in graph theory, a pseudoforest can contain trees and pseudotrees, but cannot contain any butterflies, diamonds, handcuffs, or bicycles? (07.10)
...that it is not possible to configure two mutually inscribed quadrilaterals in the Euclidean plane, but the Möbius–Kantor graph (pictured) describes a solution in the complex projective plane? (07.09)
...that the six permutations of the vector (1,2,3) form a hexagon in 3d space, the 24 permutations of (1,2,3,4) form a truncated octahedron in four dimensions, and both are examples of permutohedra? (07.08)
...that Canadian sculptor John Hooper (sculpture pictured) previously lived in England, China, India, and South Africa, and was a captain in the British Army? (07.08)
...that the Rule 184 cellular automaton can simultaneously model the behavior of cars moving in traffic, the accumulation of particles on a surface, and particle-antiparticle annihilation reactions? (07.05)

...that a cyclic cellular automaton (pictured) is a system of simple mathematical rules that can generate complex patterns mixing random chaos, blocks of color, and spirals? (07.04)
...that a nonconvex polygon with three convex vertices is called a pseudotriangle? (07.04)

Spiky things[edit]

The Mighty Defender of the Wiki Barnstar. Thanks for all your work in taking care of the Humboldt University "professors"! Nyttend 20:32, 6 August 2007 (UTC)
The Graphic Designer's Barnstar. Dear me, you hadn't gotten any barnstars yet?? Well you certainly deserve this one. Keep up the good work. Cronholm¹⁴⁴ 03:29, 7 August 2007 (UTC)
The Barnstar of Recovery. I hereby award David Eppstein the Barnstar of Recovery for saving articles from deletion by making significant contributions during their deletion reviews. -- Gulmammad (talk) 04:42, 31 March 2008 (UTC)
The Barnstar--eaten-by-a-bear. I hereby award this Barnstar--eaten-by-a-bear award for this gem which made me chuckle. Cheers, Casliber (talk · contribs) 02:36, 26 May 2008 (UTC)
To David Eppstein for an exceptional job on building a gem out of the John Renton article. Well done -- Samir 06:57, 24 December 2008 (UTC)
The Article Rescue Barnstar. For rescuing Donald G. Fink from AfD, what was possibly my worst ever article (not counting the one with the opening sentence #redirect...) and well done on the DYK. SpinningSpark 15:12, 2 June 2009 (UTC)
The E=mc² Barnstar. Thanks for your tireless work improving Wikipedia's coverage of Mathematics. Jwesley₇₈ 23:58, 21 March 2010 (UTC)
The Copyright Cleanup Barnstar. For your work at this now completed CCI, helping to bring to light and to clean up a long-standing copyright problem. Moonriddengirl ^(talk) 21:41, 15 April 2010 (UTC)
The Tireless Contributor Barnstar. You get one for every 10K edits. Congratulations! Ty 02:29, 8 June 2010 (UTC)
The Stellated Dodecahedron Barnstar! Awarded for your contributions to various pages about geometry. Calcyman 20:10, 15 June 2010 (BST)
The Mensch's Barnstar. David Eppstein earned the Mensch's Barnstar by writing & illustrating Jon Folkman, Shapley–Folkman lemma, Folkman's theorem, and Folkman graph. Six-thousand visitors read the articles featured by Wikipedia's "Did you know?". Kiefer.Wolfowitz (talk) 00:58, 30 October 2010 (UTC)
The 25 DYK Creation and Expansion Medal. Congratulations on your 48 high-quality DYKs! Kiefer.Wolfowitz (Discussion) 17:39, 22 April 2011 (UTC)
The Writer's Barnstar. For the large number of detailed, book-quality articles you have contributed. InverseHypercube 02:18, 10 September 2011 (UTC)
The Teamwork Barnstar. For dealing with the User:Marshallsumter issues. Cerejota 04:45, 15 September 2011 (UTC)
The Editor's Barnstar. Great work on Michal Heiman. Drmies (talk) 18:05, 13 October 2011 (UTC)
The Original Barnstar. Great work on Pythagorean tiling! ♦ Dr. Blofeld 12:19, 23 October 2011 (UTC)
The Hungarian Barnstar of Mathematical Merit. For your consistent quality work on Hungarian mathematican biographies. Nice to see quality referenced articles on such topics! Keep it up! ♦ Dr. Blofeld 21:22, 1 December 2011 (UTC)
The Original Barnstar. Thanks for your efforts in starting Benedict Freedman and Nancy Freedman! ♦ Dr. Blofeld 23:03, 5 March 2012 (UTC)
The Tireless Contributor Barnstar. Thanks for your significant efforts in creating the new articles Mike Steel (mathematician), Alfred van der Poorten and Gesellschaft für Informatik, and for improving the encyclopedia! Northamerica1000^(talk) 12:38, 10 March 2012 (UTC)
The Teamwork Barnstar. Thank you for the re-write and reformatting of the article Albert Brahms which was formally proposed for deleltion. TeamWork is Wikipedian. Stephenwanjau (talk) 03:28, 14 May 2012 (UTC)
The Editor's Barnstar. Thank you for the help with Frances Rosamond's page. Kangwang (talk) 08:32, 11 October 2012 (UTC)
The Original Barnstar. On your work on Circle Limit III AgadaUrbanit (talk) 18:47, 5 July 2013 (UTC)
The Anti-Vandalism Barnstar. For alerting the community at Wikipedia:Articles for deletion/Danielle Vanzura. Bearian (talk) 17:24, 29 October 2013 (UTC)
The Food Barnstar. Thanks for creating Liguria Bakery, and for improving Wikipedia's coverage of business-, food- and California-related topics. Northamerica1000^(talk) 09:48, 2 November 2013 (UTC)
The Original Barnstar. Really nice pics Franz Scheerer (Olbers) (talk) 18:24, 24 January 2014 (UTC)
The Original Barnstar. A barnstar for your impressive rewrite, expansion, and clarification of Cycle basis and Cycle space! Both articles are a nice window into the algebraic topology of graphs. Mark viking (talk) 23:56, 20 March 2014 (UTC)
The Working Wikipedian's Barnstar. For a sequence of consistently helpful contributions to AfD debates. Keep up the good work! RomanSpa (talk) 08:06, 10 July 2014 (UTC)

Boxicity[edit]

This is a Wikipedia user page.
This is not an encyclopedia article. If you find this page on any site other than Wikipedia, you are viewing a mirror site. Be aware that the page may be outdated and that the user to whom this page belongs may have no personal affiliation with any site other than Wikipedia itself. The original page is located at http://en.wikipedia.org/wiki/User:David_Eppstein.

	This user is a member of WikiProject Mathematics.

CS	This user is a member of WikiProject Computer science.

	This user is a member of WikiProject Academic Journals.

	This user teaches at a university or other institution of higher education.

	This user has created a global account.

	This user is an administrator on the English Wikipedia. (verify)

they	This user considers singular they standard English usage.

OC	This user lives in Orange County, California.

This user contributes images to Wikimedia Commons.

User:David Eppstein

Contents

Did you know?[edit]

See also[edit]

Spiky things[edit]

Boxicity[edit]

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Interaction

Tools

Print/export

Languages