Interior point method, continued

In this post, we continue the design and analysis of an interior point method algorithm to solve a linear program that we started last time.

Strong duality for linear programs

In this post, we prove the strong duality theorem for linear programs, which says that if either the primal or dual is feasible, then their optimal values are equal.

Interior point method

In this post, we begin describing a basic interior point method to solve a linear program. We follow material from these notes by Professor Michel Goemans (relevant lectures are 6,7 and 8), filling in the details.

Basic properties of the Laplacian

In this post, we lay out the basics of spectral graph theory - the study of graph structure through the lens of linear algebra. Some of this material is based on a lecture for 6.854 given by Professor Aleksander Madry, and these notes by Professor Dan Spielman.

The splitting lemma in abelian categories

The splitting lemma in abelian categories is a basic tool for decomposing objects into biproducts. It is at the heart of some powerful structure theorems, such as the ones for finitely generated abelian groups and more generally finitely generated modules over a PID.

Decomposing morphisms in abelian categories

In this short post we state the basic decomposition result that any morphism in an abelian category decomposes canonically into an epimorphism followed by a monomorphism, and derive some very useful consequences.

Abelian categories

In this short post we define abelian categories (which takes some work), which were introduced as abstractions of some core properties of categories like abelian groups and modules over a ring; so for example most of homological algebra can be carried over any abelian category, which is neat.

1- and 2-factorization of graphs and digraphs

In this post we go over some basic decomposition results in regular graphs, such as 1-factorization and 2-factorization, in both directed and undirected cases. These are useful when e.g. we want to represent a graph as some group action (a so-called Schreier graph); however, I haven't been able to find some of them properly written up on the internet.

Representation theory of the symmetric group: basics

In this post we lay out some introductory material on the representation theory of $ S_n$ over $ \mathbb{C}$.

Talagrand's concentration inequality

In this post we basically go over a proof of Talagrand's concentration inequality, following material from Bela Bollobas' part III course on probabilistic combinatorics. Things can get rather messy, so hopefully writing this will force me to properly understand it.