Uniform bound on the size of support of a witness

Let R\subset X\times Y be an equivariant relation. We show that under a certain assumption on X, for every x\in X, if there exists a witness y\in Y such that R(x,y) holds, then there also exists one with small support. We show an application to extending homomorphisms.

The assumption on the set X is that it is locally finite, i.e., for every finite support S there are only finitely many elements supported by S in X. Examples of such sets include all orbit-finite sets, but also the set of all finitely supported functions between two orbit-finite sets. See this post for more on locally finite sets.

Lemma. Suppose that X is locally finite and R\subset X\times Y is an equivariant relation. Then there is a function f:\Nat \to \Nat such that for every x\in X if there exists a witness y\in Y such that R(x,y), then there is one with|\sup y|\le f(|\sup x|).

Proof. For an element x\in X, let s(x) denote the minimal size of the support of an element y such that R(x,y) holds, and 0 if no such element exists. Then s is an equivariant function from X to \Nat.

For a number n, let X_n denote the set of elements of X whose support has size at most n. By local finiteness of X, the set X_n is orbit-finite, for each number n. Therefore, the mapping s, restricted to X_n, attains a maximal value, let it be denoted by f(n)\in\Nat. The function f satisfies the condition of the lemma.\square


An application. In the application below, it does not really matter what an orbit-finite relational structure is. What matters is that their domains are orbit-finite, so the set of (partial) homomorphisms between two such structures is locally finite.

Proposition. Let A,B be two orbit-finite relational structures. Let h be a finitely supported, partial homomorphism from A to B, which extends to some homomorphism \hat h:A\to B. Then the extension \hat h:A\to B can be chosen so that  |\sup {\hat h}|\le f(|\sup {h}|), where f:\Nat\to\Nat is some mapping depending on A,B.

Proof. Apply the lemma to the relation R, consisting of pairs (f_0,f) where f_0 is a partial homomorphism from A to B and f is an extension of f_0 to f.\square


2 thoughts on “Uniform bound on the size of support of a witness”

  1. The assumption that the domain of R is all of X is not necessary, is it? Later you say “if a witness exists” anyway… Just say that the function f is partial and everything should work.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>