Consider picking a graph with m edges on n vertices uniformly at random from the set of all graphs with n vertices and m edges. What is the expected number of triangles? Before we give an exact formula, consider the following heuristic. We can approximate this graph with a random binomial graph (each edge appears […]
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 […]
A set of positive integers is said to have distinct sums (DS) if all sums where are distinct. We are interested in understanding the function . We obtain a simple lower bound on by observing that the set has DS as long as . Therefore, . Interestingly, this lower bound is not far away from being optimal, in […]
tsourakakis.com 