MKLab - GRAPHS AND NETWORKS

Graph theory

Fri, 25 Sep 2026 21:17:04 +0300

Graph theory is a branch of discrete mathematics concerned with mathematical structures called graphs, which model relationships between objects. A graph consists of vertices (or nodes) and edges connecting pairs of vertices. In an undirected graph, an edge represents a symmetric relationship, while in a directed graph, each edge has an orientation. Graphs can also be weighted, allowing edges to carry numerical values such as distances or costs, and multigraphs can contain multiple edges between the same pair of vertices or loops.

The origins of graph theory are usually traced to Euler's 1736 solution of the Seven Bridges of Königsberg problem, which demonstrated how a spatial problem could be transformed into an abstract network problem. Since then, the subject has developed into a major mathematical field, with important connections to combinatorics, topology, algebra, geometry, probability, and computer science. Classic problems such as the Four Color Theorem, questions about Eulerian and Hamiltonian paths, and the enumeration of trees helped establish many of the central ideas of the discipline.

A central concern is understanding the structure and properties of graphs. Important concepts include paths, cycles, connectivity, trees, bipartite graphs, planar graphs, graph coloring, and graph matching. For example, the degree of a vertex measures how many edges are incident to it, while the chromatic number $\chi(G)$ is the minimum number of colors needed to color the vertices so that adjacent vertices receive different colors. Graphs can also be represented algebraically through an adjacency matrix $A$, while the graph Laplacian is commonly defined as $L=D-A$, where $D$ is the diagonal degree matrix.

Graph theory has become fundamental far beyond pure mathematics. It provides mathematical models for computer networks, transportation systems, social networks, biological interactions, chemical structures, communication networks, cybersecurity, scheduling, and optimization. Problems such as finding shortest paths, constructing minimum spanning trees, determining network flows, and detecting communities can all be expressed using graphs. Modern graph theory also includes specialized areas such as algebraic/spectral graph theory, topological graph theory, geometric graph theory, extremal graph theory, random graph theory, and graph enumeration, making it an important bridge between theoretical mathematics and real-world computational problems.

Key Takeaways

Graph: $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges.
Degree of a vertex: $\deg(v)$ = number of edges incident to $v$.
Handshake Lemma: $\displaystyle \sum_{v\in V}\deg(v)=2|E|$.
Path: a sequence of vertices connected by edges.
Cycle: a path that returns to its starting vertex.
Connected graph: every pair of vertices has a path between them.
Tree: a connected graph with no cycles; a tree with $n$ vertices has exactly $n-1$ edges.
Complete graph: $K_n$ has $\displaystyle \frac{n(n-1)}{2}$ edges.
Graph coloring: adjacent vertices must receive different colors.
Chromatic number: $\chi(G)$ is the minimum number of colors required.
Adjacency matrix: $A_{ij}=1$ when vertices $i$ and $j$ are adjacent, and $0$ otherwise.
Graph Laplacian: $L=D-A$.
Eulerian problems: concern traversing every edge exactly once.
Hamiltonian problems: concern visiting every vertex exactly once.
Shortest-path problems: minimize the total weight along a path.
Minimum spanning tree: connects all vertices while minimizing total edge weight.
Graph theory provides a powerful mathematical language for networks and relationships.
Its applications range from pure mathematics to AI, algorithms, cybersecurity, biology, physics, and social-network analysis.

ARTICLE / PDF

Network theory

Fri, 25 Sep 2026 21:10:53 +0300

Network theory is a branch of graph theory, mathematics, computer science, and network science that studies systems represented as nodes (vertices) connected by edges (links). The connections can be symmetric or asymmetric, and both nodes and edges can have attributes such as weights, directions, or capacities. A network can therefore be represented mathematically as a graph $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges. The origins of network theory are often traced to Euler's solution of the Seven Bridges of Königsberg problem.

A major part of network theory is network optimization: finding the most efficient way to move through or organize a network. Important problems include shortest paths, maximum flow, transportation, matching, assignment, routing, network location, and critical-path analysis. For example, in a weighted graph, the shortest-path problem seeks a path $P$ minimizing its total weight, $d(u,v)=\min_{P:u\rightarrow v}\sum_{e\in P}w(e)$. These problems connect graph theory with combinatorial optimization, algorithms, operations research, logistics, and computer science.

