Extremal graph theory

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 combinatoric

About this result

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.

Related publications (9)

Related publications

Related people (1)

Related people

Related units

Related concepts (6)

Related concepts

Related courses (1)

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 science and in practice.

Related courses

Related lectures (5)

Related lectures

An extremal problem on crossing vectors

Michal Lason, Bartosz Maria Walczak

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Z(w)? We state a conjecture that the answer is k(w-1). We prove the conjecture for w = 4. Also, for all k and so, we construct several quite different examples of families of desired size k(w-1). This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set. (C) 2019 Elsevier Inc. All rights reserved.

Academic Press Inc Elsevier Science2014

Bridging asymptotic independence and dependence in spatial extremes using Gaussian scale mixtures

Raphaël Huser, Emeric Rolland Georges Thibaud

Gaussian scale mixtures are constructed as Gaussian processes with a random variance. They have non-Gaussian marginals and can exhibit asymptotic dependence unlike Gaussian processes, which are asymptotically independent except in the case of perfect dependence. In this paper, we study the extremal dependence properties of Gaussian scale mixtures and we unify and extend general results on their joint tail decay rates in both asymptotic dependence and independence cases. Motivated by the analysis of spatial extremes, we propose flexible yet parsimonious parametric copula models that smoothly interpolate from asymptotic dependence to independence and include the Gaussian dependence as a special case. We show how these new models can be fitted to high threshold exceedances using a censored likelihood approach, and we demonstrate that they provide valuable information about tail characteristics. In particular, by borrowing strength across locations, our parametric model-based approach can also be used to provide evidence for or against either asymptotic dependence class, hence complementing information given at an exploratory stage by the widely used nonparametric or parametric estimates of the x and (x) over bar coefficients. We demonstrate the capacity of our methodology by adequately capturing the extremal properties of wind speed data collected in the Pacific Northwest, US. (C) 2017 Elsevier B.V. All rights reserved.

Elsevier Sci Ltd2017

Decomposition of Multiple Packings with Subquadratic Union Complexity

János Pach, Bartosz Maria Walczak

Suppose k is a positive integer and X is a k-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most k sets. Suppose there is a function f(n) = o(n(2)) with the property that any n members of X determine at most f(n) holes, which means that the complement of their union has at most f(n) bounded connected components. We use tools from extremal graph theory and the topological Helly theorem to prove that X can be decomposed into at most p (1-fold) packings, where p is a constant depending only on k and f.

Cambridge Univ Press2016

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many pro

Random graph

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which