Category Mathematics
Discrepancy I
Consider a set system, a.k.a. hypergraph, where is the ground set and where . We wish to color the ground set $V$ with two colors, say red and blue, in such way that all sets in the family are colored in a “balanced” way, i.e., each set has nearly the same number of red and blue points. […]
Expected number of triangles in G(n,m)
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 […]
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 […]
tsourakakis.com 