Network analysis focuses on understanding the structure and importance of different parts of a network. One of the central ideas is centrality: determining which nodes are structurally important. Degree centrality measures the number of connections a node has, while betweenness centrality measures how frequently a node lies on shortest paths between other nodes. Closeness centrality measures how near a node is to the rest of the network, and eigenvector centrality gives greater importance to nodes connected to other important nodes. If $A$ is the adjacency matrix, eigenvector centrality can be expressed through $Ax=\lambda x$. These concepts are used in social networks, the Web, biological systems, transportation, telecommunications, and fraud detection.

Modern network theory extends beyond static graphs. Spatial networks incorporate geographical location, while temporal networks explicitly model connections that change with time. Network theory is also used to study how information, diseases, rumors, financial shocks, and other phenomena spread through interconnected systems. In biological networks, for example, nodes can represent genes, proteins, or species; in social networks they can represent people or organizations; and in computer networks they can represent computers or websites. This makes network theory a powerful mathematical framework for studying complex systems in which relationships between objects are as important as the objects themselves.

Key Takeaways

Basic structure: A network is modeled as a graph $G=(V,E)$ consisting of nodes and edges.
Network optimization: Includes shortest path, maximum flow, matching, assignment, routing, and transportation problems.
Adjacency matrix: A network can be represented by a matrix $A$, where $A_{ij}$ indicates whether nodes $i$ and $j$ are connected.
Degree: For a node $v$, its degree is $k_v=\sum_j A_{vj}$.
Shortest path: $d(u,v)=\min_{P:u\rightarrow v}\sum_{e\in P}w(e)$.
Centrality: Degree, closeness, betweenness, eigenvector, Katz, and other measures quantify structural importance.
Eigenvector centrality: $Ax=\lambda x$; importance depends partly on connections to other important nodes.
Complex networks: Many real-world networks have nontrivial structures such as hubs, communities, and heterogeneous degree distributions.
Dynamic networks: Temporal networks study connections that evolve with time rather than treating the network as static.
Applications: Social networks, Internet infrastructure, transportation, biology, neuroscience, epidemiology, finance, ecology, and information systems.
Mathematical significance: Network theory provides a bridge between graph theory, probability, linear algebra, optimization, statistics, and dynamical systems.

ARTICLE / PDF

What if you only see part of a network?

Fri, 25 Sep 2026 21:08:02 +0300

The article from Tech Xplore, based on research at Leiden University, explores a fundamental problem in network science: how can we understand a network when we can observe only part of it? Networks appear everywhere, from friendship and internet connections to brain networks and international trade. Alessio Catanzaro developed mathematical methods for reconstructing incomplete networks. His key insight is that mathematically removing the unseen part of a network has an effect analogous to renormalization, where smaller components are combined into larger-scale units. This suggests that the visible portion of a network can contain information about its hidden structure.

Catanzaro's work also leads to a surprisingly simple multi-scale network model, informally called the "pizza model." Rather than explicitly assuming that nodes belong to geographical or social communities, tightly connected groups can emerge naturally from the mathematical rules of the model. This is significant because real networks often display community structure even when those communities were not explicitly programmed into the model. Such ideas could potentially be useful for studying social networks, epidemiological transmission, biological systems, and large datasets.

The second part of the article focuses on Francesca Giuffrida's work on a different but related question: when does an observed pattern represent a genuine relationship rather than random chance? A major difficulty is that "chance" itself can be mathematically defined in different ways, and different assumptions can lead to different statistical conclusions. Giuffrida developed statistical methods for choosing appropriate models when researchers compare competing explanations. Her research particularly examines e-values, an alternative framework for evaluating statistical evidence that can offer greater reliability and reproducibility than some traditional approaches.

Giuffrida applied these ideas to brain-imaging data, where the methods helped distinguish connections between brain regions that were supported by the data from connections that could plausibly have appeared by chance. The broader message is that modern network science combines graph theory, statistical inference, probability and mathematical modeling to deal with two fundamental problems: hidden structure and false patterns. Together, the two research programs show how relatively abstract mathematical ideas can provide practical tools for understanding complex systems.

