Category Graph Theory
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 . […]
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 […]
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.