Return to Question

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):

Can a class of objects or structures of a given kind X that is characterized by some "external condition" Y be defined by a condition Z in their respective "internal" language, and if so: how?

Well-known examples ("external condition" = "internal condition"):

1. groups $G$ isomorphic to a subgroup of the symmetric group on $G$ = all groups (Cayley's theorem)

2. graphs embeddable in the plane = graphs not containing a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski's theorem)

3. numbers n of trees on k labeled vertices = numbers n = k^k-2 for some k > 1 (Cayley's theorem on trees)

4. numbers n with only one group of order n = numbers n = p₁ · p₂ · ... · p_k for some k > 0, where the p_i are distinct primes and no p_j-1 is divisible by any p_i (cyclic numbers, see Sloane's A003277)

Further examples from MO:

• Which graphs are Cayley graphs?

• Can we recognize when a category is equivalent to the category of models of a first order theory?

• Can you determine whether a graph is the 1-skeleton of a polytope?

Question #1: What's the proper way to characterize this pattern of questions? What's the common context / rationale?

Question #2: How is the introductory question to be posed properly?

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):

Can a class of objects or structures of a given kind X that is characterized by some "external condition" Y be defined by a condition Z in their respective "internal" language, and if so: how?

Well-known examples ("external condition" = "internal condition"):

1. groups $G$ isomorphic to a subgroup of the symmetric group on $G$ = all groups (Cayley's theorem)

2. graphs embeddable in the plane = graphs not containing a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski's theorem)

3. numbers n of trees on k labeled vertices = numbers n = k^k-2 for some k > 1 (Cayley's theorem on trees)

4. numbers n with only one group of order n = numbers n = p₁ · p₂ · ... · p_k for some k > 0, where the p_i are distinct primes and no p_j-1 is divisible by any p_i (cyclic numbers, see Sloane's A003277)

Further examples from MO:

• Which graphs are Cayley graphs?

• Can we recognize when a category is equivalent to the category of models of a first order theory?

• Can you determine whether a graph is the 1-skeleton of a polytope?

Question #1: What's the proper way to characterize this pattern of questions? What's the common context / rationale?

Question #2: How is the introductory question to be posed properly?

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):

Can a class of objects or structures of a given kind X that is characterized by some "external condition" Y be defined by a condition Z in their respective "internal" language, and if so: how?

Well-known examples ("external condition" = "internal condition"):

1. groups $G$ isomorphic to a subgroup of the symmetric group on $G$ = all groups (Cayley's theorem)

2. graphs embeddable in the plane = graphs not containing a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski's theorem)

3. numbers n of trees on k labeled vertices = numbers n = k^k-2 for some k > 1 (Cayley's theorem on trees)

4. numbers n with only one group of order n = numbers n = p₁ · p₂ · ... · p_k for some k > 0, where the p_i are distinct primes and no p_j-1 is divisible by any p_i (cyclic numbers, see Sloane's A003277)

Further examples from MO:

• Which graphs are Cayley graphs?

• Can we recognize when a category is equivalent to the category of models of a first order theory?

• Can you determine whether a graph is the 1-skeleton of a polytope?

Question #1: What's the proper way to characterize this pattern of questions? What's the common context / rationale?

Question #2: How is the introductory question to be posed properly?

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):

Can a class of objects or structures of a given kind X that is characterized by some "external condition" Y be defined by a condition Z in their respective "internal" language, and if so: how?

Well-known examples ("external condition" = "internal condition"):

1. groups $G$ isomorphic to a subgroup of the symmetric group on $G$ = all groups (Cayley's theorem)

2. graphs embeddable in the plane = graphs not containing a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski's theorem)

3. numbers n of trees on k labeled vertices = numbers n = k^k-2 for some k > 1 (Cayley's theorem on trees)

4. numbers n with only one group of order n = numbers n = p₁ · p₂ · ... · p_k for some k > 0, where the p_i are distinct primes and no p_j-1 is divisible by any p_i (cyclic numbers, see Sloane's A003277)

Further examples from MO:

• Which graphs are Cayley graphs?

• Can we recognize when a category is equivalent to the category of models of a first order theory?

• Can you determine whether a graph is the 1-skeleton of a polytope?

Question #1: What's the proper way to characterize this pattern of questions? What's the common context / rationale?

Question #2: How is the introductory question to be posed properly?