Key takeaways

Incomplete networks can still reveal hidden structure.
Removing unobserved parts of a network can be mathematically related to renormalization.
Catanzaro's multi-scale/"pizza" model generates community-like structures from simple rules.
Network communities do not necessarily need to be imposed beforehand; they can emerge naturally.
A central statistical question is whether an observed pattern is real or simply the result of chance.
Different mathematical definitions of randomness can produce different conclusions.
e-values provide an alternative approach to evaluating statistical evidence.
Statistical model selection is crucial when comparing competing explanations.
The methods were demonstrated using brain-imaging data to identify meaningful connections.
The research connects network theory, probability, statistics, and complex-systems mathematics.
Potential applications include epidemiology, neuroscience, social networks, AI, and data science.
A useful mathematical perspective is to represent a network as a graph $G=(V,E)$, where $V$ is the set of nodes and $E$ the set of connections.
At multiple scales, a network can be viewed through transformations such as $G \rightarrow G'$, where groups of nodes are aggregated into larger units—an idea closely related to renormalization.

ARTICLE

When it comes to networks, nature has an edge

Fri, 25 Sep 2026 20:25:52 +0300

A University of New Mexico-led study investigates a fundamental question in network science and control theory: how does the structure of a network determine whether signals are amplified, transmitted, or suppressed? The researchers developed a mathematical framework for measuring how an external signal propagates through a network and used it to compare natural networks—such as ecological food webs and gene-regulatory systems—with engineered networks such as electrical power grids. The study was published in Nature Communications as “The Frequency Response of Networks as Open Systems.”

The central finding is that natural and engineered networks tend to have different frequency-response characteristics. Many biological networks appear structurally suited to transmit signals efficiently, whereas engineered systems are frequently designed specifically to prevent amplification of disturbances. In a power grid, for example, uncontrolled propagation of a disturbance can produce instability or cascading failures, so suppression of certain signals is desirable. By contrast, biological systems often depend on the efficient transmission of information, energy, or regulatory activity.

An important mathematical idea in the work is the use of frequency-response analysis and Bode plots. If a network is represented by a linear dynamical system, its response to an input can be expressed schematically as $Y(s)=H(s)U(s)$, where $U(s)$ is the input, $Y(s)$ is the output, and $H(s)$ is the network's transfer function. Evaluating the system at $s=i\omega$ gives the frequency response $H(i\omega)$; its magnitude $|H(i\omega)|$ indicates amplification or attenuation at frequency $\omega$. The researchers found that many biological networks possess structures resembling directed acyclic architectures, allowing signals to move preferentially through the network without strong feedback loops.

The work has potential applications beyond biology. In power systems, identifying network structures that suppress amplification could help engineers design more resilient grids and limit disturbance propagation. Conversely, understanding architectures that enhance signal transmission could be useful for biological modelling and other networked systems. The researchers also identify an important direction for future work: real networks are not static, so it will be necessary to study how frequency response changes when connections evolve, adapt, or reconfigure over time.

Key takeaways

Network topology affects signal propagation: the arrangement of connections can determine whether signals are amplified or attenuated.
Natural and engineered networks have different objectives: biological networks often facilitate information or energy transmission, while engineered networks may deliberately suppress disturbances.
Frequency response provides a mathematical language for comparing these behaviours:
- $Y(s)=H(s)U(s)$
- $H(i\omega)$ = frequency response
- $|H(i\omega)|>1$ indicates amplification, while $|H(i\omega)|<1$ indicates attenuation.
Bode plots provide a familiar engineering representation of how network response changes with frequency.
Many biological networks exhibit structures close to directed acyclic graphs, reducing strong feedback and favouring directional signal propagation.
Power grids provide the contrasting case: suppressing signal amplification can improve stability and resilience.
The research connects network theory, dynamical systems, control theory and biology.
A major open problem is understanding networks whose topology changes dynamically over time.
For mathematics education, the study provides an interesting real-world connection between graphs, matrices, differential equations, complex numbers, transfer functions and logarithmic plots.

ARTICLE

A Survey of Venn Diagrams

Fri, 25 Sep 2026 16:26:21 +0300

