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

Lecture

Graph Theory: Girth and Independence

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 concept of girth in graphs, the existence of graphs with a certain girth and independence number, and the probability of edges appearing independently. It also discusses the union bound, finding sets, and the recoloring of hypergraphs.

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)

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 nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

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.

Component (graph theory)

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.

Related lectures (32)

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Dense Graphs: From Theory to Applications

Explores the transition from sparse to dense graphs and their real-world applications.

Probabilistic method and its applications

Introduces the probabilistic method to prove existence results in graph theory.

Graphical Models: Representing Probabilistic Distributions

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

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.