Return to Question

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. UPD: according to the Wikipedia page, minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.

My questions are:

1. Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs should be)?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. UPD: according to the Wikipedia page, non-trivial minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.

My questions are:

1. Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs should be)?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. UPD: according to the Wikipedia page, minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.

My questions are:

1. Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs are)?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. UPD: according to the Wikipedia page, minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.

My questions are:

1. Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs should be)?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. My questions are:

1. Is there a large enough $k$ so that all finite groups are automorphism groups of graphs with treewidth at most $k$? If no, which growth rate of $k = k(|V|)$ is required for universal representability?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. UPD: according to the Wikipedia page, minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.

My questions are:

1. Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs are)?
2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?