CECM Colloquium

November 29, 2000 from 1:30 - 3:25 in K9509, SFU

Prabhakar Raghavan, Verity Corporation

From 1:30 - 2:20 Talks on

"Networks and Sub-Networks in the World-Wide Web"

Abstract: We discuss several structural properties of graphs arising from the world-wide web including the graph of hyperlinks, and the graph induced by connections between distributed search servents. We review a number of algorithmic investigations of the structure of these networks, and conclude by proposing stochastic models for the evolution of these networks.

Romeo Rizzi
Instituto Trentino di Cultura, IRST, Trento, Italy
email: rizzi@itc.it
From 2:35 - 3:25 Talks on

"Indecomposable $r$-graphs and some other counterexamples"

Abstract:An $r$-graph is any graph that can be obtained as a conic combination of its own $1$-factors. Equivalenty, an $r$-graph is an $r$-regular graph such that at least $r$-edges leave each odd-cardinality subset of nodes. An $r$-graph $(V,E)$ is indecomposable if its edge set $E$ cannot be partitioned as $E=E_1 \cup E_2$ so that $(V,E_1)$ and $(V,E_2)$ are both $r$-graphs. We construct an indecomposable $r$-graph for every integer $r\geq 4$. This answers a question posed by Seymour and implies that the coefficients in the Schrijver System (minimal TDI system) of the $T$-cut polyhedron are not bounded by any constant.

A graph in which every two $1$-factors intersect is said to be poorly matchable. Every poorly matchable $r$-graph is indecomposable. We show that the converse of this statement is false for $r\geq 4$. Further, we construct a poorly matchable $r$-graph for every $r\geq 4$.

Related topics: Fulkerson Coloring Conjecture, Seymour's Coloring Conjecture, Hilbert bases, packing $T$-joins, colorings and flows.