Invariant systems of representatives, or the cost of symmetry (Q2022146): Difference between revisions

Main Theorem. Suppose that a group \(G\) acts on a set \(U\), and \(\mathcal F\) is a \(G\)-invariant family of finite subsets of \(U\) of uniformly bounded cardinality. Let \(X \subseteq U\) be a finite system of representatives for this family i.e. \(X \cap F \not= \emptyset\) for any \(F \in \mathcal F\). Then there exists a \(G\)-invariant system of representatives \(Y\) such that \(|Y| \leq |X| \cdot \max_{F\in \mathcal F} |F |\). The proof of the main theorem is elementary, except that the authors use B. Neumann's theorem on covering groups by cosets. Corollary. Let \(\Gamma\) be a graph and let \(K\) be a finite graph. Then if \(\Gamma\) contains a finite set of vertices (edges) \(X\) such that each subgraph of \(\Gamma\) isomorphic to \(K\) has at least one vertex (edge) from \(X\), then \(\Gamma\) contains a finite set of vertices (edges) \(Y\), \(|Y|\leq |X|\cdot \) (the number of vertices (edges) of \(K\), invariant with respect to all automorphisms of \(\Gamma\) and such that again each subgraph of \(\Gamma\) isomorphic to \(K\) has at least one vertex (edge) from \(Y\).