The average order of a connected induced subgraph of a graph and union-intersection systems

Because connectivity is such a basic concept in graph theory, extremal problems concerning the average order of the connected induced subgraphs of a graph have been of notable interest. A particularly resistant open problem is whether or not, for a connected graph $G$ of order $n$, all of whose vertices have degree at least 3, this average is at least $n∕2$. It is shown in this paper that if $G$ is a connected, vertex transitive graph, then the average order of the connected induced subgraphs of $G$ is at least $n∕2$.

The extremal graph theory problems mentioned above lead to a broader theory. The concept of a Union-Intersection System (UIS) $\mathcal{S}≔\left(P,\mathrm{ℬ}\right)$ is introduced, $P$ being a finite set of points and $\mathrm{ℬ}$ a set of subsets of $P$ called blocks satisfying the following simple property for all $A,B\in \mathrm{ℬ}$: if $A\cap B\in \mathrm{ℬ}$, then $A\cup B\in \mathrm{ℬ}$. To generalize results on the average order of a connected induced subgraph of a graph, it is conjectured that if a UIS is, in various senses, “connected and regular,” then the average size of a block is at least half the number of points. We prove that if a union-intersection set system is regular, completely irreducible, and nonredundant, then the average size of a block is at least half the number of points.