Category Mathematics

Expectation of minimum of n i.i.d. uniform random variables

Let  be independent uniform random variables from , and consider the random variable . Computing the expectation is a routine computation: . However, there a slick way of computing this expectation. Let be another uniform random variable in . Consider the probability . On the one hand due to symmetry, it is equal to , on […]

Fair allocation of a pizza

Empty bins

Suppose that  balls,  where is a constant, are thrown sequentially to bins, all of which are initially empty. Let be the number of empty bins after we have thrown balls. Clearly, . Let’s see how we can understand this sequence of random variables. When we move from step to we throw a ball. It either falls in an […]

Graph sphericity

The sphericity  of a graph is the smallest dimension such that there exists a mapping such that if and only if . The following theorem is due to Frankl and Maehara  and is a nice application of random projections. Here, . Theorem [Frankl-Maehara 1988]: Let be a graph with minimum adjacency eigenvalue where and suppose . […]

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 […]