In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
A graphon is a symmetric measurable function . Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:
Each vertex of the graph is assigned an independent random value
Edge is independently included in the graph with probability .
A random graph model is an exchangeable random graph model if and only if it can be defined in terms of a (possibly random) graphon in this way.
The model based on a fixed graphon is sometimes denoted ,
by analogy with the Erdős–Rényi model of random graphs.
A graph generated from a graphon in this way is called a -random graph.
It follows from this definition and the law of large numbers that, if , exchangeable random graph models are dense almost surely.
The simplest example of a graphon is for some constant . In this case the associated exchangeable random graph model is the Erdős–Rényi model that includes each edge independently with probability .
If we instead start with a graphon that is piecewise constant by:
dividing the unit square into blocks, and
setting equal to on the block,
the resulting exchangeable random graph model is the
community stochastic block model, a generalization of the Erdős–Rényi model.
We can interpret this as a random graph model consisting of distinct Erdős–Rényi graphs with parameters respectively, with bigraphs between them where each possible edge between blocks and is included independently with probability .
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas.
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc