Category Problem of the day

Fair allocation of a pizza

An observation on edge densities of the union of isomorphic copies of a fixed graph

Consider a fixed graph with vertices and edges respectively. Assume that is balanced which means that the maximum edge density among all possible subgraphs of is achieved from $H$. Take two copies of , call them and create a new graph . In case the two copies are edge disjoint then the edge density of […]

Recurrences and the riddle of the day

Sometimes solving exactly a recurrence can be demanding. The use of software can be useful 🙂 Something that I slept under the rag above and I want to mention it since this post by no means is supposed to be intimidating to a novice, is that in many applications (lemmas,theorems etc.) one needs the asymptotic behavior […]

Double counting

Double counting is a simple yet so powerful way to prove non-trivial theorems. Here, we present some applications of the double counting principle. Our main source is the excellent book “Extremal Combinatorics” by Stasys Jukna [1]. A newer edition from the one in the picture (which shows the book I have) is also available now. […]

Edge-disjoint spanning subgraphs of large degree

Prove the following: you can always find in a simple undirected graph of minimum degree two spanning edge disjoint subgraphs of minimum degree at least . Give also an algorithmic procedure to find such subgraphs.

Fekete’s Lemma and an application on Ramsey theory

Fekete’s lemma was proved by Pólya and Szegő. A historical note, not related to Fekete’s lemma thought, which I did not know myself before reading the biography of Szegő and I find it for some reason interesting to know: At the age of 15, the young John von Neumann, recognised as a mathematical prodigy, was […]