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"
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.
Instituto Trentino di Cultura, IRST, Trento, Italy
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.