Matematics++, spring semester 2024/2025

Ida Kantor, Robert Šámal, Martin Tancer

Topic

Modern computer science often uses mathematical tools that reach beyond the scope of standard mathematical courses in the bachelor program. This course will present a (somewhat condensed) introduction to several fields of mathematics that proved especially useful in computer science and in discrete mathematics. Computer science applications will be shown as well. This course is suitable for master's or PhD students of computer science. The students are assumed to have prior knowledge in the extent of mandatory courses of the bachelor program in computer science. For illustration, see topics of past lectures.

This year we will focus on measure theory -- as a background for probability. Also on geometry in high dimensions and a bit of functional analysis.

Prerequisites

Interest in mathematics, knowledge roughly in the extend of cs bachalor degree at MFF UK. We will mostly build upon analysis, probability and linear algebra.

Extent

Two hours of lectures and two hours of tutorials weekly (2/2). Credit and exam.

Tutorials

A substantial part of the class will consist of independent solving of homework problems. Credit will be given for solving a sufficient number of problems. The exercises will be led by Petr Chmel and Tomáš Hons.

Exam

Will be oral, containing both theory and problems. For the arrangement of time, email the lecturers. (Ideally all of them, the one with similar time preferences as you will reply.) Note: each of us will examine you from anything that was being taught, not just his/her third!

Literature

[KMS] I. Kantor, J. Matoušek, R. Šámal: Mathematics++ (should be available in the library)
[W] T.B. Ward: Functional analysis lecture notes [AS] N. Alon, J. H. Spencer: The Probabilistic Method (so far only Azuma's inequality)

Covered material

(For illustration, see the web page of last edition of this class.)
DateTopicLiterature
18. 2.[IK] Motivation for why we need the notion of Lebesgue measure (i.e., a generalization of the length of an interval to more general sets): integrating more exotic functions, probability. Four natural properties that we would like this measure to satisfy (it is defined on all subsets of reals, for intervals it agrees with their length, it is translation invariant and countably additive) . Definition of outer Lebesgue measure and proof that it has three-and-half of the four properties: instead of countable additivity, we could prove only countable subadditivity. Sadly, there is a counterexample to countable additivity: the Vitali set. And tragically, it can be proved our whole task is hopeless: that no set function on \(\mathbb{R}\) satisfies all 4 properties. We give up on the first property, define (Lebesgue) measurable sets and restrict the outer measure to this family. Definition of \(\sigma\)-algebra and mentioned that measurable sets form a \(\sigma\)-algebra (proof left as an exercise). Definition of smallest \(\sigma\)-algebra generated by a set. Borel sets. Mentioned that Borel sets are measurable (proof left as an exercise). [KMS], Chapter 1
25.2.[IK] Proof of countable additivity for the Lebesgue measure. Terminology: null set, almost everywhere. Higher dimensional Lebesgue measure. General definition of measure and of measure space. Examples: counting measure, Dirac measure. Generalized definition of partition of a set. Simple function, integral of simple function. Integral of nonnegative function. A particular approximation of a nonnegative function by a simple function (as a motivation for why we only want to define integrals for measurable functions). Measurable functions, integral of a measurable function. Integrable functions. Lemma (without proof): for a bounded function f defined on a set of finite measure, supremum of the integrals of lower approximations by simple functions equals infimum of the integrals of upper approximations by simple functions, if and only if f is measurable. [KMS], Chapter 1
4.3.[IK] Measurable functions defined on general measure spaces (with codomain being the real line). In this context: simple functions, integral. Properties of integral. Complete measure spaces (and why we like them). Fatou's lemma. Monotone convergence theorem. Linearity of integral. Littlewood principles: mentioned informally. [KMS], Chapter 1
11. 3.[IK] Dominated convergence theorem. Product of measure spaces. Sigma-finite measure spaces. Fubini theorem, Tonelli theorem. Definition of probability space. Observation that the axioms are the same as for measure space, with the added requirement that probability of the whole set is 1. Motivation for the notion of density. In general, if we have a nonnegative measurable function f defined on a measure space, we may use it as "density" to define a new measure. This way, we get, e.g., the Gaussian measure from the Lebesgue measure. Motivation and definition of expected value. Normal distribution, computation of the constant of the density function. [KMS], Chapter 2.3
... [RŠ] ...
22.4. [MT] High-dimensional geometry. Brief motivation (image recognition, mathcing polytope, ellipsoid method). High-dimensional paradoxes ("small" ball enclosed by other balls, not-so-good random sampling, neighborhood of the equator of a high-dimensional sphere). Unidomdular function, Brunn's theorem. The Brunn-Minkowski inequaliy. Proof that the Brunn-Minkowski inequality implies Brunn's theorem. Isoperimetric problem and its solution via the Brunn-Minkowski inequality. Lemma (Brunn-Minkowski on the line). A dimension-free Brunn-Minkowski inequality and the proof that it implies the standard Brunn-Minkowski inequality. [KMS], Chapters 2.1, 2.2.
29.4. [MT] Prékopa--Leindler inequality (as a generalization of a dimesion-free Brunn-Minkowski) and its proof. Measure concentration: Measure concentration on the sphere. Other spaces with measure concentration (Gaussian measure in $\mathbb{R}^d$; Hamming cube, permutations, constant degree expanders.) A sketch of the proof of measure concentration on the sphere (the first step is the isoperimetric inequality on the sphere---it has not been sketched how to get it; the second step is to bound the measure of a neighborhood of a hemisphere---this has been explained). [KMS], Chapters 2.2, 2.4
6.5. [MT] Lipschitz functions (definition and two examples). Theorem: Concentration of Lipschitz functions on the sphere (proof via measure concentration on the sphere). Gromov's sphere waist theorem (without proof). Martingales: motivation, definition, a vertex exposure martingale. Azuma's inequality (without proof) and its corollary. An application of Azuma's inequality: Concentration of the chromatic number in the random graph $G(n,p)$ (proof sketched). Higher-dimensional Gaussian measure (via formula as well as via a vector of independent random variables with the standard normal distribution). An application of the Gaussian measure: generating a random point on the sphere. Lemma regarding Gaussian projection (proof sketched). Remarks on normal distribution (not necessarily standard normal). [KMS], Chapters 2.3, 2.4; [AS], Chapters 7.1, 7.2 (according to the 4th edition).