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

Lecture

Graphs and Probabilities

In course

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

This lecture covers the relationship between graphs and probabilities, focusing on modular and super modular probabilities, correlation properties, and the use of FKG inequality. It also discusses the adjacency matrix of graphs, the 'pseudorandomness condition', and PSD matrices.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Adjacency matrix

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.

Probability

Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin.

Related lectures (34)

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Probabilities and Statistics

Covers fundamental concepts in probabilities and statistics, including linear regression, exploratory statistics, and the analysis of probabilities.

Graphs: Properties and Representations

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Dependence and Correlation

Explores dependence, correlation, and conditional expectations in probability and statistics, highlighting their significance and limitations.

Variance and Covariance: Properties and Examples