Albert-László Barabási Created 2026-10-20 Updated 2026-11-05
Albert-László Barabási is a physicist known for work on complex networks. With Réka Albert, he introduced the Barabási-Albert model, in which a growing graph attaches new vertices preferentially to vertices with larger degree.[ref]
The central scientific idea is a mechanism, rather than merely a fitted curve: growth and degree-dependent attachment can create a broad degree distribution. This encouraged testing network formation rules against data and helped connect graph theory with statistical mechanics. The mechanism does not imply that every heavy-tailed real network follows that model.
Alexander Sidorenko 2026-11-05
Alexander Sidorenko works on density inequalities in graph theory and the theory of hypergraphs. His name is associated with the Sidorenko conjecture, which compares copies of a fixed bipartite graph with the random-density benchmark.[ref]
With David Conlon and Joonkyung Lee, he studied hypergraph failures of the analogous inequality. Their result turns such failures into improved extremal constructions, connecting analytic inequalities for densities with concrete forbidden-subgraph problems.[ref]
Brendan McKay 2026-11-05
Brendan McKay is a researcher in computational graph theory and an emeritus professor at the Australian National University. His institutional homepage identifies nauty as software for graph isomorphism and graph automorphisms.[ref]
A graph automorphism is a relabeling that preserves adjacency within a graph. For an original cycle on four vertices, choose the image of one vertex in4 ways and then choose which of its two neighbors receives the next vertex in2 ways. The remaining images are forced, giving
These relabelings form a group. Computing such symmetries can avoid repeating equivalent branches of a structural search.
Graph canonical labeling addresses a complementary problem: assign a representative encoding so that isomorphic graphs receive the same canonical result. This makes it possible to compare structures whose input vertex names differ or to remove duplicate generated graphs. McKay's work on nauty made these tasks practical for many graph classes.
With Adolfo Piperno, he described the mathematical basis of individualization-refinement graph search and the implementations in nauty and Traces graph isomorphism software. Their paper connects the validity of the search framework with performance comparisons, while distinguishing the practical algorithms from a general worst-case efficiency claim.[ref]
Choongbum Lee 2026-11-05
Choongbum Lee works on graph theory and Ramsey theory. His joint paper with David Conlon, Jacob Fox and Benny Sudakov investigates copies of a graph whose vertex order must be preserved.[ref]
The ordered setting is sensitive to labeling: some ordered matchings have superpolynomial Ramsey numbers. Thus low ordinary degree does not by itself make an order-constrained embedding problem easy.[ref]
Claude Berge Created 2026-10-14 Updated 2026-11-05
Claude Berge was a mathematician whose work helped establish modern graph theory, with connections to combinatorics, game theory and optimization. His books gave common mathematical language to networks arising in different applications. He also formulated the strong perfect graph conjecture, a major stimulus to research on perfect graphs.[ref] A perfect graph has equal chromatic number and clique number in every induced subgraph. The condition expresses when the obvious lower bound for graph coloring, supplied by mutually adjacent vertices, is always attainable; requiring it in every induced subgraph is essential.
Figure 1.
Portrait of Claude Berge
. Mihály Hujter (HUJTER Mihály), photograph in New York, 1985; Commons records VRT permission ticket 2025052210006236. Creative Commons Attribution-Share Alike 4.0 International., via Wikimedia Commons. Source.
Darij Grinberg Created 2026-10-13 Updated 2026-11-05
Author of graph theory lecture notes developing multigraphs, directed graphs and traversal results. The cited lecture makes conventions about isolated vertices and trivial trails explicit.[ref]
Discrete geometry 2026-11-05
Discrete geometry studies finite or discrete configurations of geometric objects, such as points, lines, circles, polytopes, and packings. Typical questions count incidences, optimize separation or coverage, or determine which combinatorial patterns can be realized geometrically.
For example, distinct points in the Euclidean plane determine at most different lines, because every determined line contains a pair of points. Equality holds when no three points are collinear; collinearity merges several pairs into the same line. This simple argument connects a geometric degeneracy to a change in a counting problem.
Other problems ask how many equal disks can touch a given disk without overlapping, or how a polygon can be triangulated. Convex geometry, graph theory, and computational geometry supply complementary tools: coordinates constrain realizability, while a combinatorial description records which objects meet.
Discrete mathematics Created 2026-10-31 Updated 2026-11-05
Discrete mathematics studies structures built from distinct objects and finite or countable choices. Its main connections include combinatorics, graph theory, number theory, mathematical logic and the analysis of algorithms. The distinction concerns the structures under study, rather than a ban on using real numbers or analysis in proofs.
For example, a graph with vertices has possible unordered edges when loops and repeated edges are excluded. Counting possible edge sets gives labeled simple graphs. A small modeling assumption about allowed edges has turned a structural question into an exact counting formula. Such translations underpin scheduling, networks and computer science.
Domino tiling 2026-11-05
A domino tiling covers a region made of unit squares by nonoverlapping rectangles, each occupying two adjacent squares. Equivalently, it is a perfect matching in the graph whose vertices are squares and whose edges join squares sharing a side. This translates a geometric covering problem into graph theory.
A rectangle has tilings satisfying , with . At the left edge, either one vertical domino leaves a rectangle, or two horizontal dominoes leave a rectangle. Hence , and . A checkerboard colouring gives a different tool: every domino covers one square of each colour, so unequal colour counts obstruct a tiling. Equal counts are necessary but need not suffice for arbitrary regions.
Eric Lehman Created 2026-10-13 Updated 2026-11-05
Eric Lehman is a coauthor of Mathematics for Computer Science by Eric Lehman and others. The text develops discrete mathematical tools for computer science, including proof techniques, graph theory, counting and probability. Its analysis of indicator variables provides a reusable route from a complicated random count to a sum of simple event probabilities.[ref]
F. Thomson Leighton Created 2026-10-13 Updated 2026-11-05
F. Thomson Leighton is a coauthor of Mathematics for Computer Science by Eric Lehman and others. The text develops proofs, graph theory, counting and probability as tools for analyzing algorithms and discrete structures. Its presentation ties formal arguments to computing questions, such as using indicator random variables and linearity of expectation to evaluate a complicated random count.[ref]
Graph Created 2026-09-24 Updated 2026-10-18
Figure 1.
Two drawings of the same six-vertex graph and its adjacency matrix
. Details.
A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set tells us what the objects are; records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.[ref]
This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.[ref]
Our running simple graph has
where abbreviates the unordered pair . It consists of two triangles in a graph, and , joined by . The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that and are adjacent, whereas and are not.
Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, is a length-five walk but not a trail, since it uses twice. The length-three graph path is a shortest route: crossing between the two triangles in a graph requires , with at least one edge before it and one after it. Thus in graph distance, regardless of the drawing.[ref]
An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here is an Eulerian trail of length seven, whereas is a Hamiltonian path of length five. The first repeats ; the second omits . Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.[ref]
The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are . In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.[ref][ref]
Graph of a function Created 2026-10-05 Updated 2026-11-05
For a function , its graph of a function is the subset of the Cartesian product . Exactly one ordered pair has first coordinate for each . For example, the quadratic function on the real line has the parabola as its graph.
The graph determines the values and the domain of a function, but alone does not record a larger specified codomain: the same set of ordered pairs can be regarded as lying in or when both contain all its outputs. It also differs from a graph in graph theory, whose edges need not specify exactly one output per input.
Graph theory Created 2026-09-24 Updated 2026-10-13
Graph theory studies vertices and the edges connecting them: which graph paths exist, how efficiently we can travel, and which connections are indispensable. A road map becomes a graph when junctions are vertices and road segments are edges; a communications network uses routers and links instead. The drawing helps us see connections, but its apparent lengths need not be the costs being optimized. Record travel times or transmission costs separately in a weighted graph.
The appeal of graph theory is that one model serves many practical questions. Graph paths describe routes, connected components of a graph identify isolated regions, and minimum spanning trees connect all locations cheaply. The shortest path problem asks a different question: find the cheapest journey between specified locations. Our four-vertex example below makes that distinction concrete and shows how the Dijkstra algorithm discovers a route without trying every graph path.
Jacob Fox 2026-11-05
Jacob Fox works on extremal combinatorics, Ramsey theory and algebraic and probabilistic methods in graph theory. His Stanford research page also identifies applications to computer science.[ref]
With David Conlon, Choongbum Lee and Benny Sudakov, he studied ordered Ramsey numbers. Requiring the vertices of a monochromatic copy to appear in a prescribed order can force superpolynomial growth even when the underlying graph is a matching.[ref]
László Lovász 2026-11-05
László Lovász is a mathematician whose work connects combinatorics, graph theory and efficient algorithms. With Arjen K. Lenstra and Hendrik W. Lenstra, he developed the LLL algorithm, which replaces a basis of a Euclidean lattice by a more geometrically controlled basis of the same lattice. Their 1982 paper uses lattice reduction to factor polynomials over the rational numbers in polynomial time.[ref]
The point of reduction is not to change the lattice: integer basis changes preserve it. Instead, shorter, better organized vectors expose relations hidden by a poor basis. This is a striking bridge from geometric reasoning to exact algebraic computation. Lovász shared the 2021 Abel Prize with Avi Wigderson for contributions linking discrete mathematics and theoretical computer science.[ref]
Figure 1.
László Lovász; photograph by Peter Badge, Abel Prize laureate page
.
Mark Newman Created 2026-10-18 Updated 2026-10-31
Michał Pilipczuk Created 2026-10-13 Updated 2026-11-05
Coauthor with Tuukka Korhonen and Giannos Stamoulis of research on graph minors and disjoint paths. Their work connects structural graph theory with algorithms for detecting specified configurations.[ref]
Øystein Ore Created 2026-10-31 Updated 2026-11-05
Øystein Ore worked in ring theory, Galois theory, lattice theory and graph theory. His work on noncommutative rings investigated when a ring can be embedded in a division ring, extending the idea of forming fractions beyond commutative arithmetic.
His later books also linked mathematical ideas with their history. The movement from algebraic structures to closure relations and graphs illustrates how an organizing mathematical viewpoint can lead into several different subjects.[ref]
Figure 1.
Portrait of Øystein Ore
. Identified external portrait in the University of St Andrews MacTutor collection; photographer not stated on the inspected display. Source.