Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Lovasz Lemma local: dépendances et indépendance

Dans cours

MATH-467: Probabilistic methods in combinatorics

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desir ...

Description

Cette séance de cours présente le Lemme local de Lovasz, qui traite des événements qui ne sont pas mutuellement indépendants. Il couvre le concept de «petites dépendances» et explore les graphiques de dépendance pour comprendre comment les événements sont liés. La séance de cours traite également des conditions dans lesquelles il existe des solutions valables satisfaisant le lemme local de Lovasz, tel que défini par la localisation des racines dans le polynôme d'indépendance.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Concepts associés (28)

Dependency graph

In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph. Given a set of objects and a transitive relation with modeling a dependency "a depends on b" ("a needs b evaluated first"), the dependency graph is a graph with the transitive reduction of R.

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.

Matroïde

En mathématiques, et plus particulièrement en combinatoire, un matroïde est une structure introduite comme un cadre général pour le concept d'indépendance linéaire. Elle est donc naturellement liée à l'algèbre linéaire (déjà au niveau du vocabulaire : indépendant, base, rang), mais aussi à la théorie des graphes (circuit, cycle), à l'algorithmique (algorithme glouton), et à la géométrie (pour diverses questions liées à la représentation). La notion a été introduite en 1935 par Whitney. Le mot matroïde provient du mot matrice.

Indépendance algébrique

En algèbre, l'indépendance algébrique d'un ensemble de nombres, sur un corps commutatif, décrit le fait que ses éléments ne sont pas racines d'un polynôme en plusieurs indéterminées à coefficients dans ce corps. Soient L un corps commutatif, S un sous-ensemble de L et K un sous-corps de L. On dit que S est algébriquement libre sur K, ou que ses éléments sont algébriquement indépendants sur K si, pour tout suite finie (s, ... , s) d'éléments distincts de S et tout polynôme non nul P(X, ...

Matroid oracle

In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications. The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent.

Afficher plus

Séances de cours associées (33)

Ensembles et opérations: Introduction aux mathématiques

Couvre les bases des ensembles et des opérations en mathématiques, des propriétés des ensembles aux opérations avancées.

Relations en informatique

Explore les propriétés des relations en informatique, y compris les relations d'équivalence et la partition d'un ensemble.

La réalisation nerve et géométrique

Déplacez-vous dans le calcul et la réalisation géométrique de petites catégories, explorant la relation entre les nerfs et les structures géométriques.

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Matroids: Intersection matroid

Couvre le concept de matroids, se concentrant sur l'intersection matroid et les propriétés des sous-ensembles d'un ensemble de sol.

Afficher plus

Concepts associés (28)

Dependency graph

Graphe orienté acyclique

Matroïde

Indépendance algébrique

Matroid oracle

Afficher plus