The “A Survey of Venn Diagrams” by Frank Ruskey and Mark Weston is a broad combinatorial and geometric survey of Venn diagrams, originally published as a Dynamic Survey in 1997 and updated through 2005. The authors treat Venn diagrams not simply as illustrations of set intersections, but as mathematical objects with rich combinatorial, graph-theoretic, geometric, and topological structure. An $n$-Venn diagram consists of $n$ closed curves arranged so that all $2^n$ possible combinations of inside/outside regions occur, with every such region connected. Thus, for three curves there are $2^3=8$ regions, while an $n$-diagram necessarily contains $2^n$ regions. The survey also distinguishes Venn diagrams from Euler diagrams, which may omit some of these combinations.

A major theme is the construction and classification of Venn diagrams. Venn's original construction adds curves successively, with each new curve dividing every existing region into two. Edwards developed another inductive construction that introduces considerable symmetry and leads to attractive graph-theoretic structures. The survey represents a Venn diagram as a planar graph and studies its dual graph, whose vertices correspond to the $2^n$ regions. Adjacent regions differ in exactly one membership bit, so the dual graph is a spanning subgraph of the $n$-dimensional hypercube $Q_n$. For a simple Venn diagram, Euler's formula gives particularly elegant formulas: if $v$ is the number of vertices and $e$ the number of edges, then $v=2^n-2$ and $e=2^{n+1}-4$.

The survey devotes substantial attention to symmetry. A rotationally symmetric $n$-Venn diagram is invariant under rotations by multiples of $2\pi/n$. A striking result is that such a diagram can exist only when $n$ is prime: the $\binom nk$ regions corresponding to the $k$-element subsets must be distributed equally among the $n$ rotational sectors, requiring $n\mid\binom nk$ for every $1\le kevery prime $n$. Their construction connects Venn diagrams with Boolean lattices, chains, and necklaces, and produces diagrams with $\binom{n}{\lfloor n/2\rfloor}$ vertices, which is the minimum possible for monotone Venn diagrams.
Finally, the survey explores enumeration, minimality, extendibility, monotonicity, and open problems. For example, there are six Venn classes and fourteen diagrams for $n=3$, while the complete number of diagrams becomes difficult to determine as $n$ grows. For simple diagrams the number of vertices is fixed at $2^n-2$, but non-simple diagrams can have fewer vertices; a general lower bound is $\left\lceil(2^n-2)/(n-1)\right\rceil$. For monotone Venn diagrams, the minimum number of vertices is exactly $\binom n{n/2}$ (with the appropriate interpretation for odd $n$). The survey also connects extendibility to Hamiltonian cycles in associated graphs. One particularly notable historical open question was whether simple symmetric Venn diagrams exist for more than seven curves; the survey records increasingly complex examples for $n=11$ and beyond.

Key takeaways

An $n$-Venn diagram has exactly $2^n$ regions, representing every possible subset of the $n$ sets.
Venn diagrams can be studied as planar graphs, with their dual graphs embedded in the Boolean hypercube $Q_n$.
For a simple $n$-Venn diagram:
- Regions: $2^n$
- Vertices: $2^n-2$
- Edges: $2^{n+1}-4$
The $k$-regions correspond naturally to the $\binom nk$ subsets of size $k$.
Rotationally symmetric Venn diagrams require $n$ to be prime, because $n$ must divide $\binom nk$ for every $1\le k
Edwards' construction connects Venn diagrams to hypercubes, Boolean lattices and bipartite planar graphs.
The problem is not merely geometric: Venn diagrams have deep connections to graph theory, combinatorics, topology and order theory.
For monotone Venn diagrams, the minimum number of vertices is $\binom n{\lfloor n/2\rfloor}$.
The survey shows how apparently elementary diagrams can lead to difficult enumeration and existence problems.
A useful teaching connection is the correspondence
sets → binary strings → Boolean lattice → hypercube → planar graph, providing a bridge from elementary set theory to advanced combinatorics.

Read the full “A Survey of Venn Diagrams”

Networks Hold the Key to a Decades-Old Problem

Mon, 21 Sep 2026 22:40:43 +0300

