\input zb-basic
\input zb-ioport
\iteman{io-port 00887769}
\itemau{Imrich, Wilfried; Sauer, Norbert; Woess, Wolfgang}
\itemti{The average size of nonsingular sets in a graph.}
\itemso{Sauer, N. W. (ed.) et al., Finite and infinite combinatorics in sets and logic. Proceedings of the NATO Advanced Study Institute, Banff, Canada, April 21-May 4, 1991. Dordrecht: Kluwer Academic Publishers. NATO ASI Ser., Ser. C, Math. Phys. Sci. 411, 199-205 (1993).}
\itemab
Summary: A nonsingular set in a finite graph is defined as the vertex set of an induced subgraph which has no isolated point. If $G$ is a graph without isolated points and with at least two vertices and $B$ is a connected subgraph, then the average size of those nonsingular sets in $G$ which contain $B$ is at least $(|G |+ |B |)/2$. This result is used to prove the following: if ${\cal F}$ is a family of sets which is closed with respect to union, and if none of the generating sets in ${\cal F}$ has more than two elements, then the average size of a set in ${\cal F}$ is at least half of the size of the largest set in ${\cal F}$.
\itemrv{~}
\itemcc{}
\itemut{isolated point; nonsingular sets; family of sets; generating sets; average size}
\itemli{}
\end