MHB How Many Unique Substructures Exist in an n-Clique?

  • Thread starter Thread starter Andrei1
  • Start date Start date
AI Thread Summary
The discussion centers on determining the number of unique substructures in an n-clique, denoted as K_n. For part (a), the answer of 2^n for the number of subgraphs is generally accepted, though some may argue for 2^n - 1 if excluding the empty graph. Part (b) is debated, as the correct interpretation of substructures leads to a conclusion that there are multiple unique structures, not simply n. Part (c) raises questions about the definition of elementary substructures, with clarification provided on the criteria for such structures. Overall, the conversation emphasizes the complexity of defining and counting substructures in graph theory.
Andrei1
Messages
36
Reaction score
0
Let $$K_n$$ be the $$n$$-clique for some $$n\in\mathbb{N}$$. Then any graph having at most $$n$$ vertices is a subgraph of $$K_n$$.
(a) How many substructures does $$K_n$$ have?
(b) How many substructures does $$K_n$$ have up to isomorphism?
(c) How many elementary substructures does $$K_n$$ have?
My answers:
(a) $$2^n$$
(b) $$n$$
(c) $$2^n$$
Are they correct?
 
Physics news on Phys.org
Andrei said:
My answers:
(a) $$2^n$$
(b) $$n$$
(c) $$2^n$$
Are they correct?
If by substructures you mean subgraph, then the answer to part (a) looks okay. Some people may write $2^n-1$ because they might not want to include $\emptyset$ in the list.

For the second, is the question asking to find out the number of graphs, up to isomorphism, having at most $n$ vertices. In that case, the answer cannot be just $n$.

For part (c), I don't know the definition of elementary substructures. Can you please define it?
 
$$M$$ is a substructure of $$N$$ ... if
1. $$M$$ is a structure having the same vocabulary as $$N$$,
2. the underlying set $$U_M$$ of $$M$$ is a subset of the underlying set $$U_N$$ of $$N$$, and
3. $$M$$ interprets the vocabulary in the same manner as $$N$$ on $$U_M$$.

Let $$N$$ and $$M$$ be structures in the same vocabulary. Then $$M$$ is an elementary substructure of $$N$$ ... if and only if the identity function $$id\colon M\to N$$ defined by $$id(x)=x$$ is an elementary embedding [preserves all formulas].

About (b). Let's take a 4-clique. Any subgraph of it is not a substructure if it is not a clique. So I have, up to isomorphism, 4 substrucutures: one 1-clique, one 2-clique, ...
 
Andrei said:
About (b). Let's take a 4-clique. Any subgraph of it is not a substructure if it is not a clique. So I have, up to isomorphism, 4 substrucutures: one 1-clique, one 2-clique, ...
Then by substructures you do not means subgraphs. It's fine then.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top