The article describes a major advance on a decades-old problem in Fourier analysis known as Chowla’s cosine problem. Fourier analysis studies how complicated functions can be represented as combinations of simple waves, and Chowla asked how low a sum of $N$ cosine waves must become. He conjectured that for any set of $N$ positive integers, a corresponding cosine sum must eventually fall below $-\sqrt{N}$. Despite decades of work, mathematicians had been unable to approach this bound; the best previous result was dramatically weaker.

The breakthrough came unexpectedly from graph theory rather than traditional Fourier analysis. Researchers studied eigenvalues of special networks called Cayley graphs and realized that the graph structure could be translated into information about cosine sums. Their method proved that every such cosine sum falls below $-N^{1/10}$, while a subsequent result improved this to $-N^{1/7}$.

These results still do not prove Chowla’s conjectured $-N^{1/2}$ bound, but they are the first advances to have the same power-law form as the conjecture. The deeper significance is the unexpected connection between graph theory and Fourier analysis, suggesting that techniques developed for networks may reveal new structure in problems about waves and number theory.

ARTICLE

Component

Tue, 08 Sep 2026 02:28:22 +0300

Component

A component, or connected component, of an undirected graph is a maximal connected subgraph: a collection of vertices in which every pair can be joined by a path, and which cannot be enlarged while remaining connected. Thus, the connected components partition the vertex set of a graph into disjoint subsets. A connected graph has exactly one component, while each isolated vertex forms its own component. Equivalently, define two vertices $u$ and $v$ to be related when there is a path from $u$ to $v$; this is an equivalence relation, and its equivalence classes are precisely the vertex sets of the connected components.

The number of components $c$ is an important invariant of a graph. For a graph with $n$ vertices, every spanning forest contains exactly $n-c$ edges. If the graph additionally has $m$ edges, its circuit rank is
m−n+c.m-n+c.
The number of components also appears in algebraic graph theory: it equals the multiplicity of the eigenvalue $0$ of the graph's Laplacian matrix. Components can be found efficiently using breadth-first search (BFS) or depth-first search (DFS) in linear time $O(n+m)$. When edges are progressively added, a disjoint-set (union–find) structure can maintain the components very efficiently. Connected-component algorithms also have practical applications in areas such as image analysis, where groups of adjoining pixels can be identified as separate objects.

Connected components become especially interesting in random graph theory. In the Erdős–Rényi model $G(n,p)$, the structure changes sharply as the edge probability $p$ increases. For $p<(1-\varepsilon)/n$, components are generally small; around the critical threshold $p\approx1/n$, components of order $n^{2/3}$ appear; and for $p>(1+\varepsilon)/n$, a single giant component containing a positive fraction of all vertices emerges. A still higher threshold around $p\sim(\log n)/n$ marks the transition from several components to a graph that is connected with high probability.

Key takeaways

A connected component is a maximal connected part of a graph.
Components partition all vertices into disjoint groups.
They can be computed in $O(n+m)$ time using BFS or DFS.
They connect graph theory with linear algebra, topology, algorithms, image processing, and random graphs.

ARTICLE

Clique problem

Tue, 08 Sep 2026 02:25:33 +0300

Summary

The clique problem is a fundamental problem in graph theory and theoretical computer science. Given an undirected graph $G=(V,E)$, a clique is a subset of vertices in which every pair of vertices is connected by an edge—in other words, the vertices form a complete subgraph. Several related computational problems arise: finding a maximum clique (the clique containing the largest possible number of vertices), finding all maximal cliques (cliques that cannot be enlarged), or deciding whether a graph contains a clique of size at least $k$. The size of a maximum clique is called the clique number, usually denoted $\omega(G)$. A useful duality is that a clique in $G$ corresponds exactly to an independent set in the complement graph $\overline{G}$.

Computationally, the problem is famous for its difficulty. The decision version—determining whether $G$ contains a $k$-clique—is NP-complete, while finding a maximum clique is NP-hard and is also exceptionally difficult to approximate efficiently. A straightforward brute-force method checks the $\binom{n}{k}$ possible sets of $k$ vertices, requiring roughly $O(n^k k^2)$ time when $k$ is variable. By contrast, finding just one maximal clique can be done greedily in linear time. For enumerating all maximal cliques, the classical Bron–Kerbosch algorithm is widely used; optimized versions achieve worst-case time $O(3^{n/3})$, which is essentially optimal because an $n$-vertex graph can itself contain as many as $3^{n/3}$ maximal cliques.

