Let $S = \{1, \dots, n\}$. Given a bijection $f : S \to S$ an orbit of $f$ is a set of the form $\{x, f(x), f(f(x)), \dots \}$ for some $x \in S$. We denote by $c(f)$ the number of distinct orbits of $f$. For example, if $n=3$ and $f(1)=2$, $f(2)=1$, $f(3)=3$, the two orbits are $\{1,2\}$ and $\{3\}$, hence $c(f)=2$. Given $k$ bijections $f_1$, $\ldots$, $f_k$ from $S$ to itself, prove that \[ c(f_1) + \dots + c(f_k) \le n(k-1) + c(f) \]where $f : S \to S$ is the composed function $f_1 \circ \dots \circ f_k$. Proposed by Maria Monks Gillespie
Problem
Source: USA December TST for 57th IMO 2016, Problem 1
Tags: combinatorics, December TST, bijection, orbit, graph theory, group theory, linear algebra
ABCDE
21.12.2015 18:34
Darn didn't solve this during the TST but it's basically the special case of
Lemma: Let $G_1$ and $G_2$ be two graphs on $n$ vertices such that $G_1$ has $c_1$ connected components and $G_2$ has $c_2$ connected components. Then $G_1\cup G_2$ has at least $c_1+c_2-n$ connected components.
ProofSuppose that $G_1\cup G_2$ is connected. It suffices to show that given a fixed $G_1$, the maximum number of connected components $G_2$ can have is $n+1-c_1$. Consider a graph $G$ with $c_1$ vertices, where each vertex corresponds to a connected component of $G_1$, and we connect two vertices in $G$ if in $G_2$, there exists an edge between the vertices of their corresponding connected components in $G_1$. $G$ clearly must be connected since $G_1\cup G_2$ is connected. Now, consider a spanning tree $G'$ of $G$. $G'$ has $c_1-1$ edges and the corresponding edges of $G'$ must exist in $G_2$, so there exists a subgraph of $G_2$ with no cycles and at least $c_1-1$ edges. Hence, $G_2$ has at least $n-(c_1-1)=n+1-c_1$ connected components, as desired.
If $G_1\cup G_2$ is not all connected, then we will prove the result with strong induction. The base case of $n=1$ is clearly true. Now, split $G_1\cup G_2$ into two disjoint subgraphs $X$ and $Y$ with $x>0$ and $y>0$ vertices respectively. If $c_x$, $c_y$, $c_{1,x}$, $c_{2,x}$, $c_{1,y}$, and $c_{2,y}$ are the number of connected components of $X$, $Y$, $G_1$ in $X$, $G_2$ in $X$, $G_1$ in $Y$, and $G_2$ in $Y$ respectively, then by induction we have that $c_x\geq c_{1,x}+c_{2,x}-x$ and $c_y\geq c_{1,y}+c_{2,y}-y$. Thus, $G_1\cup G_2$ has $c_x+c_y\geq c_{1,x}+c_{2,x}+c_{1,y}+c_{2,y}-x-y=c_1+c_2-n$ connected components, as desired.
Note that it suffices to show the case where $k=2$ because if it were true we would have that $c(f_1)+\ldots+c(f_k)\leq c(f_1)+\ldots+c(f_{k-1}\circ f_k)+n\leq\ldots\leq n(k-1)+c(f)$.
Consider graphs $H_1$ and $H_2$ on vertices $1,\ldots,n$, where we connect two edges $i$ and $j$ in $H_k$ if $f_k(i)=j$. Note that $H_1$ has $c(f_1)$ connected components and $H_2$ has $c(f_2)$ connected components. Consider the graph $H_1\cup H_2$. Clearly, any orbit of $f_1\circ f_2$ must be contained in $H_1\cup H_2$, so the number of orbits of $f_1\circ f_2$ is at least the number of connected components of $H_1\cup H_2$, which is at least $c_1+c_2-n$, as desired.
fractals
22.12.2015 00:09
Let $s(g) = n - c(g)$ for each such bijection. The desired inequality is equivalent to $s(f) \le s(f_1) + \ldots + s(f_k)$.
Lemma. $s(g)$ is the minimum amount of swaps needed to turn the identity bijection into $g$.
Proof:
It is easy to see that we can create a cycle of length $c$ in $c - 1$ swaps by induction. Doing this for each cycle, $c_1$ through $c_l$, of $g$, yields $\sum_{i = 1}^l (c_i - 1) = \left(\sum_{i = 1}^l c_i\right) - l = n - l$, and $l = c(g)$ so it is possible to write $g$ in $n - c(g)$ swaps. Now we show that this is the minimum.
To do this, simply notice that each swap either links two disjoint cycles together or breaks one complete cycle apart; the net result is that $c(g)$ changes by $1$. To get from the identity to $g$, we need to join cycles at least $n - c(g)$ times, so there must be at least that many swaps. The Lemma is proved. $\Box$
Now we're done, because $f$ can certainly be created by $s(f_1) + \ldots + s(f_k)$ swaps; just follow the swaps for $f_k$, then for $f_{k - 1}$, and so on down to $f_1$. And thus, since $s(f)$ is the length of the minimal sequence of swaps to make $f$, certainly $s(f)$ is at most equal to that quantity.
DrMath
22.12.2015 04:04
Define a connected component of a graph $G$ to be a subgraph such that any edge going through a vertex of $G$ has its other endpoint in a vertex in $G$. Moreover, there does not exist two subgraphs $G_1, G_2$ of $G$ such that $G_1, G_2$ had disjoint vertices and no edge ran between $G_1, G_2$. The problem hinges on this lemma:
Lemma: Suppose $A, B$ are directed graphs on $n$ vertices. Let $E(G)$ be the number of connected components on a graph $G$. Then $E(A)+E(B)\le n+E(A\cup B)$. (Note that some edges might loop at a vertex).
Proof: Let a single vertex be a vertex that is its own connected component. Define a multi-edge to be an edge that is part of a connected component with at least 2 vertices. Suppose that there were $x$ single-vertices in $B$. Then any other connected component of $B$ goes through at least $2$ vertices, and thus $x+2(E(B)-x)\le n$. In other words, $x\ge 2E(B)-n$. In other words, the number of pairs of vertices with an edge running between them is at most $E(B)-x\le n-E(B)$.
Now consider the graph $A$, and repeatedly add edges from graph $B$. Each multi-edge can connect at most 2 connected components of $A$, reducing $E(A)$ by 1. When the process terminates, $E(A)$ has been reduced by at most $n-E(B)$, and thus $E(A\cup B)\ge E(A)-(n-E(B))=E(A)+E(B)-n$, proving the lemma. $\blacksquare$
We will prove $c(f_1)+c(f_2)\le n+c(f_1\circ f_2)$; then the result holds by induction on $k$.
Let $G(f)$ for any $f:S\rightarrow S$ be the directed graph such that an edge goes from $V_1$ to $V_2$ iff $f(V_1)=V_2$. Consider the connected components of $G(f_1)\cup G(f_2)$. Suppose that $C_1, C_2$ were two such connected components, and there existed an edge of $G(f_1\circ f_2)$ that ran from $C_1$ to $C_2$. Then it would follow that either an edge of $G(f_1)$ or $G(f_2)$ ran between $C_1$ and $C_2$, contradicting that $C_1$ and $C_2$ were connected components of $G(f_1)\cup G(f_2)$.
It therefore follows that $E(G(f_1\circ f_2))\ge E(G(f_1)\cup G(f_2))$. Suppose this were not true. Then it would mean that for some two connected components of $G(f_1)\cup G(f_2)$, there is an edge of $G(f_1\circ f_2)$ running between the two components by Pigeonhole, which was proven to be false. But then by our lemma, $E(G(f_1\circ f_2))\ge E(G(f_1)\cup G(f_2))\ge E(G(f_1))+E(G(f_2))-n$. Finally, observe that $c(f)=E(G(f))$ for a function $f:S\rightarrow S$. Thus $c(f_1\circ f_2)\ge c(f_1)+c(f_2)-n$, and the problem is proven, as desired. $\square$
gurev
22.12.2015 05:12
Some motivation for fractals's solution:
This looks a lot like the triangle inequality. How do we make it more like the triangle inequality? The $n(k-1)$ seems very silly, as the left hand side is at most $nk$, so let's change $c(f)$ to $n-c(f)$ to get rid of the constant, so that now it's $s(f) \leq s(f_1)+\cdots+s(f_k)$. This is EXACTLY the triangle inequality, as long as $s$ is a distance metric. Well if you have a group $G$ with some set of generators $S$, a natural way to put a metric on $G$ is to let $|g|$ be the smallest size of a set of generators which multiplies to $g$. And the most natural generators for the permutation group $S_n$ are the transpositions. So it comes as no surprise that the metric induced by these generators is exactly $s$.
pi37
22.12.2015 17:55
fractals wrote:
Let $s(g) = n - c(g)$ for each such bijection. The desired inequality is equivalent to $s(f) \le s(f_1) + \ldots + s(f_k)$.
Lemma. $s(g)$ is the minimum amount of swaps needed to turn the identity bijection into $g$.
Proof:
It is easy to see that we can create a cycle of length $c$ in $c - 1$ swaps by induction. Doing this for each cycle, $c_1$ through $c_l$, of $g$, yields $\sum_{i = 1}^l (c_i - 1) = \left(\sum_{i = 1}^l c_i\right) - l = n - l$, and $l = c(g)$ so it is possible to write $g$ in $n - c(g)$ swaps. Now we show that this is the minimum.
To do this, simply notice that each swap either links two disjoint cycles together or breaks one complete cycle apart; the net result is that $c(g)$ changes by $1$. To get from the identity to $g$, we need to join cycles at least $n - c(g)$ times, so there must be at least that many swaps. The Lemma is proved. $\Box$
Now we're done, because $f$ can certainly be created by $s(f_1) + \ldots + s(f_k)$ swaps; just follow the swaps for $f_k$, then for $f_{k - 1}$, and so on down to $f_1$. And thus, since $s(f)$ is the length of the minimal sequence of swaps to make $f$, certainly $s(f)$ is at most equal to that quantity.
You can also prove the lemma with same approach as other solutions: that is, consider the graph with transpositions as edges. Then to get at most $c(f)$ connected components, we need at least $n-c(f)$ transpositions. This is essentially the same as what you did, just phrased in the way of what a lot of other people did separately.
AdithyaBhaskar
22.12.2015 18:28
Well I am going to sleep in a few min but I solved this using induction twice.
Hydroxide
24.12.2015 06:35
By induction on $k$, it suffices to prove the result for $k=2$, i.e., $c(f_1\circ f_2)\ge c(f_1)+c(f_2)-n$. We will prove this by induction on $n$.
The base case $n=1$ is clear. Now assume the result is true for all lesser $n$. By definition, $f_1$ and $f_2$ are permutations of $S$, so their orbits correspond to their cycles when written in cycle notation. Thus the orbits of $f_1$ form a partition of $S$; call this partition $P_1$. Similarly, let $P_2$ be the partition of $S$ formed by the orbits of $f_2$. If $c(f_1)+c(f_2)\le n+1$, then the result is immediate, so assume that $c(f_1)+c(f_2)\ge n+2$.
Lemma. Given two partitions $P_1$, $P_2$ of $S$ satisfying $|P_1|+|P_2|\ge n+2$, there exists a proper subset $R$ of $S$ such that:
(i) $R$ is the union of $p_1$ parts of $P_1$ and the union of $p_2$ parts of $P_2$, for some $p_1$ and $p_2$
(ii) $|R|\ge p_1+p_2-1$.
ProofWe can construct $R$ using the following algorithm:
Step 1: Start with an arbitrary part $A$ of $P_1$ and color it red. Then color blue all the parts in $P_2$ that contain an element from $A$.
Now continue this process: at each step, color red all the parts in $P_1$ that contain an element from a blue part (other than the parts already colored red), and then color blue all the parts in $P_2$ that contain an element from a red part (other than the parts already colored blue). (These are performed sequentially, not simultaneously.) The process terminates when there is no need to color additional parts in $P_1$ red at the beginning of a step. Let $|R|(t)$, $p_1(t)$, and $p_2(t)$ denote the number of elements in a red part at the end of step $t$, the number of red parts at the end of step $t$, and the number of blue parts at the end of step $t$, respectively. We claim that $|R|(t)\ge p_1(t)+p_2(t)-1$ for all $t$ for which the process has not terminated at the beginning of step $t$, which we will prove by induction.
For the base case $t=1$, we have $|R|(1)=|A|$, $p_1(1)=1$, and $p_2(1)\le |A|$, so indeed $|R|(1)\ge p_1(1)+p_2(1)-1$. Now assume the claim is true for all lesser $t$. Recall that at step $t$, we color red all the parts in $P_1$ that contain an element from a blue part. Let $N$ be the set of "new" elements in a blue part from step $t-1$. Note that we color at most $|N|$ new parts red. But we color exactly $p_1(t)-p_1(t-1)$ new parts red, so
\[
p_1(t)-p_1(t-1)\le |N|.\qquad\qquad\qquad\qquad\qquad(1)
\]Also, from step $t-1$ to step $t$ we increase the number of elements in a red part by $|R|(t)-|R|(t-1)$, so the number of "new" elements in a red part is $|R|(t)-|R|(t-1)-|N|$. Next, we color blue all the parts in $P_2$ that contain an element from a red part (other than the parts that are already colored blue); note that we color at most $|R|(t)-|R|(t-1)-|N|$ new parts blue. But we color exactly $p_2(t)-p_2(t-1)$ new parts blue, so
\[
p_2(t)-p_2(t-1)\le |R|(t)-|R|(t-1)-|N|.\qquad\qquad\qquad\qquad(2)
\]Adding $(1)$ and $(2)$ yields $p_1(t)+p_2(t)-p_1(t-1)-p_2(t-1)\le |R|(t)-|R|(t-1)$, so
\begin{align*}
|R|(t)\ge |R|(t-1)-p_1(t-1)-p_2(t-1)+p_1(t)+p_2(t)\ge p_1(t)+p_2(t)-1
\end{align*}where we used the inductive hypothesis $|R|(t-1)\ge p_1(t-1)+p_2(t-1)-1$. This completes the proof of the claim.
Now observe that this process terminates, as otherwise $S$ would have to have arbitrarily many elements. Moreover, letting $R$ be the union of the red parts in $P_1$ at the end of the step just before termination (or the union of the blue parts in $P_2$; they are the same set) satisfies (i), and it satisfies (ii) by the above claim. It only remains to show that $R$ is a proper subset of $S$. But this is immediate: if $R=S$, then $n=|S|=|R|\ge p_1+p_2-1=|P_1|+|P_2|-1\ge n+1$, contradiction. This completes the proof of the lemma.
Since $|P_1|=c(f_1)$ and $|P_2|=c(f_2)$, the lemma applies. Note that $R$ is an invariant subset of $f_1$ and $f_2$, i.e., the image of $R$ under $f_1$ and $f_2$ is itself. Therefore $R$ is an invariant subset of the permutation $f_1\circ f_2$, which implies that $R$ can be partitioned into some number of orbits of $f_1\circ f_2$. In particular, $R$ consists of at least one orbit.
Next, let $f_1'$ and $f_2'$ be the functions that result from restricting the domain of $f_1$ and $f_2$ to $S\backslash R$, respectively. By property (i) of $R$, it follows that $f_1':S\backslash R\to S\backslash R$ and $f_2': S\backslash R\to S\backslash R$ are permutations of $S\backslash R$. Moreover, $c(f_1')=c(f_1)-p_1$ and $c(f_2')=c(f_2)-p_2$. So by the inductive hypothesis,
\begin{align*}
c(f_1'\circ f_2')&\ge c(f_1')+c(f_2')-|S\backslash R|\\
&=c(f_1)+c(f_2)-p_1-p_2-|S\backslash R|\\
&=c(f_1)+c(f_2)-p_1-p_2-(n-|R|)\\
&=c(f_1)+c(f_2)+(|R|-p_1-p_2)-n\\
&\ge c(f_1)+c(f_2)-n-1
\end{align*}where the last step follows from property (ii) of $R$. Hence, $c(f_1\circ f_2)\ge 1+c(f_1'\circ f_2')\ge c(f_1)+c(f_2)-n$ as desired. This completes the induction and the proof.
Dukejukem
09.01.2016 03:27
Let $S_n$ be the symmetric group. Note that for $\sigma \in S_n$, the orbits of $\sigma$ are just the cycles in the disjoint cycle decomposition of $\sigma.$ Lemma 1: Let $\tau_1, \cdots, \tau_k \in S_n$ be transpositions. Then $c(\tau_1 \cdots \tau_k) \ge n - k.$ Proof of Lemma 1: We go by induction on $k$, the base case $k = 1$ being obvious. Assume the claim true for $k - 1$ and we will prove that $c(\tau_1 \cdots \tau_k) \ge n - k.$ If $\tau_2 \cdots \tau_k$ is written as a product of disjoint cycles, then left multiplication by $\tau_1$ either joins two cycles or breaks one cycle into two. In either case, \[c(\tau_1 \cdots \tau_k) \ge c(\tau_2 \cdots \tau_k) - 1 \ge n - k,\]where the last step follows from the inductive hypothesis. This completes the proof. _________________________________________________________________________________________________ Lemma 2: Each $\sigma \in S_n$ can be written as a product of $n - c(\sigma)$ transpositions. Proof of Lemma 2: Note that a cycle of length $k$ can be written as a product of $k - 1$ transpositions: \[(12 \cdots k) = (1k) \cdots (13)(12).\]By concatenating these transpositions for every cycle in the disjoint cycle decomposition of $\sigma$, the desired result follows. _________________________________________________________________________________________________ Now, note that $f_i$ can be written as a product of $n - c(f_i)$ transpositions by Lemma 2. By concatenating these transpositions, we can write $f = f_1 \cdots f_k$ as a product of $\sum_{i = 1}^{k} \big(n - c(f_i)\big)$ transpositions. Thus, by Lemma 1, \[c(f) \ge n - \sum_{i = 1}^{k} \big(n - c(f_i)\big).\]This yields the desired result. $\square$
Mirrorinf
09.01.2016 06:50
Group theory! Burnside's counting theorem and class equation.
leminscate
15.12.2016 14:11
I don't think the following solution has been posted yet and it seems a bit shorter than the ones in this thread. I'm not completely sure if it works but it seems to as far as I can see. By induction we only need to prove the $k=2$ case i.e. $c(f_1)+c(f_2)\leq n+c(f_1\circ f_2)$. To do this, we induct on $n$. The $n=1$ case is easy, so now suppose that it holds for some $n=k$. We will prove it for $n=k+1$. If neither $f_1$ nor $f_2$ have fixed points, then $c(f_1), c(f_2)\leq \frac{k+1}{2}$ and we are done. Suppose $f_1$ has a fixed point, say $x$. Define $g_1$ to be the function from $S\backslash \{x\}$ to $S\backslash\{x\}$ formed by removing the point $x$ from the directed graph of $f_1$ (if $f_1(x)=x$, $g_1$ is the restriction of $f_1$ to $S\backslash\{x\}$; if $f(a)=x, f(x)=b$ where $a,b\neq x$ simply change it to $f(a)=b$). Note $g_1$ is a bijection. Define $g_2$ similarly. Define $g_3$ from $f_1\circ f_2$ in the same way. If $x$ is also a fixed point of $f_2$, $x$ will be a fixed point of $f_1\circ f_2$. Then $c(f_1\circ f_2)+(k+1)-c(f_1)-c(f_2)=(c(g_3)+1)+(k+1)-(c(g_1)+1)-(c(g_2)+1)=c(g_3)+k-c(g_2)-c(g_1)\geq 0$ by the $n=k$ case. If $x$ is not a fixed point of $f_2$, it will not be a fixed point of $f_1\circ f_2$. Then $c(f_1\circ f_2)+(k+1)-c(f_1)-c(f_2)=c(g_3)+(k+1)-(c(g_1)+1)-c(g_2)=c(g_3)+k-c(g_2)-c(g_1)\geq 0$ by the $n=k$ case. So it's also true for $n=k+1$ so by induction we're done.
solver6
17.12.2016 00:29
For any $f\in S_n$ consider matrix $A_f$, such that $A_f(e_i) := e_{f(e_i)}$ (where $e_1, \ldots, e_n$ is basis of $V$). So one can check that $c(f) = \dim\ker(A_f - E)$. So to prove main inequality we only need to prove next matrix inequality $\dim\ker(A - E)+ \dim\ker(B - E)\leq n + \dim\ker(AB - E)$. $\Box$
MathPanda1
06.03.2017 05:00
As shown above, we only have to prove the result for $k=2$. Consider directed graphs $G_1$ and $G_2$ on vertices $1,\ldots,n$, where we connect an edge from $i$ to $j$ in $G_k$ if $f_k(i)=j$. We use backwards induction on $c(f_2)$. $c(f_2)=n$ is trivial (since $f_2$ maps $i$ to $i$). Now assume it is true for $c(f_2)=k+1$. We prove the result for $k$. Consider some $f_1$ and $f_2$ such that $c(f_2)=k$. There exists a cycle in $G_2$ with at least two elements (since $k<n$), so we take two adjacent elements $a$ and $b$. Suppose $a$ is connected to $b$ and $b$ is connected to $c$. Now, switch the edges so that $a$ is connected to $c$ and $b$ is connected to itself to form $G_2'$ and $f_2'$. Then, $c(f_2') = k+1$. Thus, by the induction hypothesis, $c(f_1)+c(f_2') \leq n+c(f_1 \circ f_2')$ Then, in $G_1\cup G_2'$, from this switch, the only change in that graph is that the neighbors of $a$ and $b$ in $G_1\cup G_2'$ are switched. Thus, at most one cycle was gained in $G_1\cup G_2$ from the switch, so $c(f_1 \circ f_2')-1 \leq c(f_1 \circ f_2)$, and therefore, $c(f_1)+c(f_2) = c(f_1)+c(f_2')-1 \leq n+c(f_1 \circ f_2')-1 \leq n+c(f_1 \circ f_2)$, as required.
SidVicious
24.07.2017 13:41
Can this be done with Burnside lemma? I don't know which group to choose to act on set $S.$
mofumofu
14.03.2018 13:48
Does this work? By induction it suffices to show $c(f)+c(g) \le n+c(gf)$. If $f$ is not all fixed points, say $f(a)=b$, let $f(b)=c$, where $c\ne b$, let $g(b)=d$ and $g(c)=e$. Consider the swaps $f(a)=c, f(b)=b, g(b)=e$ and $g(c)=d$. Note $gf$ stays the same, so RHS stays constant, but no. of orbits of $f$ increases by $1$, and no. of orbits of $g$ decreases by at most $1$, so LHS does not decrease. We keep repeating until $f$ is identity, where the inequality clearly holds.
mathuz
10.10.2018 16:31
solver6 wrote:
For any $f\in S_n$ consider matrix $A_f$, such that $A_f(e_i) := e_{f(e_i)}$ (where $e_1, \ldots, e_n$ is basis of $V$). So one can check that $c(f) = \dim\ker(A_f - E)$. So to prove main inequality we only need to prove next matrix inequality $\dim\ker(A - E)+ \dim\ker(B - E)\leq n + \dim\ker(AB - E)$. $\Box$
Can you explain that: Why \[ c(f) = \dim\ker(A_f - E) ? \]
math_pi_rate
28.02.2019 19:35
I liked this problem a lot (no idea why ). Anyway here's my solution: Consider the symmetric group $S_n$ whose elements are all the bijections from $S$ to itself. It is well known that every element of $S_n$ can be written as a product of disjoint cycles. Let $f$ be an element of $S_n$ with $P$ fixed points, and which can be written as a product of $D$ disjoint cycles (of length at least $2$). Then one can easily see that we have $c(f)=P+D$. Consider the following key claim- CLAIM Let $\eta$ be a cycle of length $z \geq 2$. Then $\eta$ can be converted into the identity permutation in $z-1$ steps. Proof of Claim Even though the claim is intuitively quite clear, I'll give a brief sketch. The proof proceeds by induction on $z$. For $z=2$ the result is obvious. Assume that the result is true for $z$. Then in a $z+1$-cycle, simply interchange one of the elements to get a permutation consisting of a $z$-cycle and a fixed element. Now apply the inductive hypothesis to get the desired result. $\Box$ Let $\sigma$ be the identity element of $S_n$. Also let $\ell(\zeta)$ denote the length of a cycle $\zeta$ of $f$. Then, by our Claim, $f$ can be converted into $\sigma$ in $$\sum_{i=1}^D (\ell(\zeta)-1)=(n-P)-D=n-c(f)$$steps. Keeping this in mind, we define the function $d:S_n \times S_n \rightarrow \mathbb{N} \cup \{0\}$ as follows- $d(\sigma,f)=d(f,\sigma)$ is the minimum number of steps required to convert $f$ to $\sigma$, i.e. $d(f,\sigma)=n-c(f)$ $\text{ }$ $d(f,g)=d(f,\sigma)+d(\sigma,g)$ Note that, because of the way in which we defined the function $d$, it must be a metric function, or specifically it must follow the triangle inequality. Now, consider the $k$ bijections given to us. Then, using the above analysis, we get that $$d(f_1,\sigma)+d(f_2,\sigma)+ \dots +d(f_k,\sigma) \geq d(f_1 \circ f_2 \circ \dots \circ f_k, \sigma) \Rightarrow c(f_1) +c(f_2)+ \dots + c(f_k) \leq n(k-1) + c(f) \quad \blacksquare$$ P.S. Thanks to v_Enhance for writing the Napkin for noobs like me . That book is the reason why I got so interested in group theory. Also can someone please check my solution.
Derive_Foiler
27.12.2019 01:01
Hmm nobody was quite as pathologically inductive as I was . . . By induction it suffices to show this for $k=2.$ By considering a cycle decomposition of $f,$ it suffices to show that, for $\sigma_k$ disjoint cycles, \[c\left(\prod_{k=1}^m\sigma_k\right)+c(g)\le c\left(\prod_{k=1}^{m-1}\sigma_k\right)+c(g\circ\sigma_m)\]because we can inductively "slide" each cycle away from one factor into the other until we get $c(\text{id})+c(g\circ f)$ as the maximal case. By letting $|\sigma_k|$ be the order of $\sigma_k,$ we find that $c\left(\prod_{k=1}^m\sigma_k\right)=n-\sum_{k=1}^m\big(|\sigma_k|-1\big)$ because each cycle eats $|\sigma_k|$ elements and spits out 1 orbit. This observation turns the above statement into showing \[c(g\circ\sigma)\ge c(g)-|\sigma|+1.\]However, this is not hard because $\sigma$ only permutes $|\sigma|$ elements and so can only disrupt $|\sigma|$ orbits in $g\circ\sigma.$ This means that in $g\circ\sigma,$ $\sigma$ must leave $c(g)-|\sigma|$ of $g$'s orbits untouched, and the remaining elements must form at least 1 orbit. This is the above inequality.
BOBTHEGR8
28.03.2020 14:52
Note that we only need to show $c(f_1)+c(f_2)\leq n +c(f)$ Okay so here is a proof of a stronger fact Solution- First note that it is enough to prove for $k=2$. Let $G$ denote the group generated by $f_1,f_2$ , we will prove the result with $f_1\circ f_2$ replaced by any $f\in G$ Let $G$ act on $\{1,2,\cdots,n\}$, let the orbits be $\mathbb{O}_1,\mathbb{O}_2,\cdots,\mathbb{O}_t$ (These orbits are different than those in question) Note that when any $f\in G$ is written in cyclic notation all elements in any cycle are in same orbit. So define $c_i(f)=$number of cycles of $f$ in $\mathbb{O}_i$, where $1\leq i\leq t , f\in G$. Then we have $\displaystyle c(f)=\Sigma_{i=1}^tc_i(f)$ and $n=\Sigma_{i=1}^t|\mathbb{O}_i|$ Now note that for any $f\in G , f$ has atleast one cylcle in each orbit and so we have $c_i(f)\geq 1$ and so it is enough to prove the following more general result- Lemma- $c_i(f_1)+c_i(f_2)\leq |\mathbb{O}_i|+1$ Proof- Consider a graph with vertices as cycles of $f_1$ and $f_2$ in $\mathbb{O}_i$ and two vertices are joined if the cycles have a common element. We will show that any the graph is connected, for consider any two cycles and let there respective elements be $a$ and $b$ , as $a$ and $b$ are in same orbit we get that there is a sequence of applying $f_1$ and $f_2$ on $a$ to get $b$ , we just follow this sequence along the cycles to get the required path and hence the graph is connected. Consider a set of cycles $\{C_1,C_2,\cdots,C_m\}$ such that union of all there elements is $\mathbb{O}_i$ and for $i>1 , C_i$ is joined to $C_j$ for some $1\leq j <i$ So now we show two inequalities and combine them to get required result 1 .In worst case all cycles except the chosen ones are singleton so we have $c_i(f_1)+c_i(f_2) \geq m+2 |\mathbb{O}_i|-(|C_1|+|C_2|+\cdots+|C_m|)$ 2. For each $i>1, C_i$ contributes at most $|C_i|-1$ new elements and as their union has all elements we have $|C_1|+(|C_2|-1)+\cdots+(|C_m|-1) \geq |\mathbb{O}_i|\implies |C_1|+|C_2|+\cdots+|C_m| -m \geq |\mathbb{O}_i|-1$ Combining these two we have $c_i(f_1)+c_i(f_2)\leq |\mathbb{O}_i|+1$
Idio-logy
24.11.2020 11:15
It suffices to prove the case $k=2$, where we want $c(f) + c(g) \le n + c(gf)$. Draw the bijections as directed 2-factors on the vertex set $\{1,2,\dots,n\}$, and we say that edges of $f$ are red and edges of $g$ are blue. Then the red graph $R$ has $c(f)$ connected components $r_1, \dots, r_{c(f)}$, while the blue graph $B$ has $c(g)$ connected components. Suppose we overlap the red graph and the blue graph and call the resulting union $G$, then $G$ has at most $c(gf)$ connected components. We will prove a stronger result, namely that $c(g) \le C(G) + n - c(f)$, where $C(G)$ is the number of connected components of $G$.
Focus on some connected component $C$ of $G$, and suppose it contains the red components $r_1,r_2,\dots,r_k$.
Claim. If there are $x$ blue cycles such that the union of these cycles and $r_1,\dots,r_k$ is connected, then these cycles cover at least $k + x - 1$ distinct vertices in $C$.
Proof. Induct on $x$, the base case is trivial. For the induction step, consider a blue cycle and suppose it joins together the components $r_1,\dots,r_i$. Then it contains at least $i$ vertices. If we delete this cycle, then we must join together $k-i+1$ components with $x-1$ cycles, which costs at least $(k-i+1) + (x-1) - 1 = k-i+x-1$ distinct vertices. These vertices are all distinct from the $i$ vertices we deleted, because each vertex only have degree 2. Thus, there are at least $i+(k-i+x-1) = k+x-1$ vertices in total. $\square$
By the Claim, we have at least $x + (V(C) - (k+x-1)) = 1 + V(C) - k$ blue cycles in $C$. Summing this together for all connected components $C$ of $G$ gives the desired bound.
sriraamster
07.09.2021 01:34
can anyone let me know if this is wrong? it feels unsatisfying Rephrase the problem in terms of directed graphs. Note that $f$ can be represented as a directed graph on $n$ vertices where each vertex has indegree $1$ and outdegree $1,$ as it is a bijection. It follows that $c(f_i)$ is the number of cycles in the graph representation of $f_i.$ Therefore, from here on out, we will use the terms "function" and "graph" interchangeably. Claim: If $A$ and $B$ are directed graphs on $n$ vertices, then $c(A) + c(B) \le n + c(A \cup B).$ Proof: Suppose $E(G)$ is the number of connected components in graph $G.$ Then, $c(A) = E(A)$ and $c(B) = E(B)$ since both are the union of many disjoint cycles, which are thus the connected components of each. We will show the stronger result that $E(A) + E(B) \le n +E(A \cup B)$ from which the original follows since $c(A \cup B) \le E(A \cup B).$ Let $c(A) = a$ and $c(B) = b.$ Let $s$ be the number of times a cycle from $B$ and a cycle from $A$ share common vertices. Then, $E(A \cup B) = a + b - s.$ Then, any vertex $v \in A \cup B$ is the intersection of at most a single pair of cycles $a_i \in A$ and $b_j \in B,$ since $v$ is included in at most $1$ set in the orbit of $A,$ and similarly for $B.$ Therefore, since in order for two cycles to intersect they must share some vertex $v \in \{1, 2, 3, \dots, n \},$ we have $s \le n$ which means $E(A \cup B) \ge a + b - n.$ To finish, $E(A \cup B) \ge E(A) + E(B) - n \implies E(A \cup B) + n \ge E(A) + E(B) \iff c(A \cup B) + n \ge c(A) + c(B).$ To show the result of the problem, induct on $k.$ The base case gives the identity, so assume \[ c(f_1) + \cdots + c(f_{k-1}) \le n(k-2) + c(g) \]where $g = f_1 \circ \cdots \circ f_{k-1}.$ Then, $f = f_1 \circ \cdots \circ f_k = g \circ f_k.$ Notice that if we consider the graph of $g \circ f_k,$ each cycle in it induces a cycle in $g \cup f_k,$ since we can consider an edge in $g \circ f_k$ to be the "composition" of two edges in $g \cup f_k,$ i.e $x \to f_k(x) \to g(f_k(x))$ instead of directly going $x \to f_k(x).$ Therefore, $c(g \circ f_k) \ge c(g \cup f_k),$ and using the above claim gives \begin{align*} c(f_1) + \cdots + c(f_k) \le n(k-2) + c(g) + c(f_k) \le n(k-2) + n + c(g \cup f_k) \le n(k-1) + c(g \circ f_k) = n(k-1) + c(f) \end{align*}as desired.
mathleticguyyy
26.10.2021 04:17
Unfortunately missed the comparatively nicer solutions, but still a cool problem. When $k=1$, there is nothing to prove, so we will proceed on $k\ge 2$ with induction. Base case: $k=2$ We will induct on $n$, with the base case $n=1$ trivial. For the inductive step, if neither function has fixed points, then $c(f_1)+c(f_2)\le \frac{n}{2}+\frac{n}{2}=n<n+c(f)$. If both functions share a fixed point, then we can simply delete it and shift the functions accordingly, and both sides decrease by $2$ ($c(f_1),c(f_2),c(f),n$ each goes down by $1$). Otherwise, assume WLOG that $f_1$ has a fixed point at $n$ but $f_2$ does not. Then, we can delete $n$ entirely, and if $f_2(a)=n$ and $f_2(n)=b$, then now let $f_2(a)=b$. It's evident that we decreased the LHS by exactly $1$ because $f_2$ doesn't lose any orbits, and RHS decreases by at least $1$ because $n$ decreases. We have exhausted all possibilities, and hence the base case is complete. Grand inductive step: $c(f_1)+\ldots +c(f_{k+1})\le n(k-1)+c(f_1 \circ \dots \circ f_k)+c(f_{k+1})\le n(k-1)+n+c(f_1 \circ \dots \circ f_k\circ f_{k+1})$.
CT17
29.01.2022 21:33
Really sketchy writeup: We only need to consider the $k=2$ case, as this solves the problem by induction as shown in many above posts. Construct undirected graphs $G_1$ and $G_2$ on the same set of $n$ vertices corresponding to $f_1$ and $f_2$, respectively (where there is an edge between vertices $a$ and $b$ in $G_i$ iff $f_i(a) = b$ or $f_i(b) = a$). Let $G = G_1\cup G_2$. Note that $G_1$, $G_2$, and $G$ may contain edges connecting a point to itself, and $G$ may contain two edges between a single pair of points. Moreover, note that $G_1$ and $G_2$ are made up of disjoint cycles, each of which corresponds to an orbit in $f_1$ or $f_2$. The key observation is that the number of orbits of in $f_1\circ f_2$ is at least the number of connected components in $G$. Finally, for a graph $J$ define $e(J)$ to be the number of connected components of $J$. Consider an arbitrary connected component $H$ of $G$ with $m$ vertices and corresponding subgraphs $H_1$ and $H_2$ of $G_1$ and $G_2$, respectively. Suppose $e(H_1) = r$. Let $X$ be a set of cycles in $G_2$, of minimal size $s$, such that $X\cup G_1$ is connected. Then $\sum_{C\in X} |C| - 1\ge r-1$, so $X$ contains at least $r + s - 1$ vertices of $H_2$. In particular, $e(H_2)\le s + m - (r + s - 1)$ and hence $e(H_1) + e(H_2) \le m + 1$. Summing over all connected components $H$, we obtain $c(f_1) + c(f_2) = e(G_1) + e(G_2) \le n + e(G) \le n + c(f_1\circ f_2)$ as desired.
IAmTheHazard
13.04.2022 05:10
Weird problem. Most of this problem is just the $k=2$ case, i.e. $$c(f_1)+c(f_2) \leq n+c(f_1 \circ f_2).$$Represent $f_1,f_2$ as graphs $G_1,G_2$ respectively on $n$ vertices in the obvious way. Then $c(f)$ simply counts the number of connected components (cycles) in the corresponding graph of $f$. Let $c_1,c_2$ denote the number of connected components in $G_1,G_2$ respectively. The desired inequality is then implied by the following claim: Claim: The number of connected components in $G_1 \cup G_2$ is at least $c_1+c_2-n$. Proof: Rewrite the expression as $c_1+(n-c_2)$ with all the connected components of $G_1$ and add in one connected component of $G_2$ at a time. If we add a component $C$ with $c$ vertices at some point, any preexisting connected component which becomes joined to $C$ cannot overlap with any other (since that would imply that some connected components in either $G_1$ or $G_2$ share a vertex—this is easy to check), hence there are at most $c$ connected components which become joined to $C$. Therefore, by adding $C$ we decrease the number of connected components by at most $c-1$. Doing this for every connected component of $G_2$ decreases the number of connected components of $G_1$ by at most $n-c_2$, proving the desired inequality. Now by induction the general inequality is true, since $$c(f_1)+\cdots+c(f_k)+c(f_{k+1})\leq n(k-1)+c(f_1 \circ \cdots \circ f_k)+c(f_{k+1})\leq nk+c(f_1 \circ \cdots \circ f_{k+1}).~\blacksquare$$
Inconsistent
24.12.2022 02:31
Obviously we just need to prove the $k = 2$ case. Now notice we may express $f_1$ as $n - c(f_1)$ involutions, each of which decreases the total number of cycles by at most $1$, so the inequality $c(f_2) - c(f_1 \circ f_2) \leq n - c(f_1)$ by counting finishes immediately.
5 minute solve
megarnie
12.06.2023 23:12
\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] Note: All orbits have a finite length We induct on $k$. The main part is showing the base case $k=2$. Claim: $c(f_1) + c(f_2)\le n + c(f)$ Proof: We induct on $n$. If $n=1$, the result is obvious. Now suppose the result was true for everything less than $n$. We show it is true for $n$ by casework on the fixed points of $f_1, f_2$. Case 1: $f_1$ and $f_2$ do not have any fixed points. Then all orbits have length at least $2$, hence $c(f_1)$ and $c(f_2)$ are both at most $n/2$, which means the bound is obviously true. Case 2: $f_1$ and $f_2$ share a fixed point WLOG the fixed point is equal to $n$. Note that $f_1, f_2, f$ all have fixed points at $n$. Then we may let $g_1$, $g_2$, $g$ be from $\{1, 2, \ldots, n-1\}$ to $\{1,2, \ldots, n-1\}$ satisfying $g_1(x) = f_1 (x)$, $g_2(x) = f_2(x)$, and $g(x) = f(x) = g_1(g_2(x)) $ for $1\le x\le n-1$. Using the inductive hypothesis, we have \[c(f_1) + c(f_2) = (c(g_1) + 1) + (c(g_2) + 1) \le c(g_1) + c(g_2) + 2 \le c(g) + n + 1 = n + c(f),\]as desired. Case 3: $f_1$ has a fixed point that $f_2$ does not. WLOG again that $f_1$ has a fixed point at $n$, and let $f_2(n) = a, f_2(b) = n$. Define $g_1, g_2$ similarly to the previous case except that $g_2(b) = a$. Define $g$ from $\{1,2,\ldots, n-1\}$ to itself such that $g(x) = g_1(g_2(x))$ for all $x\in \{1,2,\ldots, n-1\}$. Notice that any cycle of $f$ not containing $n$ remains the same in $g$, and the cycle containing $n$ just changes from $\ldots \to b \to n \to f_1(a) = g_1(a) \to \ldots $ to $\ldots \to b \to g_1(a) \to \ldots$, which means that $f$ and $g$ have the same number of cycles. Additionally, $g_1$ has one less cycle than $f_1$ and $g_2$ has the same number of cycles as $f_2$. Now, using the inductive hypothesis we have \[c(f_1) + c(f_2) = c(g_1) + 1 + c(g_2) \le (n-1) + c(g) + 1 = n + c(f), \]as desired. Case 4: $f_2$ has a fixed point that $f_1$ does not. WLOG that $f_2$ has as fixed point at $n$, let $f_1(n) = c, f_1(d) = n$. Define $g_1, g_2$ similarly to case 2 except that $g_1(d) = c$. Define $g$ similarly to the previous case. Notice that any cycle of $f$ not containing $ n$ remains the same in $g$, and the cycle containing $n$ changes from $\ldots f_2^{-1}(d) \to n \to c \to \ldots $ to $\ldots g_2^{-1}(d) \to c \to \ldots $m which means that $f$ and $g$ have the same number of cycles. Additionally, $g_1$ has the same number of cycles as $f_1$, and $g_2$ has one less cycle than $f_2$. Now, using the inductive hypothesis we have \[c(f_1) + c(f_2) \le c(g_1) + c(g_2) + 1 \le (n-1) + c(g) + 1 \le n + c(f),\]as desired. We have exhausted all cases, so the induction on $n$ is complete. $\square$ Suppose the result was true for everything less than $k$. Now we have \begin{align*} c(f_1) + c(f_2) + \cdots c(f_{k-1}) + c(f_k) \\ \le n(k-2) + c(f_1 \circ f_2 \circ \cdots \circ f_{k-1}) + c(f_k) \\ \le n(k-2) + n + (f) = n(k-1) + c(f), \\ \end{align*}as desired.
HamstPan38825
10.09.2023 22:57
Lemma. [Key Lemma] For any function $f$ and permutation $\sigma$ associated with $f$, we have $c(f) + s(\sigma) = n$, where $s(\sigma)$ is the number of swaps required to turn $\sigma$ into the identity. Proof. Looking at the directed graph generated by $f$, notice that we can create at most two self-loops every swap, where equality occurs if and only if two elements map to each other under $\sigma$. In any other case we can create at most one self-loop, so the equality follows. [In more casual terms, we essentially get one free corrected element for every cycle connected to a tree in $f$.] $\blacksquare$ By induction it suffices to show that $s(\sigma_1) + s(\sigma_2) \geq s(\sigma_1 \circ \sigma_2)$. But this is clear as we can always revert $\sigma_1 \circ \sigma_2$ to the identity by reverting it to $\sigma_2$ first.
rafayaashary1
29.09.2023 23:50
What follows is not profoundly different from the arguments above, just phrased differently. Denote by \(S_{n}\) the \(n^{\text{th}}\) symmetric group and by \(\rho_{n}\colon S_{n}\to\text{GL}\left(V_{n}\right)\) the standard permutation representation of \(S_{n}\) on \(V_{n}=\mathbb{C}^{n}\). Given a subset \(F\subseteq S_{n}\), denote moreover by \(V_{n}^{F}\) the invariant subspace of the restriction of \(\rho_{n}\) to the subgroup of \(S_{n}\) generated by \(F\). The key insights are that \(\text{dim}\left(V_{n}^{\left\{f_{i}\right\}}\right)\ =\ c\left(f_{i}\right)\) and that \begin{align*} V_{n}^{\left\{f\right\}}\ &\supseteq\ V_{n}^{\left\{f_{i}\right\}_{i=1}^{k}}\\ &=\ \bigcap_{i=1}^{k} V_{n}^{\left\{f_{i}\right\}}\\ &=\ \left(\sum_{i=1}^{k} \left(V_{n}^{\left\{f_{i}\right\}}\right)^{\perp}\right)^{\perp} \end{align*}(with "\(\perp\)" the orthogonal complement). Taking dimensions then gives \begin{align*} c\left(f\right)\ &=\ \dim\left(V_{n}^{\left\{f\right\}}\right)\\ &\geq\ \dim\left(\left(\sum_{i=1}^{k} \left(V_{n}^{\left\{f_{i}\right\}}\right)^{\perp}\right)^{\perp}\right)\\ &\geq\ n\ -\ \sum_{i=1}^{k} \left(n-\dim\left(V_{n}^{\left\{f_{i}\right\}}\right)\right)\\ &=\ n\left(1-k\right)\ +\ \sum_{i=1}^{k} c\left(f_{i}\right)\text{,} \end{align*}which is clearly equivalent to the desired inequality. \(\blacksquare\)
Joider
27.11.2023 06:44
Please is there any attachments for diagnosing The problem statement py drawing the graph
thdnder
30.01.2024 15:06
By induction, we can assume $k=2$. Let $c'(f) = n - c(f)$. Then the given inequality can be rewritten as $c'(f \circ g) \le c'(f) + c'(g)$. Note that for given permutation $f$, $c'(f)$ is the number of swaps to change $f$ into the identity permutation. Since we can change $f \circ g$ into the identity permutation using exactly $c'(f) + c'(g)$ swaps (change $f$ into the identity permutation and change $g$ into the identity permutation), hence $c'(f) + c'(g) \ge c'(f+g)$. $\blacksquare$
Pyramix
16.02.2024 23:31
Note that if $f,g$ are bijective functions, with same domain and range $S$, then so is $f\circ g$. So, $f_1\circ f_2\cdots f_k$ is a bijective function. We know that for each bijective function $S\rightarrow S$, the orbits are a partition of $S$. We now prove a key claim. Key Claim: For bijective functions $f_1:S\rightarrow S$ and $f_2:S\rightarrow S$, we have \[c(f_1)+c(f_2)\leq n+c(f_1\circ f_2) \ \ \ \ (\star)\]Proof. If $c(f_1)+c(f_2)\leq n$, we are already done. Suppose $c(f_1)+c(f_2)>n$. For a function $f:S\rightarrow S$, we construct a directed $G(f)$ such that the directed edge $u\rightarrow v$ exists if and only if $v=f(u)$. Then, each orbit represents the terms of a directed cycle in $G$, and $c(f)$ represents the number of such distinct cycles. Let $\mathcal{C}_1,\mathcal{C}_2,\ldots,\mathcal{C}_{c(f_1)}$ denote the directed cycles in $G(f_1)$ and $\mathcal{C'}_1,\ldots,\mathcal{C'}_{c(f_2)}$ denote the directed cycles in $G(f_2)$. Consider a simple (undirected) graph $H$ on $c(f_1)+c(f_2)$ vertices with each vertex representing a directed cycle in either $f_1$ or $f_2$. Two vertices are connected if the corresponding cycles have at least one vertex in common. Then, $H$ is a bipartite graph as directed cycles belonging to the same directed graph are disjoint. Moreover, the degree of each vertex in $H$ is at most the size of the corresponding cycle. Claim: $c(f)$ is at least the number of connected components in $H$, where $f=f_1\circ f_2$. Proof. Let $\mathcal{K}$ be a connected component of $H$. Let $\mathcal{C'}\in G(f_2)$ be a cycle which lies in this connected component. Let $u\in\mathcal{C'}$ be an arbitrary vertex in this cycle. Suppose $u\rightarrow v$ in the cycle, i.e. $u=f_2(v)$. Since $\mathcal{K}$ is a connected component of $H$, there exists a cycle $\mathcal{C}\in G(f_1)$ such that $v\in\mathcal{C}$ and the corresponding vertex of $\mathcal{C}$ in graph $H$ lies in $\mathcal{K}$ as it is connected to the vertex of cycle $\mathcal{C'}$. So, the vertex $w=f_1(v)\in\mathcal{C}$ and $w=f_1(v)=f_1(f_2(u))=f(u)$. Hence, for the of vertices lying in the one of the cycles of $\mathcal{K}$, their image in $f$ also lies in $\mathcal{K}$. So, we get at least one cycle of $f$. The claim follows. $\blacksquare$ We now use a Lemma. Lemma. For a graph on $v$ vertices with $e$ edges, there are at least $v-e$ connected components. Proof. If $e=v-1$, the graph is a tree and there is one connected component. If $e<v$, then the graph is disconnected and there are more than one connected components. Suppose there are $k$ connected components, with each component having $v_i$ vertices and $e_i$ edges. Then, $v_i\leq e_1+1$. Summing up, we get $v=\sum_{i=1}^{k}v_i\leq k+\sum_{i=1}^{k}e_i=k+e\Rightarrow k\geq v-e$, as claimed. Equality holds when all connected components are trees. $\blacksquare$ Note that in $H$, each vertex has a degree at most the number of elements in the corresponding directed cycle. Hence, the degree sum of the vertices in $H$ corresponding for cycles $\mathcal{C}_1,\mathcal{C}_2,\ldots,\mathcal{C}_{c(f_1)}$ is at most $n$, as each cycle is disjoint. Similarly, the degree sum for vertices in $H$ corresponding for cycles $\mathcal{C}_1,\ldots,\mathcal{C}_{c(f_2)}$ is at most $n$ as well. We know, for any simple graph, the total degree sum is twice the number of edges. So, if $H$ has $e_h$ edges, then $2e_h\leq2n\Rightarrow e_h\leq n$. Moreover, the number of vertices in $H$ is exactly $c(f_1)+c(f_2)$. It follows that if there are $k_h$ connected components in $H$, then \[c(f)\geq k_h\geq c(f_1)+c(f_2)-e_h\geq c(f_1)+c(f_2)-n,\]as claimed. $\blacksquare$ We now repeatedly use inequation $(\star)$ to get the following equations: \[c(f_1)+c(f_2)\leq n+c(f_1\circ f_2),\]\[c(f_1\circ f_2)+c(f_3)\leq n+c(f_1\circ f_2\circ f_3),\]\[\vdots\]\[c(f_1\circ f_2\circ\cdots\circ f_{k-1})\leq n+c(f_1\circ f_2\circ\cdots f_k)=n+c(f).\]Adding up these $k-1$ inequations, we get the desired result. $\blacksquare$
N3bula
14.10.2024 10:43
Note that all orbits from the surjective property are disjoint. Let $k=\min(c(f_1), c(f_2), \dots, c(f_n))$, suppose that $c(f)<k$ and let $k-c(f)=i$, thus call the $k$ orbits $O_1$, $O_2$, $\ldots$, $O_k$. All these orbits are disjoint, thus if two values from $O_i$ and $O_j$ end up in the same orbit of $c(f)$ this implies that there had to be an orbit in one of the other functions that contained a value from $O_i$ and $O_j$, thus for each time we reduce $k$ be $1$ we also reduce the maximum number of functions by $1$ and as when $k$ is $1$ and the result are $n$ the inequality holds, the inequality must hold.
cj13609517288
15.11.2024 00:49
Clearly it suffices to show this for $k=2$, so we want to show \[c(f)+c(g)\le n+c(f\circ g).\]Consider the cycles for $f$ as a collection of sets $\mathcal{C}_f$ and similarly for $\mathcal{C}_g$. Take our sets $\mathcal{C}_f$ and add in $S\in\mathcal{C}_g$ one by one. If we subtract from $2n$ on both sides and define $d(f)=n-c(f)$, we want to show \[d(f)+d(g)\ge d(f\circ g).\]Note that $d$ is just the sum of "the number of things minus one" over all cycles. Thus whenever we merge some connected thing, the worst case scenario is that the RHS is still all combined, which means we added at most "number of things in $S$ minus (number of things it connected to)" things in the connected component, and removes (number of things it connected to minus one) connected components, which works out. $\blacksquare$