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.
Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?
A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.
Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and additive combinatorics, and frequently employs the probabilistic method.
Mantel's Theorem (1907) and Turán's Theorem (1941) were some of the first milestones in the study of extremal graph theory.
In particular, Turán's theorem would later on become a motivation for the finding of results such as the Erdős–Stone theorem (1946). This result is surprising because it connects the chromatic number with the maximal number of edges in an -free graph. An alternative proof of Erdős–Stone was given in 1975, and utilised the Szemerédi regularity lemma, an essential technique in the resolution of extremal graph theory problems.
Graph coloring
A proper (vertex) coloring of a graph is a coloring of the vertices of such that no two adjacent vertices have the same color. The minimum number of colors needed to properly color is called the chromatic number of , denoted . Determining the chromatic number of specific graphs is a fundamental question in extremal graph theory, because many problems in the area and related areas can be formulated in terms of graph coloring.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
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
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees,
En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables Les graphons sont liés aux graphes denses : d'une part, les modèles de graphes aléatoires définis par les graphons donnent lieu à des graphes denses presque sûrement.
Pál Turán, né le à Budapest et décédé le , est un mathématicien hongrois connu comme l'auteur du théorème de Turán. Son nombre d'Erdős est 1. Il était l'époux de Vera Sós Turán, mathématicienne elle aussi. Théorème d'Erdős-Kac Histoire de la fonction zêta de Riemann Université Loránd Eötvös Prix Kossuth Théorème de Szemerédi Conjecture d'Erdős-Turán sur les bases additives Inégalité d'Erdős-Turán Graphe de Turán Catégorie:Naissance à Budapest Catégorie:Naissance en août 1910 Catégorie:Naissance dans le roya
Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.
Explore les applications de théorie des valeurs extrêmes, les stratégies d'estimation et les techniques de modélisation pour l'analyse statistique des extrêmes dans les séries chronologiques.
Explore le lemme de régularité Szemerédi, la régularité électronique dans les graphes bipartites, la structure des supergraphes et les techniques d'induction.
Explore les concepts fondamentaux de la théorie des graphes, les résultats d'Erds, le lemme chromatique et le théorème de Union Bound en théorie des graphes.
Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...
ELSEVIER SCIENCE INC2023
We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...
The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succe ...