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

Lecture

Regularity Lemmas and Density Theorems

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 proof of Szemerédi's Regularity Lemma and Roth's Density Theorem, focusing on the process of partitioning graphs and identifying regular structures. It explains how to detect irregular pairs in a graph, the concept of supervertices, and the implications of not satisfying regularity conditions. The lecture also delves into the application of these lemmas in identifying arithmetic progressions within sets and avoiding them. Additionally, it discusses the significance of cutting graphs into precise partitions and the conditions under which irregularities occur.

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

Related concepts (32)

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory.

Naive set theory

Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It describes the aspects of mathematical sets familiar in discrete mathematics (for example Venn diagrams and symbolic reasoning about their Boolean algebra), and suffices for the everyday use of set theory concepts in contemporary mathematics.

Zermelo set theory

Zermelo set theory (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It bears certain differences from its descendants, which are not always understood, and are frequently misquoted. This article sets out the original axioms, with the original text (translated into English) and original numbering.

Zermelo–Fraenkel set theory

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.

Constructive set theory

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories. In addition to rejecting the principle of excluded middle (), constructive set theories often require some logical quantifiers in their axioms to be set bounded, motivated by results tied to impredicativity.

Related lectures (53)

Sets and Operations: Introduction to Mathematics

Covers the basics of sets and operations in mathematics, from set properties to advanced operations.

Cartesian Product in Linear Algebra

Explores the Cartesian product in linear algebra and the method of induction for proving propositions.

Set Theory: Basics and Operations

Covers the basics of set theory, including sets, elements, operations, empty sets, and defining sets based on properties.

Cartesian Product MOOC: Analysis I (part 1): Prelude, basic concepts, real numbers MOOC: Analysis I

Covers the concept of the Cartesian product, emphasizing the order of elements in pairs.

Real Numbers: Sets and Operations