The clique problem has important applications beyond pure graph theory. In a social network, for example, vertices can represent people and edges mutual acquaintances, so a clique represents a group in which everyone knows everyone else. Similar clique-search techniques appear in bioinformatics, protein-interaction analysis, computational chemistry, molecular matching, evolutionary-tree reconstruction, automatic test generation, and even mathematical research. Much of modern research therefore focuses either on faster algorithms for special graph classes or on proving precisely why the general clique problem cannot be solved efficiently under standard complexity assumptions such as $P\ne NP$.

Key takeaways

Area: Graph Theory, Combinatorics, Algorithms, Computational Complexity.
Clique: a complete subgraph; every pair of its vertices is adjacent.
Maximum clique: largest clique; its size is $\omega(G)$.
Complexity: the $k$-clique decision problem is NP-complete, making the clique problem one of the classical examples of computational intractability.

ARTICLE

Arc diagram

Tue, 08 Sep 2026 01:55:35 +0300

Arc Diagram

An arc diagram is a method of drawing a graph in which all vertices are placed along a straight line and the edges are represented by semicircles or other convex curves drawn above or below that line. For directed graphs, a common convention is to use arcs above the line for one direction and below it for the opposite direction. Although the term arc diagram became popular through Martin Wattenberg’s 2002 work on visualizing repeated patterns in strings, similar graph representations date back at least to the 1960s.

Mathematically, arc diagrams are closely related to graph theory, graph drawing, planar graphs, Hamiltonian graphs, book embeddings, and crossing-number problems. Every planar graph can be represented as a crossing-free arc diagram if edges are allowed to consist of more than one semicircle. However, requiring each edge to be represented by a single semicircle imposes much stronger restrictions: such crossing-free drawings correspond to two-page book embeddings, and deciding whether a graph admits one is NP-complete. Minimizing the number of crossings is also NP-hard.

Arc diagrams also have applications well beyond pure graph drawing. They are used in information visualization, in the Farey diagram of rational numbers—where fractions $p/q$ and $r/s$ are connected when $|ps-rq|=1$—and in molecular biology for visualizing RNA, DNA, and protein structures. In RNA diagrams, for example, crossing arcs can represent pseudoknots and other aspects of molecular topology.

Key takeaways

Main mathematical area: Graph Theory / Discrete Mathematics.
Closely related fields: Computational Geometry, Graph Algorithms and Combinatorics.
Vertices lie on a line; edges are represented by arcs.
Arc diagrams are useful for studying planarity, crossings, Hamiltonian cycles and book embeddings.
Some optimization problems involving arc diagrams are NP-hard or NP-complete.
Applications include data visualization, number theory and computational biology.

ARTICLE

A Beginner’s Guide to Graphs

Mon, 07 Sep 2026 20:30:37 +0300

The freeCodeCamp article “A Beginner’s Guide to Graphs — From Google Maps to Chessboards” introduces graphs as data structures made of vertices (nodes) and edges (connections), showing how they model real-world systems such as Google Maps routes, social networks, web links, Git histories, dependencies, and chess moves. It explains major graph types—including directed, undirected, weighted, unweighted, cyclic, acyclic, and directed acyclic graphs (DAGs)—and compares two common ways to store them in programs: adjacency lists, which are memory-efficient for sparse graphs, and adjacency matrices, which provide fast edge lookups but require $O(V^2)$ memory.
The article then introduces the two fundamental traversal algorithms, Breadth-First Search (BFS), which explores nodes level by level and is especially useful for finding shortest paths in unweighted graphs, and Depth-First Search (DFS), which explores one branch deeply before backtracking and is useful for tasks such as cycle detection, topological sorting, and maze solving. Finally, it demonstrates these ideas through the Knight’s Travails chess problem, where each chessboard square becomes a node and legal knight moves become edges, illustrating how graph theory turns seemingly different practical problems into variations of the same underlying structure.

ARTICLE