Random Graphs
Alan Frieze
Carnegie Mellon University
Wean 7220
Feb 10th, 15:30
We will review some of the major results in random graphs and some of the more challenging open problems. We will cover algorithmic and structural questions. We will touch on newer models, including those related to the WWW.
Speaker: Todd Phillips
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Data Structures for Cellular Decompositions
Abstract:
In many applications of comptutational geometry, we seek to store and manipulate a complex geometric collection that has been decomposed into primitive geometric objects (cells). Common examples include the storage of meshes, scenes, arrangements, or embedded planar graphs. Good data structures must efficiently support localized operations for exploring adjacency and containment between these cells. In general, such decompositions may have very complicated neighborhoods and connectedness that can lead to computational topology problems. We will explore state of the art data structures, and we will see how a group theoretic approach to the problem can yield very elegant solutions. We will also present some recent contributions from both algebraic and data structures viewpoints.
Teresa Maria Jeronimo Sousa
“Decompositions of Graphs”
Thursday, February 9, 2006
4:00 p.m.
Posner Hall, Room 259
ABSTRACT:
The subject of graph decompositions is a vast topic and has been studied for the past 40 years by numerous people. Given two graphs $G$ and $H$, an $H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a graph isomorphic to $H$. We allow partitions only, that is, every edge of $G$ appears in precisely one part. Let $\phi_H(G)$ be the smallest possible number of parts in an $H$-decomposition of $G$. We study the function $\phi_H(n)$ which is the smallest number such that any graph $G$ of order $n$ admits an $H$-decomposition with at most $\phi_H(n)$ elements.
Erdos, Goodman and Posa proved that $\phi_{K_{3}}(n)=t_2(n)$, where $t_{r-1}(n)$ denotes the number of edges in the Turan Graph, $T_{r-1}(n)$. This result was extended by Bollobas, who proved that $\phi_{K_{r}}(n)=t_{r-1}(n)$, for all $n \geq r \geq 3$.
We managed to obtain the exact value of $\phi_H(n)$ for some graphs $H$, namely the cycle of length 5, the cycle of length 5 with one chord and any clique-extension of order $r+1$. For $r \geq 3$ a clique-extension of order $r+1$ is a connected graph that consists of a $K_r$ plus another vertex adjacent to at most $r-1$ vertices of $K_r$. For all fixed $H$ with chromatic number $r \geq 3$ we will prove an asymptotic result about $\phi_H(n)$, that is we show that $\phi_H(n)= t_{r-1}(n)+o(n^2)$. For a non-empty graph $H$ we denote by gcd(H) the greatest common divisor of the degrees of $H$. For a bipartite graph with gcd(H)=1 the exact value of the function $\phi_H(n)$ will be obtained, for $n$ sufficiently large.
The proofs presented use Turan’s Theorem, the Regularity Lemma, results of Pippenger and Spencer, Gustavsson’s Decomposition Theorem for dense graphs and results about packing vertex disjoint copies of a fixed graph $H$ into a large graph $G$.
This is joint work with Oleg Pikhurko.
