Dominik Farhan

Discrete optimization

These are some of my notes on discrete optimization mostly based on lectures by professor Martin Loebl.

If you find any mistakes, I would really appreciate if you could drop me an email at dominik(salamander) so I can fix them.

Appart from the part titled Definitions and examples, the notes are somewhat raw and a few proofs are incomplete.


Are you preparing for the exam?

If you are about to take the exam from Discrete and Continous Optimization at MFF these notes can serve you well. They were originally written as a preparation for this one occasion. However, I later added some other things that I considered relevant and I don't try to distinguish between the preparation for the exam and all additional materials.

When I took the exam in the summer of 2023 the discrete part was write-all-you-know about one of the topics. The topic was choosen by professor Loebl. Studying professors Loebl's notes should be enough to pass but you need to understand them. If something is triv. for the professor, it should appear trivialy simple to you too.

Also the first impression seemed to matter quite a lot. I was asked about Rank function and submodularity and after meticulously prooving the equivalent definition of the rank function he hapilly stopped me and we continued with a brief talk about submodularity, how to prove the corresponding theorem (to my reliev I wasn't asked to write down the proof), and applications.

Other resources

Here is a list of other resources I enjoyed reading: