Naturally induced type in flag algebras

78 Views Asked by At

In Razborov's paper on flag algebras (in particular, the second paragraph under section 2.2), he writes:

Given a type $\sigma$ of size $k$, $k' \leq k$ and an injective mapping $\eta : [k'] \rightarrow [k]$, let $\sigma|_{\eta}$ be the naturally induced type of size $k'$ (that is, for any predicate symbol $P(x_{1}, ... , x_{r})$ in $L$ and any $i_{1}, ... ,i_{r} \in [k']$, $\sigma|_{\eta} \vDash P(i_{1}, ..., i_{r})$ iff $\sigma \vDash P(\eta(i_{1}), ..., \eta(i_{r}))$. For a $\sigma$-flag $F=(M,\theta)$, the $\sigma|_{\eta}$-flag $F|_{\eta}$ is defined as $F|_{\eta} = (M, \theta\eta)$.

I am unfamiliar with the basic model theory that this paper is written in and am more interested in the application to graph theory. In the context of graph theory, types are essentially graphs with vertices labelled in bijection with some set of integers; in this case, $\sigma$ is a graph on $k$ vertices with those vertices labelled in bijection with $[k]$.

My question is: how should I be thinking about this "induced type" $\sigma|_{\eta}$ in the context of graph theory? I see that it is a smaller type of size $k'$, but how are these vertices labelled in relation to the vertices in $\sigma$?

1

There are 1 best solutions below

0
On BEST ANSWER

The injective mapping $\eta$ tells you the labeling. The type $\sigma|_\eta$ is a subgraph of $\sigma$ (when thinking of both as unlabeled graphs); the vertices labeled $1, 2, \dots, k'$ in $\sigma|_\eta$ are labeled $\eta(1), \eta(2), \dots, \eta(k')$ in $\sigma$.

Let me try to give an example. Let $\sigma$ be the $2$-vertex type with an edge between vertices $1$ and $2$, and let $\sigma'$ be the $1$-vertex type. Let $F, G, H$ be the flags in the diagram below:

here are some flags

Here, $F$ is a $\sigma$-flag, while $G$ and $H$ are $\sigma'$-flags.

We can define two injections from $[1]$ to $[2]$: $\eta$, which sends $1$ to $1$, and $\zeta$, which sends $1$ to $2$. Both $\sigma|_\eta$ and $\sigma|_\zeta$ are the $1$-vertex type $\sigma'$, but averaging will work differently.

Let's suppose we apply the averaging operator $[\![\cdot ]\!]_{\sigma,\eta}$ to $F$. This gives a multiple of $F|_\eta = G$, because $\eta$ tells us "the vertex labeled $1$ in $\sigma'$ corrresponds to the vertex labeled $1$ in $\sigma$". The normalizing factor $q_{\sigma,\eta}(F)$ is $1$, because no matter which unlabeled vertex of $G$ you label as $2$, you get $F$ back. So $[\![F]\!]_{\sigma,\eta} = G$.

Now apply the averaging operator $[\![\cdot ]\!]_{\sigma,\zeta}$ to $F$. This gives a multiple of $F|_\zeta = H$, because $\zeta$ tells us "the vertex labeled $1$ in $\sigma'$ corresponds to the vertex labeled $2$ in $\sigma$". The normalizing factor $q_{\sigma,\zeta}(F)$ is $\frac12$, because only one of two choices for the other vertex in $H$ will produce $F$. So $[\![F]\!]_{\sigma,\zeta} = \frac12 H$.