TITLE: Can someone provide a physical -- not mathematical -- intuition for the phase in a quantum wavefunction?
QUESTION [32 upvotes]: I've read every thread on StackExchange (and Quora and reddit...) that I can find about a physical intuition for the phase in the quantum wave function, and I still Just. Don't. Get. It. (Yes, I've seen this thread--didn't help!)
As a jumping off point, I've been watching this terrific visualization of the quantum wave function. According to this video, for a particle in an infinite square well, the "phase" will rotate in the complex plane. Okay...what does that mean physically? Let's focus on just the ground state wave function. If it's not "rotating" in real space (right?), then what exactly is changing to make the phase "rotate"? If I could "see" the wave function with my eyes, what would I see?
I understand the mathematical argument that the phase doesn't matter: the complex exponential cancels out when you calculate the probability distribution, etc.
Maybe my confusion stems from a misunderstanding of what phase even is in quantum mechanics. When I visualize phase, I think of a sine wave and how much it has been shifted to the left or right (relative to some origin). But when I watch that visualization of the ground state wave function, nothing is sliding left or right, the wave isn't going anywhere. So what information does the phase encode here? I'm clearly missing something...
As background, I'm fairly new to quantum physics. I've always wanted to understand it beyond the usual "pop sci" descriptions, so I've been following the MIT OpenCourseware lectures on quantum physics. The physical nature of this phase is just really tripping me up and I've yet to find any explanation anywhere that goes beyond "well it works out in the math." Or is that all it is: just a convenient mathematical bookkeeping trick that physicists keep around because it happens to match observations?

REPLY [1 votes]: I've been revisiting the same thing for myself right now, and stumbled upon just a great (and very short!) mathematical explanation, which made a perfect sense to me.
The even shorter explanation is this:

We must keep the total probability to be 100%  all the time.

All the time.
Physically it means that for any given initial property of a particle (say, it's orientation along physical X, or Y axis, or any other property) - we can predict whether this is going to change in any way, and calculate exact (!!) probability of that to happen.
How? We treat any property of a particle as an abstract vector, located in an abstract vector space: this vector always has a fixed length, and it can be rotated.
What?.. Why (physically) - ??
First reason is, because any physical property can exist in a number of options. Usually there's just 2: "up/down" (as in quantum spin), "clockwise/counterclockwise" (as in polarisation), etc.; but there might be many, even nearly infinite:

this, or that, or any other position of a particle on a continuous screen (say, in a double slit experiment);
this, or that, or any other position of a particle in our continuous space-time (say, on its way to a screen, or to the slits, or any other way);
this, or that, or any other orientation (axis) of a particle in our continuous space-time (say, not just "up/down", but any arbitrary - relative to former), etc.

Second, and most important reason is: these options cannot be realized simultaneously - and that's that! The vector form on itself - is just a convenient way to express such "not simultaneousness" mathematically: we merely assign to each of the 2 (or whatever) of our options its own orthogonal axis (meaning that it is perpendicular to any other axis, along which our state-vector's coordinates are defined; there, again, might be any number of axis - in a realm of mathematics), and then we just measure the length of our state-vector along these option-axis: that length (its square really, which in fact is just a pure Pythagorean theorem) would be our probability.

So, wavefunctions just live in such continuous vector spaces with many perpendicular axis, evolving (more often by rotation) among one of these "not simultaneous" axis with its phase.
Ultimately, phase is just an artifact of a wavefunction, rotating in that vector space; and the nature of this rotation purely depends on which property of a particle you've chosen to analyze: it might represent a change in space-time coordinates, or a change in spatial orientation (axis), or whatnot; therefore, a phase - is just a rate of that change.
But why do we need to express these discrete, countable options in such continuous way?
Short answer is, because it is an experimental fact: we can calculate exact (!!) probability for any arbitrary option by just knowing what option our physical system is in right now. Even if it is uncertain.
Say, if a particle is "up" right now - we can calculate and find that it is definitely (100%) going to be still "up" if we will measure it in the same "up/down" direction; but, if we will choose to measure that same "up" particle in another direction (say, "left/right", or if the particle was "uncertain") - we will find an even (50/50 - for the set with 2 options) probability.
But more often probability between 2 or more options is not even - if we were to choose an arbitrary direction of measurement; or, due to interference (like in a double slit) - which is literally wavefuncion overlapping with its own different parts.
But either way, probability must always add up to 100%.
All the time,  no matter the arbitrariness.
Again: it is just an experimental fact, which turned out to be best described in a vector space; and we need that vector space to be continuous exactly for its predictive power - not just for "up/down" or "left/right", but any arbitrary angle: that is especially clear in the case of physical orientation (axis) in space-time.
Long answer is: this is also more commonly known as Heisenberg's uncertainty principle.

EDIT: also, in my own research, there was another very common physical example for the meaning of a phase - the fact that it is somehow related to a charge of a particle:

In quantum mechanics the scalar field is equivalent to a phase shift in the wavefunction of the charged particle

It has deep physical meaning, for example as an explanation to why do particles annihilate with their antiparticles (since latter are having their phase rotating in opposite direction).
And, I do not know much else about that :) in fact, I revisited the whole thing exactly because I've been researching charges.
But, I do believe that the same argument as above still applies: something is changing as time goes on.
The fair objection then might be: if we choose our "property" freely, and a phase merely shows a change in that property, does that mean that change of any property is related to charge - ?..
Honestly, I do not know: I can bet that a change in "spatial/momentum" property might be just luckily coincident with charge; and yet, there might be other momenta that partice can have (say, angular momentum), which can have whole different set of "change rates" of its own.
But ultimately, there's a "time/energy" property relation for any particle:
$$\Delta E \Delta t \geq \frac{\hbar}{2}$$
$-$ where $E$ is a total energy: I bet, that is the right property to look at "change rates" of, if one is interested in phase-charge relation.


TITLE: Why can't you pick socks using coin flips?
QUESTION [76 upvotes]: I'm teaching myself axiomatic set theory and I'm having some trouble getting my head around the axiom of choice. I (think I) understand what the axiom says, but I don't get why it is so 'contentious', which probably means I haven't yet digested it properly.
As far as I can make out, one phrasing of the axiom is: for any family of non-empty, pairwise disjoint sets, there exists a set containing exactly one element from each set in the family.
If that's all the axiom states, why is there so much debate around it? If it were stated as there exists a procedure for constructing such a set, that might help me understand (though is that an incorrect statement of the axiom?), but then again:
To use Russell's classic shoes-and-socks example, why won't a coin flip for each pair of socks suffice?
I'm sure this must be a stupid question, but please help me understand why.

REPLY [8 votes]: Your instinct is basically correct, you can choose socks arbitrarily ("by flipping a coin") without an axiom that lets you. But only because anything you do is necessarily a finite process.
In fact the Axiom of Choice is not needed for finite sets. Various restricted forms of it are theorems of the other axioms: https://mathoverflow.net/questions/32538/finite-axiom-of-choice-how-do-you-prove-it-from-just-zf
AC is controversial when applied to transfinite sets. To over-simplify, you can think of the "controversy" as specifically being related to the fact that it's equivalent to the Well-Ordering Theorem (which my course called the Well-Ordering Principle, but apparently that's ambiguous in other contexts). Nobody ever disputed that finite and countable sets can be well-ordered, it's the rest that are tricky.
There's a joke (that doesn't entirely stand up to analysis, but does reflect the gut instincts of many), that the Axiom of Choice is obviously true, the Well-Ordering Theorem is obviously false, and Zorn's Lemma is obviously incomprehensible. They're all equivalent.

REPLY [0 votes]: May I add to Andreas Blass' answer? The axiom of choice is a statement that the set-theoretic universe contains lots of sets. In terms of your example with socks, the question is: If you have a countable number of pairwise disjoint 2-element sets does there exist a set which contains exactly one element from each of these 2-element sets. The axiom of choice says yes, such a set does exists, but there are models of set theory in which the axiom of choice fails and in which no set meets each of the 2-element sets in exactly one element.


TITLE: Finding all polynomials $p(x)$ such that $ \mathbb{Q}[x]/p(x) \simeq \mathbb{Q}(A)$ for fixed $A$ algebraic
QUESTION [2 upvotes]: As an example, if we put $F =\mathbb{Q}(\sqrt{2}, \sqrt{3}, ... , \sqrt{n})$, $F$ is the splitting field of $p(x)$ so that we can write
$$
p(x) = (x^2 - 2)(x^2 - 3)\cdots (x^2 - n).
$$
Question: if it is always true the isomorphism above (I'm not sure there is a counter-example for a general case), how can I find all polynomials $p\in\mathbb{Q}[x]$ such that $\mathbb{Q}[x]/p(x) \simeq \mathbb{Q}(A)$ for a fixed algebraic $A$ (or a series of extensions for that matter)?
Are they the [irreducible] polynomials which are multiples of $p(x)$, when $p(x)$ is such that $\mathbb{Q}(A)$ is its splitting field?

REPLY [2 votes]: By the Primitive Element Theorem, an algebraic extension $F$ of $\mathbb{Q}$ is of the form $\mathbb{Q}(\alpha)$ for some $\alpha\in\mathbb{C}$ if and only if $[F:\mathbb{Q}]$ is finite. Not all such extensions are given by splitting fields, however.
For $\alpha\in\overline{\mathbb{Q}}$, let $n=[\mathbb{Q}(\alpha)\colon\mathbb{Q}]$. Then $\mathbb{Q}[x]/(p(x))$ is isomorphic to $\mathbb{Q}(\alpha)$ if and only if $p(x)$ is irreducible over $\mathbb{Q}$, $\deg(p)=n$, and there is a root $\beta$ of $p(x)$ in $\mathbb{Q}(\alpha)$. There are going to be infinitely many such polynomials (for example, all $\beta=q_1\alpha+q_2$ with $q_1,q_2\in\mathbb{Q}$, $q_1\neq 0$ will do), and I suspect you’ll find it rather difficult to find all such polynomials. Even with something like $\mathbb{Q}(\sqrt{2},\sqrt{3})$, you have infinitely many elements of degree $4$ in that field, generally written as $q$-linear combinations of $1+\sqrt{2}$, $\sqrt{3}$, and $\sqrt{6}$.
Of course, they can all be written as $q$-linear combinations of $1$, $\alpha,\ldots,\alpha^{n-1}$ (since these elements form a basis for $\mathbb{Q}(\alpha)$ over $\mathbb{Q}$ as a vector space), but not all such combinations work.


TITLE: Special Relativity Assumption
QUESTION [0 upvotes]: In the Book "The Geometry of Minkowski spacetime" by Naber, he says we may assume the following:

Any two admissible observers agree on the temporal order of any two events on the worldline of a photon, i.e., if two such events have coordinates $(x^1, x^2, x^3, x^4)$
   and $(x^1_0, x^2_0, x^3_0, x^4_0)$ in $S$ and $(\hat{x}^1, \hat{x}^2, \hat{x}^3, \hat{x}^4)$ and $(\hat{x}^1_0, \hat{x}^2_0, \hat{x}^3_0, \hat{x}^4_0)$ in $\hat{S}$ then $x^4 - x^4_0$ and $\hat{x}^4 - \hat{x}^4_0$ have the same sign.

i.e. that two observers agree upon the ordering of events in spacetime. Why is he making this assumption? Isn't the whole point of SR to say that simultaneity is relative?

REPLY [0 votes]: For completeness [especially for those without easy access to the reference], it might be good to include the other assumptions.

Each admissible observer presides over a 3-dimensional, right-handed,
Cartesian spatial coordinate system based on an agreed unit of length
and relative to which photons propagate rectilinearly in any direction.
Each admissible observer is provided with an ideal standard clock based
on an agreed unit of time with which to provide a quantitative temporal
order to the events on his worldline.
For each admissible observer the speed of light in vacuo as determined
by the Fizeau procedure is independent of when the experiment is performed,
the arrangement of the apparatus (i.e., the choice of P), the
frequency (energy) of the signal and, moreover, has the same numerical
value c (approximately $3.0 \times 10^8$ meters per second) for all such
observers.
"causality assumption": Any two admissible observers agree on the temporal order of any two events on the worldline of a photon, i.e., if two such events have coordinates $(x^1, x^2, x^3, x^4)$ and
$(x^1_0, x^2_0, x^3_0, x^4_0)$
in S and $(\hat x^1, \hat x^2, \hat x^3, \hat x^4 )$ and
$(\hat x^1_0, \hat x^2_0, \hat x^3_0, \hat x^4_0 )$ in $\hat S$,
then $x^4 − x^4_0$ and $\hat x^4 − \hat x^4_0$ have the same sign.
The Relativity Principle: All admissible frames of reference are completely
equivalent for the formulation of the laws of physics.

The causality assumption seems to be a requirement that observers agree on the same sense of "future" [for lightlike related events]. (Temporal-inversions are excluded.) Furthermore, he uses this to define "causal automorphism" as used in the Zeeman theorem, which Naber discusses later on that page and in the rest of the book.


TITLE: Are the following statements true or false?
QUESTION [0 upvotes]: Let $S$ be the set of vectors $\left\{ \left( 3,1,0\right), \left( -1,0,0\right) \right\}$ in $\mathbb{R}^{3}$. Let $T$ be the set of vectors which are orthogonal to some vectors in $S$, and $U$ be the set of vectors which are orthogonal to all vectors in $S$. Which are true or false ?
(a) $S$ is a subspace of $\mathbb{R}^{3}$
(b) $T$ is a subspace of $\mathbb{R}^{3}$
(c) $U$ is a subspace of $\mathbb{R}^{3}$
(d) $T$ is spanning set for $\mathbb{R}^{3}$
I understand the definitions of spanning, orthogonal and subspace, but I am having difficulty applying it to these True or False questions.

REPLY [2 votes]: For (a): does $S$ contain $(0,0,0)$? All subspaces must contain this vector.
For (b): Note that $(1,-3,1)$ and $(0,3,0)$ are both elements of $T$. Is their sum $(1,0,1)\in T$?
For (c): Clearly, $(0,0,0)\in U$. Suppose $(a,b,c),(x,y,z)\in U$. Then,
$$
(a+x,b+y,c+z)\cdot (3,1,0)=(a,b,c)\cdot(3,1,0)+(x,y,z)\cdot(3,1,0)=0+0=0.
$$
Similarly, $(a+x,b+y,c+z)\cdot(-1,0,0)=0$. Thus, $(a,b,c)+(x,y,z)$. See if you can show that $\lambda(a,b,c)\in U$ for all $\lambda\in \mathbb{R}$ as well.
For (d): Note that $\{(1,0,0),(0,1,0),(0,0,1)\}\subset T$. What does this tell you?


text:
We are interested in symmetries of rather different types, e.g. Lie
algebra actions or group actions. Hence we would like to consider
symmetries of high generality. To achieve this, we implement the
notion of symmetry as \emph{Hopf algebras}.

Recall that a Hopf algebra is an algebra which has a compatible
coalgebra structure, where the unit has an inverse with respect to the
convolution product, the antipode. We will denote the algebra
multiplication by $\mu$, the unit by $\id$, the comultiplication by
$\Delta$, the counit by $\counit$ and the antipode by $S$. We will use
Sweedler notation
\begin{equation}
    \label{eq:SweedlerNotation}
    \Delta(h) = h_{(1)} \tensor h_{(2)}
\end{equation}
to denote comultiplication.

In this section we investigate how Hopf algebras can be interpreted as
symmetries. The classical way of thinking about symmetries is that of
an action. By an action we take a point of e.g.\ an algebra and move
it under the influence of an element of the Hopf algebra. But we could
consider the dual situation, i.e. that of a coaction of a Hopf
algebra, aswell. Here one is interested in how a point of a coalgebra
can be reached by elements of a Hopf algebra or more figurative, how
an element of a coalgebra decays.

Unlike in many parts of the literature, where one considers only
module or comodule structures of a Hopf algebra as action or coaction,
respectively, we want to keep track of the additional structures
appearing in a Hopf algebra. That is instead of only a module we would
consider additionally some flatness condition on it, which ensures
compatibility with the comultiplication. And instead of only a
comodule we consider some coflatness condition, which ensures
compatibility with the product of the Hopf algebra. The terms flat and
coflat are not to be considered in the categorical sense, but instead
should be thought of as coming from differential geometry, where one
considers \emph{flat connections}, i.e. those giving rise to flat
bundles. Thanks to the Serre-Swan theorem, flat bundles correspond to
flat modules. Hence the flatness conditions ensures that we can lift
the action to the Morita modules. Analogously the coflatness
conditions ensures that we have coflat modules, i.e.\ we can lift the
coaction to Morita-Takeuchi comodules.

The structure of this section is as follows. First we define the
notion of a Hopf coaction, give some examples and clarify the notion
of coinvariants. Then we will study the corresponding
\emph{cocharacter groups}, which are the analogue to character groups
of actions. We show how one can associate a Lie algebra of
coderivations to the cocharacter groups. Finally we include the
cocharacter groups in the bigger context of a cohomology theory for
Hopf algebras.

\subsection{Coactions of Hopf algebras}
\label{subsec:HopfCoaction}

In this subsection we investigate the notion dual to that of an
action, i.e.\ the notion of coactions. These coactions describe how an
element of a coalgebra decays. We first state the definition, which at
first glance might look a bit messy, but afterwards the definition is
clarified by an extended version of Sweedler notation. The axioms are
just the categorical duals of that of an action. We use the flip
morphism $\tau$ with permutation in the superscript, indicating the
elements which are switched.
\begin{definition}[Hopf coaction]
    \label{definition:HopfCoaction}
    Let $C$ be a coalgebra and $H$ a Hopf algebra. A (right) coaction of $H$
    on $C$ is a linear map $\coacts \colon C \to C \tensor H$ which
    satisfies the following axioms:
    \begin{definitionlist}
        \item \label{item:CoactionsIsComodule}
        $C$ is a $H$-comodule via $\coacts$, i.e.\ we have
        \begin{equation}
            \label{eq:CoactionCompatibleWithComultiplication}
            (\coacts \tensor \id) \circ \coacts
            = (\id \tensor \Delta_H) \circ \coacts
        \end{equation}
        and
        \begin{equation}
            \label{eq:CoactionCounitary}
            c \tensor 1 = (\id \tensor \counit)(\coacts c)
        \end{equation}
        for all $c \in C$.
        \item \label{item:CoactionIsCoflat}
        The coaction $\coacts$ is coflat, i.e. we have
        \begin{equation}
            \label{eq:CoactionCoflatnessCompatibleProduct}
            (\id \tensor \mu) \circ \tau^{(2 3)} \circ (\coacts \tensor
            \coacts) \circ \Delta_C
            = (\Delta_C \tensor \id) \circ \coacts
        \end{equation}
        and
        \begin{equation}
            \label{eq:CoactionCoflatnessCounitarity}
            (\counit_C \tensor \counit_H)(\coacts(c))
            = \counit_C(c) \tensor 1
        \end{equation}
        for $c \in C$.
    \end{definitionlist}
\end{definition}
The definition of a left coaction is completely analogously.
\begin{remark}
    \label{remark:ExtendingSweedlerNotationToCoaction}
    The equations stated in Definition~\ref{definition:HopfCoaction}
    are very abstract. Hence we would like to concretize them using
    Sweedler notation. However we are dealing with different types of
    comultiplications and corepresentations and later we would like to
    have a good notation for coactions on comodules, aswell. A way to
    solve this issue is the following. We extend the sumless Sweedler
    notation as follows: for $c \in C$ and a coaction $\coacts$ one
    denotes the elements coming from the coaction by \emph{upper}
    indices, i.e. one writes
    \begin{equation}
        \label{eq:ExtendedSweedlerNotationForCoaction}
        \coacts c = c^{(0)} \tensor c^{(1)},
    \end{equation}
    the zero being reserved for elements of the coalgebra.
    Then the axioms of Definition~\ref{definition:HopfCoaction} can be
    stated as follows. For $c \in C$ we have for part
    \refitem{item:CoactionsIsComodule}
    \begin{equation}
        \label{eq:SweedlerCoactionCompatibleWithComultiplication}
        c^{(0)} \tensor c^{(1)} \tensor c^{(2)}
        = c^{(0)} \tensor (c^{(1)})_{(1)} \tensor (c^{(1)})_{(2)},
    \end{equation}
    which allows us to always write the comultiplication of $H$ in the upper
    indices, and
    \begin{equation}
        \label{eq:SweedlerCoactionCounitary}
        c \tensor 1 = c^{(0)} \tensor \counit(c^{(1)}),
    \end{equation}
    and for the second part one has
    \begin{equation}
        \label{eq:SweedlerCoactionCoflatnessCompatibleProduct}
        c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor c_{(1)}^{(1)}
        c_{(2)}^{(1)}
        = c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor c^{(1)}
    \end{equation}
    and
    \begin{equation}
        \label{eq:SweedlerCoactionCoflatnessCounitarity}
        \counit(c^{(0)}) \tensor \counit(c^{(1)})
        = \counit(c) \tensor 1.
    \end{equation}
    The axioms ensure the notation is valid, as the ambiguity of which
    comultiplication is used in
    \eqref{eq:SweedlerCoactionCoflatnessCompatibleProduct} disappears
    thanks to
    \eqref{eq:SweedlerCoactionCompatibleWithComultiplication}.
\end{remark}
We give some examples.
\begin{example}
    \label{example:Coactions}
    \begin{examplelist}
        \item \label{item:TrivialCoaction}
        The trivial coaction is given by simply tensorizing with $1$,
        i.e. if $C$ is a coalgebra and $H$ any Hopf algebra then the
        trivial coaction of $H$ on $C$ is given by
        \begin{equation}
            \label{eq:TrivialCoaction}
            \coacts(c) = c \tensor 1
        \end{equation}
        for all $c \in C$.
        \item \label{item:GradingCoaction}
        Let $H = RG$ be a group Hopf algebra and let $C =
        \bigoplus_{g \in G} C_g$ be a $G$-graded coalgebra. Then the
        grading coaction of $H$ on $C$ is given by
        \begin{equation}
            \label{eq:GradingCoaction}
            \coacts c = c \tensor g
        \end{equation}
        for $c \in C_g$.
        \item \label{item:AdjointCoaction} Let $H$ be a Hopf algebra.
        Considering the underlying coalgebra we can investigate the
        adjoint coaction of $H$ on itself. The adjoint coaction is
        given by
        \begin{equation}
            \label{eq:AdjointCoaction}
            \coacts h = h_{(2)} \tensor S(h_{(1)}) h_{(3)}
        \end{equation}
        for all $h \in H$. For $H$ being a group Hopf algebra this is
        again the trivial coaction, since then
        $\coacts(h) = h \tensor h^{-1} h = h \tensor 1$. This holds
        for every cocommutative Hopf algebra aswell, since one has
        $\coacts(h) = h_{(2)} \tensor S(h_{(1)}) h_{(3)} = h_{(1)}
        \tensor \counit(h_{(2)}) = h \tensor 1$. For Sweedler's Hopf
        algebra
        $H_4 = R\gen{1,g,x,gx \; | \; g^2 = 1, x^2 = 0, xg = - gx}$ one
        gets $\coacts g = g \tensor 1$,
        $\coacts x = 1 \tensor xg + x \tensor g + g \tensor gx$, and
        $\coacts xg = g \tensor gx + gx \tensor g + 1 \tensor xg$.
        \item \label{item:InnerCoaction}
        One can consider an inner coaction, i.e. if we have an Hopf
        algebra $H$, a coalgebra $C$ and a coalgebra homomorphism $J
        \colon C \to H$ then the inner coaction is given by
        \begin{equation}
            \label{eq:InnerCoaction}
            \coacts c = c_{(2)} \tensor S(J(c_{1})) J(c_{(3)})
        \end{equation}
        for all $c \in C$.
    \end{examplelist}
\end{example}
As always we need a corresponding notions of morphisms, so we define
equivariant coalgebra morphisms:
\begin{definition}[$H$-equivariant coalgebra homomorphism]
    \label{definition:CoactionEquivariantMorphisms}
    Let $H$ be a Hopf algebra coacting on the coalgebras $C$ and $D$.
    A coalgebra homomorphism $\Phi \colon C \to D$ is called
    $H$-equivariant if
    \begin{equation}
        \label{eq:CoactionEquivariantMorphisms}
        \phi(c^{(0)}) \tensor c^{(1)} = \phi(c)^{(0)} \tensor
        \phi(c)^{(1)}
    \end{equation}
    for all $c \in C$.
\end{definition}
Analogously to the invariants of an action one defines the
coinvariants of a coaction as those elements which are affected by the
coaction like under the trivial coaction.
\begin{definition}[Coaction coinvariants]
    \label{definition:CoinvariantsOfCoaction}
    Let $C$ be a coalgebra with coaction $\coacts$ of $H$. The set of
    coinvariants is denoted by
    \begin{equation}
        \label{eq:CoinvariantsOfCoaction}
        C^{\co H} = \{c \in C \; | \; \coacts(c) = c \tensor 1 \}.
    \end{equation}
\end{definition}
From the definition we can deduce a formula for the coaction
interacting with the antipode of the Hopf algebra.
\begin{lemma}
    \label{lemma:AntipodeAndCoaction}
    Let $C$ be a coalgebra carrying a coaction of a Hopf algebra $H$.
    Then
    \begin{equation}
        \label{eq:AntipodeAndCoaction}
        c_{(1)} \tensor c_{(2)}^{(0)} \tensor c_{(2)}^{(1)}
        = c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor S(c_{(1)}^{(1)})
          c^{(1)}
    \end{equation}
    and
    \begin{equation}
        \label{eq:AntipodeAndCoactionSecond}
        c_{(1)}^{(0)} \tensor c_{(2)} \tensor c_{(1)}^{(1)}
        = c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor c^{(1)}
          S(c_{(2)}^{(1)})
    \end{equation}
    hold for all $c \in C$.
\end{lemma}
\begin{proof}
    This follows by the following calculation
    \begin{align*}
        c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor S(c_{(1)}^{(1)})
        c^{(1)}
        &\stackrel{(*)}{=} c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor
           S(c_{(1)}^{(1)}) c_{(1)}^{(1)} c_{(2)}^{(1)} \\
        &= c_{(1)}^{(0)} \tensor c_{(2)}^{(0)} \tensor
           \counit(c_{(1)}^{(1)}) c_{(2)}^{(1)} \\
        &= c_{(1)} \tensor c_{(2)}^{(0)} \tensor c_{(2)}^{(1)},
    \end{align*}
    where we used counitarity, the properties of the antipode and in
    ($*$) the compatibility with the Hopf
    product~\eqref{eq:SweedlerCoactionCoflatnessCompatibleProduct}.
    The second equation follows completely analogously.
\end{proof}

config: arxiv


text:
\begin{document}

 \onehalfspace

\shortdate
\yyyymmdddate
\settimeformat{ampmtime}
\date{\today, \currenttime}
\footskip=28pt

\begin{abstract}
  We prove that for any $t\ge 3$ there exist constants $c>0$ and~$n_0$
  such that any $d$-regular $n$-vertex graph~$G$ with
  $t\mid n\geq n_0$ and second largest eigenvalue in absolute
  value~$\lambda$ satisfying $\lambda\le c d^{t}/n^{t-1}$ contains a
  $K_t$-factor, that is, vertex-disjoint copies of $K_t$ covering
  every vertex of~$G$.
\end{abstract}

\maketitle

\section{Introduction}
An $(n,d,\lambda)$-graph is an $n$-vertex $d$-regular graph whose
second largest eigenvalue in absolute value is at most~$\lambda$.
These graphs are central objects in extremal, random and algebraic
graph theory. The interest in these graphs lies in the fact that
various pseudorandom properties can be inferred from the value of
$\lambda$, in terms of the other parameters. For example, if
$\lambda \ll d$ then such a graph has the property that its edges are
`distributed' uniformly, which is one of the essential properties
exploited in random graphs and the regularity method from extremal
graph theory. More precisely, the following inequality, called the
\emph{expander mixing lemma} (see e.g.~\cite{AC88}), makes this
quantitative:
\begin{equation}
  \label{eq:EML.1}
  \left|e(A,B)-{d\over n}|A||B|\right|<\lambda\sqrt{|A||B|},
\end{equation}
whenever~$A$ and~$B$ are vertex subsets of an
$(n,d,\lambda)$-graph~$G$, where~$e(A,B)$ denotes the number of edges
between~$A$ and~$B$ (edges in $A\cap B$ are counted twice).  An
excellent introduction to the study of $(n,d,\lambda)$-graphs is given
in a survey of Krivelevich and Sudakov~\cite{KS06}.  The emphasis
there and throughout the field is on the interplay between the
parameters~$n$, $d$ and~$\lambda$ and graph properties of interest;
more precisely, given some property, one wishes to establish best
possible conditions on~$n$, $d$ and~$\lambda$ that ensure that any
$(n,d,\lambda)$-graph with parameters satisfying such conditions has
the property.

In this note we will only be concerned with conditions on the
parameters~$n$, $d$ and~$\lambda$ that guarantee the existence of
certain spanning structures, i.e., subgraphs that occupy the whole
vertex set (and have minimum degree at least one). Thus, we will be
somewhat selective in our discussion. In particular, we are interested
in whether, for some fixed~$t\geq 3$, our $(n,d,\lambda)$-graph
contains a family of vertex-disjoint copies of~$K_t$ covering each
vertex exactly once, which we call a
\textit{$K_t$-factor}.\footnote{This is also sometimes called a
  \textit{perfect $K_t$-matching} or a \textit{perfect $K_t$-tiling}
  in the literature.}  We remark that the case $d=\Theta(n)$ is
well-understood since the existence of bounded degree spanning graphs
in $(n,d,\lambda)$-graphs follows from the celebrated Blow-up lemma of
Koml\'os, S\'ark\"ozy and Szemer\'edi~\cite{KSS_bl}; see the
discussion in e.g.~\cite{HKP18a}.  Moreover, a sparse blow-up lemma
for subgraphs of $(n,d,\lambda)$-graphs~\cite{ABHKP16} gives general
nontrivial conditions for the existence of a given bounded degree
spanning subgraph in the case~$d=o(n)$.  These conditions are stronger
than those discussed in what follows (and hence, as expected, the
general results in~\cite{ABHKP16} are weaker than the ones below).

While extremal and random graph theory provide tools to answer
questions in this line of research positively, one is naturally
interested in the asymptotic tightness of the obtained results.  This
requires constructions of special pseudorandom graphs, most of the
known examples of which come from algebraic graph theory or geometry.
For our study here, there is essentially one prime example of such a
construction, due to Alon~\cite{Alon94}, who gave $K_3$-free
$(n,d,\lambda)$-graphs with $d=\Theta(n^{2/3})$ and
$\lambda=\Theta(n^{1/3})$.  Krivelevich, Sudakov and
Szab\'o~\cite{KSS04} then extended these to the whole possible range
of $d=d(n)$, constructing $K_3$-free $(n,d,\lambda)$-graphs with
$\lambda=\Theta(d^2/n)$.  Alon's construction is an important
milestone in the study of $(n,d,\lambda)$-graphs.  It provides a rare
example of something that is reminiscent of threshold phenomena in
random graphs in the context of $(n,d,\lambda)$-graphs: if
$\lambda\le 0.1 d^2/n$, then any vertex of an $(n,d,\lambda)$-graph is
contained in a copy of $K_3$, while there are $K_3$-free
$(n,d,\lambda)$-graphs with $\lambda=\Omega(d^2/n)$.  Even more is
true: as proved by Krivelevich, Sudakov and Szab\'o~\cite{KSS04},
$(n,d,\lambda)$-graphs with $\lambda\le 0.1 d^2/n$ contain a
fractional triangle-factor.\footnote{A fractional $K_t$-factor in a
  graph $G$ is a function $f:\cK_t\to\mathbb{R}_+$, where $\cK_t$ is
  the set of copies of $K_t$ in $G$, such that
  $\sum_{v\in K\in \cK_t}f(K)=1$ for all $v\in V(G)$.}  A natural
conjecture from the same authors~\cite{KSS04} states the following.

\begin{conjecture}[Conjecture~7.1 in~\cite{KSS04}]
  \label{conj:KSS}
  There exists an absolute constant $c>0$ such that every
  $(n,d,\lambda)$-graph~$G$ on $n\in 3\mathbb{N}$ vertices with
  $\lambda\le cd^2/n$ has a triangle-factor.
\end{conjecture}

The first result in this direction was given by Krivelevich, Sudakov
and Szab\'o~\cite{KSS04}, who proved that it suffices to impose
$\lambda\leq cd^3/(n^2\log n)$ for some absolute constant~$c>0$.  This
was improved by Allen, B\"ottcher, H\`an and two of the current
authors~\cite{ABHKP17} to $\lambda\leq cd^{5/2}/n^{3/2}$ for
some~$c>0$.  In fact, the result in~\cite{ABHKP17} is that this
condition on~$\lambda$ is enough to guarantee the appearance of
squares of Hamilton cycles (the square of a Hamilton cycle is obtained
by connecting distinct vertices at distance at most~$2$ in the cycle).
Another piece of evidence in support of Conjecture~\ref{conj:KSS} is a
result in~\cite{HKP18a, HKP18b} that states that, under the condition
$\lambda\le (1/600) d^2/n$, any $(n,d,\lambda)$-graph~$G$ with~$n$
sufficiently large contains a `near-perfect $K_3$-factor'; in fact,
$G$~contains a family of vertex-disjoint copies of $K_3$ covering all
but at most $n^{647/648}$ vertices of~$G$.  Very recently,
Nenadov~\cite{Nen18} proved that $\lambda\leq cd^2/(n\log n)$ for some
constant~$c>0$ yields a $K_3$-factor.\footnote{Nenadov studied a
  larger class of graphs, namely, the class of bijumbled graphs with
  sufficient minimum degree.  This class contains
  $(n,d,\lambda)$-graphs as a special case.  For details, see concluding
  remarks at the end of this note.}

With regard to $K_t$-factors for general $t\in \mathbb{N}$,
Krivelevich, Sudakov and Szab\'o~\cite{KSS04} remark that the
condition $\lambda\le cd^{t-1}/n^{t-2}$ yields, for appropriate
$c=c(t)$, a fractional $K_t$-factor.  Although there is, alas, no
known suitable generalization of Alon's construction to $K_t$-free
graphs, this condition on~$\lambda$ may be seen as a benchmark in the
study of $K_t$-factors in $(n,d,\lambda)$-graphs.  The first
nontrivial result for this study was the result in~\cite{ABHKP17}
showing that $\lambda\leq cd^{3t/2}n^{1-3t/2}$ for some~$c=c(t)>0$ is
sufficient to guarantee $t$-powers of Hamilton cycles (and thus
$K_{t+1}$-factors when $(t+1)\mid n$).  The aforementioned result of
Nenadov~\cite{Nen18} generalizes to $K_t$-factors~\cite{Nen18}, giving
the condition $\lambda\leq cd^{t-1}/(n^{t-2}\log n)$ for some
constant~$c=c(t)>0$.  The purpose of this note is to present a proof
that, under the condition $\lambda\leq cd^t/n^{t-1}$ for some
suitable~$c=c(t)>0$, any $(n,d,\lambda)$-graph contains a
$K_t$-factor.  More precisely, we prove the following.

\begin{theorem}
  \label{thm:main}
  Given an integer $t\ge 3$, there exist $c>0$ and $n_0>0$ such
  that every $(n, d, \lambda)$-graph~$G$ with $n\ge n_0$ and
  $\lambda \le c d^t/n^{t-1}$ contains a $K_t$-factor.
\end{theorem}

If~$d\geq cn/\log n$ for some suitable~$c=c(t)>0$ and~$t\geq4$, then
the condition in Theorem~\ref{thm:main} is the weakest that is
currently known to imply the existence of $K_t$-factors.
Theorem~\ref{thm:main}, first announced in~\cite{HKP18a}, was obtained
independently of Nenadov's result.  There are however similarities in
both approaches, since they both use absorption techniques.  However,
the structures and arguments that are used are different and Nenadov's
method is more effective in the more interesting sparse range.

We use standard notation from graph theory, see e.g.~\cite{West}. We
will omit floor and ceiling signs in order not to clutter the
arguments.

\section{Tools}

\subsection{Properties of $(n,d,\lambda)$-graphs}
We begin by giving some basic properties of $(n,d,\lambda)$-graphs.
Some of these are well known and used throughout the study of
$(n,d,\lambda)$-graphs whilst others are specifically catered to our
purposes here.

\begin{theorem}[Expander mixing lemma~\cite{AC88}]
  \label{thm:EML}
  If $G$ is an $(n,d,\lambda)$-graph and $A$, $B\subseteq V(G)$, then
  \begin{equation}
    \label{eq:EML}
    \left|e(A,B)-\frac dn|A||B|\right|<\lambda\sqrt{|A||B|}.
  \end{equation}
\end{theorem}

\begin{proposition}[Proposition~2.3
  in~\cite{KSS04}]\label{prop:lambda}
  Let $G$ be an $(n,d,\lambda)$-graph with~$d\le n/2$.  Then
  $\lambda\ge \sqrt{d/2}$.
\end{proposition}

\begin{fact}
  \label{fact:d_bound}
  Let $G$ be an $(n,d,\lambda)$-graph with $d\le n/2$.  Suppose
  $\lambda\le d^t/n^{t-1}$ for some $t\ge2$.  Then
  $d\ge n^{1-1/(2t-1)}/2$.
\end{fact}
\begin{proof}
  Proposition~\ref{prop:lambda} tells us that $\lambda\ge \sqrt{d/2}$.
  Thus $\lambda\le d^t/n^{t-1}$ implies that
  $d^{2t-1}\ge n^{2t-2}/2$, whence
  $d\ge n^{1-1/(2t-1)}/2^{1/{(2t-1)}}$ follows.
\end{proof}

\begin{fact}\label{fact:irregular}
  Let $G$ be an $(n,d,\lambda)$-graph with
  $\lambda \le \eps d^{t}/n^{t-1}$. If $U$ is a set of
  $m'\ge d/2$ vertices, then there are at most $\eps d$ vertices $u$
  with $|N_G(u)\cap U| < d m'/(2n)$.
\end{fact}
\begin{proof}
  Let $U'$ be the set of vertices $u$ such that
  $|N_G(u)\cap U| < d m'/(2n)$. By Theorem~\ref{thm:EML}, we have
  \[
    \frac dn m' |U'| - \lambda \sqrt{ m' |U'| } < e(U, U') < |U'|
    \frac{d m'}{2n}.
  \]
  Together with $\lambda \le \eps d^{t}/n^{t-1}$, we obtain that
  $|U'|\le 8\eps^2 d^{2t-3}/n^{2t-4}\le \eps d$.
\end{proof}

Write $\Ktm$ for the graph obtained by replacing one vertex of~$K_t$
by an independent set of size~$40$.

\begin{fact}
  \label{fact:cliquecount}
  Let $G$ be an $(n, d, \lambda)$-graph with
  $\lambda \le cd^{t}/n^{t-1}$ and suppose
  $cd^{t}/n^{t-1}\ge40$.  Then any set of $2^tcd$
  vertices spans a copy of~$\Ktm$.  Moreover, any set of
  $2^{t-1}cd^2/n$ vertices spans a copy of~$K_{t-1}$.
\end{fact}
\begin{proof}
  Let $U$ be a set of at least $2cd^{t-1}/n^{t-2}$ vertices in~$G$.
  Since $\lambda \le cd^{t}/n^{t-1}\le d|U|/(2n)$, it follows
  from Theorem~\ref{thm:EML} that
  \[
    2e(U)\ge\frac dn|U|^2 -\lambda|U|\ge|U|\cdot \frac{d|U|}{2n},
  \]
  which implies that~$U$ contains a vertex with degree at
  least~$d|U|/(2n)$.

  Thus, given a set of $2^tcd$ vertices, we can iteratively pick
  vertices with large degree in the common neighborhood, and get a
  $(t-1)$-clique whose common neighborhood has size at least
  $2^tcd\cdot(d/(2n))^{t-1} = 2cd^{t}/n^{t-1} \ge 40$ (the
  smallest set from which we pick a vertex in this process has size
  $4cd^{t-1}/n^{t-2}$).  Therefore, we obtain a copy of~$\Ktm$.  The
  proof of the `moreover'-part is analogous.
\end{proof}

\subsection{Templates and absorbing structures}

A \emph{template} $T$ with \emph{flexibility} $m\in \mathbb{N}$ is a
bipartite graph on $7m$ vertices with vertex parts $X$ and
$Z_1\cup Z_2$, such that $|X|=3m$, $|Z_1|=|Z_2|=2m$, and for any
$\bar{Z}\subset Z_1$, with $|\bar{Z}|=m$, the induced graph
$T[V(T)\setminus\bar{Z}]$ has a perfect matching. We call $Z_1$ the
\textit{flexible} set of vertices for the template. Montgomery first
introduced the use of such templates when applying the absorbing
method in his work on spanning trees in random graphs~\cite{M14a}.
There, he used a sparse template of maximum degree~$40$, which we will
also use.  It is not difficult to prove the existence of such
templates for large enough~$m$ probabilistically; see
e.g.~\cite[Lemma~2.8]{M14a}. The use of a sparse template as part of
the absorbing method was also applied by Kwan in \cite{Kwan16}, where
he generalized the notion to $3$-uniform hypergraphs in order to study
random Steiner triple systems, and by Ferber and Nenadov~\cite{FN17}
in their work on the universality of random graphs.

Here, we will use a sparse template to build an absorbing structure
suitable for our purposes. The absorbing structure we will use is
defined as follows.  Let $m$ be a sufficiently large integer.  Let
$T=(X, Z_1\cup Z_2, E)$ be the bipartite template with flexibility
$m$, maximum degree $\Delta(T)\leq 40$ and flexible set $Z_1$.  Write
$X=\{x_1,\dots, x_{3m}\}$, $Z_1=\{z_1,\dots, z_{2m}\}$,
$Z_2=\{z_{2m+1}, \dots, z_{4m}\}$ and define $Z:=Z_1\cup Z_2$. An
\emph{absorbing structure} $(T, \cK, A, \cS, Z, Z_1)$ with
flexibility~$m$ contains two sets $\cK$ and $\cS$ consisting of
vertex-disjoint $(t-1)$-cliques and two vertex sets $A$ and $Z$ such
that $V(\cK)$, $V(\cS)$, $A$ and $Z$ are pairwise disjoint.
Furthermore, with the labelling $\cK:=\{K^1, K^2, \dots, K^{3m}\}$,
$A=\{a_{ij}: x_i z_j\in E(T)\}$ and
$\cS=\{S_{ij}: x_i z_j\in E(T)\}$, the following holds.  For all $i$
and~$j$ such that $x_i z_j\in E(T)$,
\begin{itemize}
\item each $\{a_{ij}\}\cup K^{i}$ spans a copy of $K_t$,
\item each $\{a_{ij}\}\cup S_{ij}$ spans a copy of $K_t$, and
\item each $\{z_{j}\}\cup S_{ij}$ spans a copy of $K_t$.
\end{itemize}

\begin{fact}
  The absorbing structure $(T, \cK, A, \cS, Z, Z_1)$ has the property
  that, for any subset $\bar Z\subseteq Z_1$ with $|\bar Z|=m$, the
  removal of $\bar Z$ leaves a graph with a $K_t$-factor.
\end{fact}
\begin{proof}
  By the property of the template $T=(X, Z_1\cup Z_2, E)$, there is a
  perfect matching~$M$ in~$T$ that covers~$X$ and $Z\setminus \bar Z$.
  Then for each edge $x_i z_j\in M$, we take the $t$-cliques on
  $\{a_{ij}\}\cup K^{i}$ and $\{z_{j}\}\cup S_{ij}$; for the
  pairs~$\{i,j\}$ such that $x_i z_j\in E(T)\setminus M$, we take the
  $t$-cliques on $\{a_{ij}\}\cup S_{ij}$.  This gives the desired
  $K_t$-factor.
\end{proof}

The following lemma asserts that $(n,d,\lambda)$-graphs possess
the absorbing structures above.

\begin{lemma}
  \label{lem:1}
  There exists $\eps_0>0$ such that for all $\eps\in (0,\eps_0)$ there
  is an $n_0\in \mathbb{N}$ such that the following holds for all
  $n\ge n_0$.  Let~$G$ be an $(n, d, \lambda)$-graph with
  $\lambda \le \eps d^{t}/n^{t-1}$ and suppose $m=\eps d$.  Then there
  exists an absorbing structure $(T, \cK, A, \cS, Z, Z_1)$ with
  flexibility~$m$ such that, for any vertex~$v$ in~$G$, we have
  $\deg(v, Z_1) \ge d|Z_1|/(2n)$.
\end{lemma}

The following concentration result will be used in the proof of Lemma~\ref{lem:1}

\begin{lemma}[Lemma~2.2 in~\cite{ABHKP16}]
  \label{lem:coupling} Let $\Omega$ be a finite probability space and
  let $\cF_0\subseteq \dots\subseteq \cF_n$ be a filtration on
  $\Omega$.  For each $i\in[n]$ let $Y_i$ be a Bernoulli random
  variable on $\Omega$ that is constant on each atom of~$\cF_i$, that
  is, let $Y_i$ be $\cF_i$-measurable.  Furthermore, let~$p_i$ be a
  real-valued $\cF_{i-1}$-measurable random variable on~$\Omega$.
  Let~$x$ and~$\delta$ be a real numbers with $\delta\in(0,3/2)$, and
  let $X=Y_1+\dots+Y_n$.  If $\sum_{i=1}^n p_i\ge x$ holds almost
  surely and $\EE [Y_i\mid\cF_{i-1}]\ge p_i$ holds almost surely for
  all $i\in[n]$, then
  \[\Pr\big(X<(1-\delta)x \big)<e^{-\delta^2 x/3}\,.\]
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem:1}]
  First we choose $\eps_0=1/(300t)$ and let $\eps\in(0,\eps_0)$. Then
  we take $n_0$ large enough.

  Let $T=(X, Z_1\cup Z_2, E)$ be a bipartite template with
  flexibility~$m$ and flexible set $Z_1$ such that $\Delta(T)\le 40$.
  Pick an arbitrary collection of~$3m$ vertex-disjoint copies of
  $\Ktm$ (using Fact~\ref{fact:cliquecount}).  Label the copies of
  $K_{t-1}$ as $\cK:=\{K^1, K^2, \dots, K^{3m}\}$.  Then label
  $A=\{a_{ij}: x_i z_j\in E(T)\}$ as the vertices in the classes
  of~$40$ vertices in the copies of $\Ktm$ such that each $a_{ij}$
  together with $K^i$ forms a copy of $K_t$ (we may then discard some
  extra vertices, according to the degree of~$x_i$ in~$T$).

  We will pick $Z=\{z_1,\dots, z_{4m}\}$ and
  $\cS=\{S_{ij}: x_i z_j\in E(T)\}$ satisfying the definition of the
  absorbing structure as follows.  Suppose that we have picked
  $Z(j-1)=\{z_1,\dots, z_{j-1}\}$ and $\cS(j-1)=\{S_{ij'}: j'<j\}$
  with the desired properties.  At step~$j$, we pick as~$z_{j}$ a
  uniform random vertex in
  $V(G)\setminus (V(\cK)\cup Z(j-1)\cup V(\cS(j-1))\cup B_j)$, where
  $B_j$ is the set of vertices $z$ in $G$ such that
  $|(N_G(a_{ij})\setminus (V(\cK)\cup Z(j-1)\cup V(\cS(j-1))))\cap
  N_G(z)| < d^2/(4n)$ for some $i$ with $x_i z_j\in E(T)$.  Since
  $|V(\cK)| + 4m + 120(t-1)m\le (123t+1) \eps d<d/2$ and
  $\Delta(T)\le 40$, Fact~\ref{fact:irregular} with
  $U=N_G(a_{ij})\setminus (V(\cK)\cup Z(j-1)\cup V(\cS(j-1)))$ implies
  that $|B_{j}|\le 40\eps d$.  Next, for each $i$ such that
  $x_i\in N_T(z_j)$, we pick a $(t-1)$-clique $S_{ij}$ in
  $(N_G(a_{ij})\setminus (V(\cK)\cup Z(j-1)\cup V(\cS(j-1))))\cap
  N_G({z_j})$, which is possible by Fact~\ref{fact:cliquecount}
  because this set contains at least $d^2/(4n)$ vertices of $G$.
  Moreover, we can choose these at most $40$ cliques to be
  vertex-disjoint, because they only take up $40(t-1)$ vertices and
  any set in $G$ of size $d^2/(4n)-40(t-1) > d^2/(5n)$ still contains
  a $(t-1)$-clique.

  At last we analyse the random process for~$Z$ and prove that, with
  positive probability, all vertices~$v$ of~$G$ are such
  that~$\deg(v,Z_1)$ is appropriately large.  Note that at step $j$ we
  have fixed
  $|V(\cK)\cup V(\cS(j-1)) \cup Z(j-1)|\le {3}(t+39)m+120(t-1)m+4m \le
  (123t+1) \eps d$ vertices.  Since when we pick $z_j$, we also need
  to avoid the set $B_j$ of size at most $40\eps d$, in total we need
  to avoid at most $140t\eps d$ vertices.  Let $v$ be a vertex in
  $G$. Given a choice of $V(\cK)\cup V(\cS(j-1)) \cup Z(j-1)$, the
  probability that $z_j\in N_G(v)$ is at least $(1-{140t}\eps) d/n$.
  Then, by Lemma~\ref{lem:coupling} with $\delta=\eps$, we have
  \[
    \Pr\left(\deg(v, Z_1) < \frac d{2n}
      |Z_1|\right)<\Pr\left(\deg_G(v, Z_1) < (1- \eps)
      (1-{140t}\eps)|Z_1|d/n\right) < e^{-\eps^3 d^2/n} =
    o\left(1\over n\right).
  \]
  Thus, the union bound over all vertices of~$G$ implies that the
  existence of~$Z_1$ with the desired property in the lemma.
\end{proof}

\subsection{A Hall-type result}
Another tool that we will use is the following theorem of Aharoni and
Haxell~\cite[Corollary~1.2]{AhHa00}.

\begin{theorem}
  \label{AhHa}
  Let $\cH$ be a family of $k$-uniform hypergraphs {on the same vertex
    set}.  A sufficient condition for the existence of a system of
  disjoint representatives\footnote{By this we mean a selection of
      edges $e_H\in H$ for all~$H\in\cH$ such that
      $e_H\cap e_H'=\emptyset$ for all $H\neq H'\in \cH$.} for $\cH$
  is that for every $\cG\subseteq \cH$ there exists a matching in
  {$\bigcup_{H\in \cG}E(H)$} of size greater than $k(|\cG|-1)$.
\end{theorem}

\section{Proof of Theorem~\ref{thm:main}}

We are now ready to prove our main result.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
  Let~$t\geq3$ be given.  Let $\eps_0$ be given by Lemma~\ref{lem:1}.
  Choose $\eps:=\min\{\eps_0,t^{-2}\}$ and let~$n_0$ be given by
  Lemma~\ref{lem:1} on input $\eps_0$.  Finally, set
  $c=\eps^2/2^{t+1}$.  We may assume that
  \begin{equation}\label{eq:blow_up}
    {d\over n}\le{\eps\over2t},
  \end{equation}
  since otherwise the existence of a $K_t$-factor is guaranteed by the
  Blow-up Lemma~\cite{KSS_bl} (see the discussion in~\cite{HKP18a}).
  We apply Lemma~\ref{lem:1} to~$G$ and obtain an absorbing structure
  $(T, \cK, A, \cS, Z, Z_1)$ with flexibility~$m=\epsilon d$ on a
  set~$W$ of at most $124t\eps d$ vertices.  Thus $Z_1\subset W$ is
  such that $|Z_1|=2\eps d$ and, for any subset $\bar Z\subseteq Z_1$
  with $|\bar Z|=\eps d$, the absorbing structure with $\bar Z$
  removed has a $K_t$-factor.  Moreover, $\deg(v, Z_1) \ge d|Z_1|/2n$
  for any vertex~$v$ in~$G$.

  Now we greedily find vertex-disjoint copies of~$K_t$ in
  $G\setminus W$ as long as there are at most $\eps^2 d$ vertices
  left. This is possible by Fact~\ref{fact:cliquecount} because
  $\eps^2 d > 2^tcd$.  We denote the set of uncovered vertices in
  $V(G)\setminus W$ by~$U$.  Thus $|U|\le \eps^2 d$.

  Next we will cover $U$ by vertex-disjoint copies of $K_t$ with one
  vertex in $U$ and the other vertices from $Z_1$ by applying
  Theorem~\ref{AhHa}.  To that end, for each vertex $v\in U$, let
  $H_v$ be the set of $(t-1)$-element sets of $N(v)\cap Z_1$ that
  induce copies of $K_{t-1}$ in $G$ and let $\cH=\{H_v: v\in U\}$.  We
  claim that~$\cH$ has a system of disjoint representatives.  To
  verify the assumption of Theorem~\ref{AhHa}, we first consider sets
  $X\subseteq U$ of size at least $d^{2t-3}/n^{2t-4}$.  Let $Z'$ be
  any subset of $Z_1$ of size~$\eps d$.  Note that
  $|X||Z'|\ge \eps d^{2t-2}/n^{2t-4}$, which implies that
  $\lambda \le cd^{t}/n^{t-1}\le \eps(d/n)\sqrt{|X||Z'|}$.  By
  Theorem~\ref{thm:EML}, we have
  \[
    e(X, Z')\ge \frac dn |X| |Z'| - \lambda \sqrt{|X||Z'|} \ge \frac
    dn |X| |Z'| - \eps \frac dn |X| |Z'| \ge \frac d{2n} |X| |Z'|.
  \]
  Hence there exists a vertex $v\in X$ such that
  $\deg(v, Z')\ge d|Z'|/(2n) = \eps d^2/(2n)$.  By
  Fact~\ref{fact:cliquecount}, we can find a copy of $K_{t-1}$ in
  $N(v)\cap Z'$.  Thus in this case we can greedily find
  vertex-disjoint copies of $K_{t-1}$ which belong to
  $\bigcup_{v\in X} H_v$, as long as there are $\eps d$ vertices in
  $Z_1$ left uncovered.  This gives a matching in
  $\bigcup_{v\in X} H_v$ of size
  $\eps d/(t-1) > (t-1)\eps^2 d \ge (t-1)|X|$, for $\eps$ sufficiently
  small.  It remains to consider sets $X\subseteq U$ of size at most
  $d^{2t-3}/n^{2t-4}$.  In this case we fix any vertex $v\in X$ and
  only consider matchings in~$H_v$.  Indeed, by the construction of
  the absorbing structure (see Lemma~\ref{lem:1}), we have
  $\deg(v, Z_1) \ge d|Z_1|/2n = \eps d^2/n$ for any~$v$.  Since by
  Fact~\ref{fact:cliquecount} there is a copy of $K_{t-1}$ in every
  set of size $\eps d^2/(2n)$, we can find a set of
  $\eps d^2/(2(t-1)n)$ vertex-disjoint copies of~$K_{t-1}$ in~$H_v$.
  We are done because $\eps d^2/(2(t-1)n) \ge d^{2t-3}/n^{2t-4}$ holds
  by our initial assumption~\eqref{eq:blow_up}.  Theorem~\ref{AhHa}
  then tells us that a system of disjoint representatives does exist
  for~$\cH$, whence we conclude that there are vertex-disjoint copies
  of $K_t$ which cover all the vertices in $V(G)\setminus W$ and
  $(t-1)\eps^2d$ vertices of~$Z_1$.  We can then greedily find
  vertex-disjoint copies of~$K_t$ in the remainder of $Z_1$, which
  exist by Fact~\ref{fact:cliquecount}, until exactly $\eps d$
  vertices of $Z_1$ remain (which will be the case due to the
  divisibility assumption $t\mid n$). Then the key property of the
  absorbing structure completes a full $K_t$-factor.
\end{proof}

\section{Concluding remarks}\label{sec:remark}

\subsection*{Bijumbled graphs}
A graph $G$ on $n$ vertices is called $(\lambda,p)$-bijumbled if for
any two vertex subsets $A$, $B\subset V(G)$,
\begin{equation*}
    \left|e(A,B)-p|A||B|\right|<\lambda\sqrt{|A||B|}.
  \end{equation*}
Thus by Theorem~\ref{thm:EML},
any $(n,d,\lambda)$-graph is $(\lambda,d/n)$-bijumbled.
Nenadov's result~\cite{Nen18} asserts that for $p\in(0,1]$, any
$(\epsilon p^{t-1}n/\log n,p)$-bijumbled graph of minimum degree at
least~$pn/2$ contains a $K_t$-factor if~$\epsilon=\epsilon_t>0$ is
sufficiently small and~$t\mid n$.  It is straightforward to generalize
Theorem~\ref{thm:main} to $K_t$-factors and
$(\epsilon p^tn,p)$-bijumbled graphs with minimum degree~$pn/2$
and~$\epsilon=\epsilon_t>0$ sufficiently small.

\subsection*{A condition for arbitrary $2$-factors}
In his concluding remarks, Nenadov~\cite{Nen18} raises the question
whether the condition $\lambda=o(p^2n/\log n)$ is sufficient to force
any $(\lambda,p)$-bijumbled graph~$G$ of minimum degree $\Omega(pn)$
to contain any given $2$-factor, i.e., any $n$-vertex $2$-regular
graph.  Since any $2$-factor consists of vertex-disjoint cycles whose
lengths add up to~$n$, the problem is thus to find any given
collection of such cycles in $G$.  We will return to this question
elsewhere~\cite{HKMP18b}, with a positive answer to Nenadov's
question.

\bibliography{literature}

\end{document}


TITLE: Prove the inequality $\sqrt{\frac{a^2+1}{b+c}}+\sqrt{\frac{b^2+1}{a+c}}+\sqrt{\frac{c^2+1}{a+b}}\ge 3$
QUESTION [1 upvotes]: Let $a;b;c\in R^+$ such that $ab+bc+ca>0$. Prove that $$\sqrt{\frac{a^2+1}{b+c}}+\sqrt{\frac{b^2+1}{a+c}}+\sqrt{\frac{c^2+1}{a+b}}\ge 3$$

I have seen the similar question is $$\frac{a^2+1}{b+c}+\frac{b^2+1}{a+c}+\frac{c^2+1}{a+b}\ge 3$$ my problem is harder than it
My try: Holder: $$LHS^2\cdot \sum _{cyc}\left(a^2+1\right)^2\left(b+c\right)\ge \left(a^2+b^2+c^2+3\right)^3$$
Then we need to prove: $$\left(a^2+b^2+c^2+3\right)^3\ge 9\sum _{cyc}\left(a^2+1\right)^2\left(b+c\right)$$
After full expanding I am stuck because that inequality is not homogeneous, it hard to solve.

REPLY [4 votes]: Because by AM-GM and C-S we obtain:
$$\sum_{cyc}\sqrt{\frac{a^2+1}{b+c}}\geq3\sqrt[6]{\prod_{cyc}\frac{a^2+1}{b+c}}=3\sqrt[12]{\prod_{cyc}\frac{(a^2+1)(1+b^2)}{(a+b)^2}}\geq3\sqrt[12]{\prod_{cyc}\frac{(a+b)^2}{(a+b)^2}}=3$$


TITLE: Distance and origin preserving map between two normed vector spaces
QUESTION [1 upvotes]: Let $V$ and $W$ be two normed vector spaces and let $f: V \rightarrow W$ be a map that preserves distance as well as the origin, that is :
$ \forall x,y \in V \quad \|f(x)-f(y)\|_W=\|x-y\|_V \quad $ and $\quad f(0_V)=0_W $
Is $f$ necessarily linear ?
I know that if the norm satisfies the parallelogram identity then the answer is yes.
By the Mazur–Ulam theorem, I know that if $f$ is surjective then the answer is also yes. Here I'm asking about the consequences of requiring origin preservation instead of surjectivity.

REPLY [2 votes]: No, it may well not be linear. Consider the map$$\begin{array}{rccc}f\colon&\mathbb R&\longrightarrow&\mathbb{R}^2\\&x&\mapsto&(x,|x|).\end{array}$$On $\mathbb{R}^2$, consider the norm $\bigl\|(x,y)\bigr\|=\max\bigl\{|x|,|y|\bigr\}$ and on $\mathbb R$ the usual norm. Then $f$ preserves distances and the origin, but it is not linear.

REPLY [2 votes]: No. Take $V = \mathbb{R}$ with the standard norm and $W = \mathbb{R}^2$ with the maximum norm. Then let $f(x) = (|x|,x)$, clearly distance and origin-preserving, but not linear.


text:
~\\
\section{\sc\bf $A$-type linkage systems}
 \label{sec_stratif_A}

\subsection{The linkage systems  $\mathscr{L}(A_l)$ for $l = 5,6,7$}
  \label{sec_plis_Al}
  \index{linkage system  ! - $\mathscr{L}(A_l)$ for $l = 5,6,7$}

 In this section, we suppose that $\Gamma = A_l$ with $l = 5,6,7$.
 Let $S$ be a $\Gamma$-associated root subset. First, we have
 \begin{equation}
   \label{eq_first_Al}
   \begin{split}
    & \mathscr{L}(A_l) = \mathscr{L}_{A_{l+1}}(A_l) \cup \mathscr{L}_{D_{l+1}}(A_l)  \text{ for } l \neq 5,6,7, \\
    & \mathscr{L}(A_l) = \mathscr{L}_{A_{l+1}}(A_l) \cup \mathscr{L}_{D_{l+1}}(A_l) \cup \mathscr{L}_{E_{l+1}}(A_l)
           \text{ for } l = 5,6,7. \\
   \end{split}
 \end{equation}

 By \eqref{eq_regext4} the sizes of $A$- $D$- and $E$-components are estimated as follows:
 \begin{equation}
   \label{eq_first_Al_2}
   \Small
   \begin{split}
    & \mid \mathscr{L}_{A_{l+1}}(A_l) \mid ~\leq~ \mid \varPhi(A_{l+1}) \mid - \mid \varPhi(A_l) \mid =
              (l+1)(l+2) - l(l+1) = 2(l+1), \\
    & \mid \mathscr{L}_{D_{l+1}}(A_l) \mid ~\leq~ \mid \varPhi(D_{l+1}) \mid - \mid \varPhi(A_l) \mid =
              2l(l+1) - l(l+1) = l(l+1), \\
    & \mid \mathscr{L}_{E_6}(A_5) \mid ~\leq~ \mid \varPhi(E_6) \mid - \mid \varPhi(A_5) \mid = 72 - 30 = 42, \\
    & \mid \mathscr{L}_{E_7}(A_6) \mid ~\leq~ \mid \varPhi(E_7) \mid - \mid \varPhi(A_6) \mid = 126 - 42 = 84, \\
    & \mid \mathscr{L}_{E_8}(A_7) \mid ~\leq~ \mid \varPhi(E_8) \mid - \mid \varPhi(A_7) \mid = 240 - 56 = 184. \\
   \end{split}
 \end{equation}

\subsubsection{The linkage systems  $\mathscr{L}(A_3)$}
 By \eqref{eq_first_Al} and \eqref{eq_first_Al_2} we have

 \begin{equation}
   \label{eq_first_Al_3}
      \mathscr{L}(A_3) = \mathscr{L}_{A_4}(A_3) \cup \mathscr{L}_{D_4}(A_3), \text{ where }
      \mid \mathscr{L}_{A_4}(A_3) \mid \leq 8, \quad  \mid \mathscr{L}_{D_4}(A_3) \mid \leq 12.
 \end{equation}

 \begin{figure}[H]
 \centering
 \includegraphics[scale=0.56]{A3_to_A4D4.eps}
 \caption{
 \hspace{3mm}The single part of the $D$-component and two parts of the $A$-component
  of the linkage system $\mathscr{L}(A_3)$}

 \label{A3_to_A4D4}
 \end{figure}

 In Fig. \ref{A3_to_A4D4}, we have $8$ linkage label vectors in the $A$-component of the
 linkage system $\mathscr{L}(A_3)$. By \eqref{eq_first_Al_3} we conclude that there are
 \underline{exactly $8$ linkages in the $A$-component} $\mathscr{L}_{A_4}(A_3)$.
 For the component $\mathscr{L}_{D_4}(A_3)$, there is a different picture:
 By Table \ref{tab_pairs_D4overA4} the size of $\mathscr{L}_{A_4}(A_3)$ is twice less than the estimate in \eqref{eq_first_Al_3},
 i.e., $\mid \mathscr{L}_{D_4}(A_3) \mid \leq 6$. Thus, $\mid \mathscr{L}(A_3) \mid = 6 + 8 = 14$,
 see Fig. \ref{A3_to_A4D4}.

 \begin{table}[H]
  \footnotesize
  \centering
  \renewcommand{\arraystretch}{1.3}
  \begin{tabular} {|c|c|c|c|}
  \hline
       & $\varphi \in \varPhi(D_4)\backslash\varPhi(A_3)$ &  $\delta \in \varPhi(D_4)\backslash\varPhi(A_3)$
       & $\delta^{\nabla} = -\varphi^{\nabla} \in \mathscr{L}_{D_4}(A_3)$ \\
    \hline
     1 & $\begin{array}{ccccccc}
            0 & 1 & 1 \\
              & 1
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & 1 & 0  \\
              & 1
         \end{array}$ &
          $\begin{array}{ccccccc}
             \alpha_1 & \beta_1 & \alpha_2 \\
              -1 & 0 & 1  \\

         \end{array}$ \\
    \hline
     2 & $\begin{array}{ccccccc}
            1 & 1 & 1 \\
              & 1
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 1 & 0  \\
              & 1
         \end{array}$ &
          $\begin{array}{ccccccc}
           \alpha_1 & \beta_1 & \alpha_2 \\
             1 & -1 & 1  \\

         \end{array}$ \\
    \hline
     3 & $\begin{array}{ccccccc}
            1 & 2 & 1 \\
              & 1
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0  \\
              & 1
         \end{array}$ &
          $\begin{array}{ccccccc}
            \alpha_1 & \beta_1 & \alpha_2 \\
             0 & 1 & 0  \\

         \end{array}$  \\
    \hline
     4 & $\begin{array}{ccccccc}
            0 & -1 & -1 \\
              & -1
         \end{array}$ &
         $\begin{array}{ccccccc}
            -1 & -1 & 0  \\
              & -1
         \end{array}$ &
          $\begin{array}{ccccccc}
             \alpha_1 & \beta_1 & \alpha_2 \\
               1 & 0 & -1  \\

         \end{array}$ \\
    \hline
     5 & $\begin{array}{ccccccc}
            -1 & -1 & -1 \\
              & -1
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & -1 & 0  \\
              & -1
         \end{array}$ &
          $\begin{array}{ccccccc}
           \alpha_1 & \beta_1 & \alpha_2 \\
             -1 & 1 & -1  \\

         \end{array}$ \\
    \hline
     6 & $\begin{array}{ccccccc}
            -1 & -2 & -1 \\
               & -1
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0  \\
              & -1
         \end{array}$ &
          $\begin{array}{ccccccc}
            \alpha_1 & \beta_1 & \alpha_2 \\
             0 & -1 & 0  \\

         \end{array}$  \\
    \hline
  \end{tabular}
  \vspace{2mm}
  \caption{\hspace{3mm} $6$ pairs of roots $\varphi, \delta \in \varPhi(D_4)\backslash\varPhi(A_3)$ such that
    $\delta^{\nabla} = -\varphi^{\nabla}$}
    \label{tab_pairs_D4overA4}
  \end{table}

\subsubsection{The linkage systems  $\mathscr{L}(A_4)$}
 By \eqref{eq_first_Al} and \eqref{eq_first_Al_2} we have

 \begin{equation}
   \label{eq_first_Al_4}
      \mathscr{L}(A_4) = \mathscr{L}_{A_5}(A_4) \cup \mathscr{L}_{D_5}(A_4), \text{ where }
      \mid \mathscr{L}_{A_5}(A_4) \mid \leq 10, \quad  \mid \mathscr{L}_{D_5}(A_4) \mid \leq 20.
 \end{equation}

  The linkage system $\mathscr{L}(A_4)$ contains $4$ parts. One of the two parts of the $D$-component
  (resp. $A$-component) of the linkage system $\mathscr{L}(A_4)$ corresponds to the positive roots
   of $\varPhi(D_5)\backslash\varPhi(A_4)$ (resp. $\varPhi(A_5)\backslash\varPhi(A_4)$),
  another part of the $D$-component (resp. $A$-component) of the linkage system $\mathscr{L}(A_4)$
  corresponds to the negative roots of
  $\varPhi(D_5)\backslash\varPhi(A_4)$ (resp. $\varPhi(A_5)\backslash\varPhi(A_4)$).
  In all, \underline{there are $10 + 20 = 30$ elements in $\mathscr{L}(A_4)$}.

 \begin{figure}[H]
 \centering
 \includegraphics[scale=0.55]{A4_to_A5D5.eps}
 \caption{
 \hspace{3mm}One of the two parts of the $D$-component and one of two parts of the $A$-component
  of the linkage system $\mathscr{L}(A_4)$}

 \label{A4_to_A5D5}
 \end{figure}

\subsubsection{The linkage systems  $\mathscr{L}(A_5)$}
 By \eqref{eq_first_Al} and \eqref{eq_first_Al_2} we have

 \begin{equation}
   \label{eq_first_A5_1}
    \begin{split}
      & \mathscr{L}(A_5) = \mathscr{L}_{A_6}(A_5) \cup \mathscr{L}_{D_6}(A_5) \cup \mathscr{L}_{E_6}(A_5), \text{ where } \\
      & \mid \mathscr{L}_{A_6}(A_5) \mid ~\leq~ 12, \quad  \mid \mathscr{L}_{D_6}(A_5) \mid ~\leq~ 30, \quad
      \mid \mathscr{L}_{E_6}(A_5) \mid ~\leq~ 72 - 30 = 42.
    \end{split}
 \end{equation}
 Let the coordinates of roots of $E_6$ be as follows:
  \begin{equation*}
   \begin{array}{cccccc}
     \tau_1 & \tau_3 & \tau_4 & \tau_5 & \tau_6 \\
            &   & \tau_2 \\
    \end{array}
   \end{equation*}
 Consider the maximal and minimal roots in $E_6$:
  \begin{equation*}
   \mu_{max} = \left (
   \begin{array}{cccccc}
     1 & 2 & 3 & 2 & 1 \\
       &   & 2 \\
   \end{array}
     \right ), \quad
   \mu_{min} = -\left (
   \begin{array}{cccccc}
     1 & 2 & 3 & 2 & 1 \\
       &   & 2 \\
   \end{array}
     \right ).
  \end{equation*}

  The roots $\mu_{max}$ (resp. $\mu_{min}$) is orthogonal to any simple root except for  $\tau_2$.
  The vectors $\pm\mu_{max}^{\nabla}$ are zero.
  \index{linkage label vectors ! - $\mu^{\nabla}_{max}$ and $\mu^{\nabla}_{min}$ for $E_6$}
  Then by \eqref{eq_first_A5_1}
 \begin{equation}
   \label{eq_first_A5_2}
   \mid \mathscr{L}_{E_6}(A_5) \mid ~\leq~  42 - 2 = 40.
  \end{equation}

  \begin{lemma}
   \label{lem_compl_roots_A5}
   Let $E_6$ be the Dynkin extension of the Carter diagram $\Gamma = A_5$,
   $\varphi$ be a certain positive root in $\varPhi(E_6)\backslash\varPhi(A_5)$.
   \index{Dynkin extension ! - $A_5 <_D E_6$}
   \index{$\Gamma <_D \Gamma'$, Dynkin extension}

     {\rm (i)} The vector
   \begin{equation}
     \label{eq_A5_ext1}
      \delta = \mu_{max} - \varphi,
   \end{equation}
   where $\varphi \neq \mu_{max}$, is also a root in $\varPhi(E_6)\backslash\varPhi(A_5)$.
 ~\\

 \index{$L$, linear space ! - spanned by the $\Gamma$-associated root subset}

    {\rm (ii)}
    The linkage label vectors $\varphi^{\nabla}$ and $-\delta^{\nabla}$ coincide:
   \begin{equation}
     \label{eq_A5_ext2}
      \delta^{\nabla} = -\varphi^{\nabla}.
   \end{equation}
 \end{lemma}

 \PerfProof  \rm (i) As above, in Lemmas \ref{lem_coinc_linkage} and \ref{lem_compl_roots_E8}, we need to prove that
  \begin{equation}
     \label{eq_A5_ext3}
        \mathscr{B}(\mu_{max}) + \mathscr{B}(\varphi) - 2(\varphi, \mu_{max}) = 2. \\
   \end{equation}
In other words, we need to prove that
  \begin{equation}
     \label{eq_A5_ext4}
       (\varphi, \mu_{max}) = 1.
   \end{equation}
~\\
 We have
  \begin{equation}
      \label{eq_A5_ext5}
     (\gamma, \mu_{max}) =
       \begin{cases}
           1 \text{ for } \gamma = \tau_2, \\
           0 \text{ for } \gamma = \tau_i, \text{ where } i \neq 2.
       \end{cases}
   \end{equation}
  The fact that $\varphi \in \varPhi(E_6)\backslash\varPhi(A_5)$, $\varphi \neq \mu_{max}$ and $\varphi$ is positive means
  that $\tau_2$ enters with coefficient $1$ into the decomposition of $\varphi$ with relation to $\{\tau_1, \dots, \tau_6\}$.
  By \eqref{eq_A5_ext5} the relation \eqref{eq_A5_ext4} holds for
  any root $\varphi \in \varPhi(E_6)\backslash\varPhi(A_5)$.
  Therefore, \eqref{eq_A5_ext3} holds, i.e., $\delta$ is also a root.
  By \cite[Table V]{Bo02} the coordinate $\tau_2$ of $\mu_{max}$ is $2$.
  By \eqref{eq_A5_ext1} $\tau_2$ also enters with coefficient $1$ into the decomposition of $\delta$
  with relation to $\{\tau_1, \dots, \tau_6\}$.
  Thus, $\delta$ also belongs to $\varPhi(E_6)\backslash\varPhi(A_5)$.

 \rm (ii) By \eqref{eq_A5_ext5} for $\varphi \neq \tau_2$, we have
    \begin{equation}
     \label{eq_A5_ext6}
        \delta^{\nabla}_i = (\delta, \tau_i) =  -(\varphi, \tau_i) = -\varphi^{\nabla}_i.
   \end{equation}
 Since $L = [\tau_1,\tau_3,\tau_4,\tau_5,\tau_6]$, we have $\delta^{\nabla} = -\varphi^{\nabla}.$
 \qed
~\\

 By \eqref{eq_first_A5_1}, \eqref{eq_first_A5_2}
 the two parts of the $A$-component contain $2 \times 6 = 12$ elements; the two parts of the $D$-component
 contain $2 \times 15 = 30$ elements, see Fig. \ref{A5_to_A6D6E6}. By Lemma \ref{lem_compl_roots_A5} and
 eq. \eqref{eq_first_A5_2} we see that
 the $E$-component contains $\leq 40/2 = 20$ elements. In Fig. \ref{A5_to_A6D6E6}, we see that
 the $E$-component contains  exactly $20$ elements. In all, the linkage system
  \underline{$\mathscr{L}(A_5)$ contains $12 + 30 + 20 = 62$ elements.}

 \begin{figure}[H]
 \centering
 \includegraphics[scale=0.55]{A5_to_A6D6E6.eps}
 \caption{
 \hspace{3mm}One of the two parts of the $D$-component, one of the two parts of the $A$-component, and
 the $E$-component of the linkage system $\mathscr{L}(A_5)$}

 \label{A5_to_A6D6E6}
 \end{figure}

\subsubsection{The linkage systems  $\mathscr{L}(A_6)$}
 By \eqref{eq_first_Al} and \eqref{eq_first_Al_2} we have
  \index{linkage diagrams ! - in $\mathscr{L}(A_6)$}

 \begin{equation}
   \label{eq_first_A6_1}

    \begin{split}
      & \mathscr{L}(A_6) = \mathscr{L}_{A_7}(A_6) \cup \mathscr{L}_{D_7}(A_6) \cup \mathscr{L}_{E_7}(A_6), \text{ where } \\
      & \mid \mathscr{L}_{A_7}(A_6) \mid ~\leq~ 14, \quad  \mid \mathscr{L}_{D_7}(A_6) \mid ~\leq~ 42, \quad
      \mid \mathscr{L}_{E_7}(A_6) \mid ~\leq~ 126 - 42 = 84.
    \end{split}
 \end{equation}
~\\
 However, there are $7$ pairs of positive (resp. $7$ pairs of negative) roots  $\{\eta, \lambda\}$,
 where $\eta \in \varPhi(E_7)\backslash\varPhi(A_6)$ and $\lambda \in \varPhi(A_7)\backslash\varPhi(A_6)$
 such that the corresponding linkage label vectors coincide up-to-sign:
 $$
   \eta^{\nabla} = -\lambda^{\nabla},
 $$
 see Table \ref{tab_pairs_roots_A6ext}.
 In other words, we have to subtract $14$ roots from the estimate of $\mid \mathscr{L}_{E_7}(A_6) \mid$:
 \begin{equation}
   \label{eq_first_A6_2}

      \mid \mathscr{L}_{A_7}(A_6) \mid ~\leq~ 14, \quad  \mid \mathscr{L}_{D_7}(A_6) \mid ~\leq~ 42, \quad
      \mid \mathscr{L}_{E_7}(A_6) \mid ~\leq~ 70.
 \end{equation}
There are $2 \times 7 + 2 \times 21 + 2 \times 35 = 14 + 42 + 70 = 126$ linkage diagrams
in $\mathscr{L}(A_6)$ presented in Fig. \ref{A6_to_A7D7E7}. We conclude that there are
\underline{exactly $126$ linkage diagrams in $\mathscr{L}(A_6)$}.

\subsubsection{The linkage systems  $\mathscr{L}(A_7)$}
  \index{root system}
 By \eqref{eq_first_Al} and \eqref{eq_first_Al_2} we have
 \begin{equation}
   \label{eq_first_A7_1}
    \begin{split}
      & \mathscr{L}(A_7) = \mathscr{L}_{A_8}(A_7) \cup \mathscr{L}_{D_8}(A_7) \cup \mathscr{L}_{E_8}(A_7), \text{ where } \\
      & \mid \mathscr{L}_{A_8}(A_7) \mid ~\leq~ 16, \quad  \mid \mathscr{L}_{D_8}(A_7) \mid ~\leq~ 56, \quad
      \mid \mathscr{L}_{E_8}(A_7) \mid ~\leq~ 240 - 56 = 184.
    \end{split}
 \end{equation}

  \begin{table}[H]

  \centering
  \renewcommand{\arraystretch}{1.3}
  \begin{tabular} {|c|c|c|c|}
  \hline
       & $\eta \in \varPhi(E_7)\backslash\varPhi(A_6)$ &  $\lambda \in \varPhi(A_7)\backslash\varPhi(A_6)$
       & $\eta^{\nabla} = -\lambda^{\nabla}  \in \mathscr{L}(A_6)$ \\
    \hline
     1 & $\begin{array}{ccccccc}
          \alpha_1 & \beta_1 & \alpha_2 & \beta_2 & \alpha_3 & \beta_3 \\
            1 & 2 & 3 & 2 & 1 & 0 \\
              &  &  2
         \end{array}$ &
         $\begin{array}{ccccccc}
          & \alpha_1 & \beta_1 & \alpha_2 & \beta_2 & \alpha_3 & \beta_3 \\
            1 & 1 & 1 & 1 & 1 & 1 & 1 \\
         \end{array}$ &
          $\begin{array}{ccccccc}
          \alpha_1 & \beta_1 & \alpha_2 & \beta_2 & \alpha_3 & \beta_3 \\
             0 & 0 & 0 & 0 & 0 & -1 \\
         \end{array}$ \\
    \hline
     2 & $\begin{array}{ccccccc}
            1 & \hspace{2mm}2 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}1 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}0 \\
         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}-1 & \hspace{2mm}1 \\
         \end{array}$ \\
    \hline
     3 & $\begin{array}{ccccccc}
            1 & \hspace{2mm}2 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}2 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 \\

         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}-1 & \hspace{2mm}1 & \hspace{2mm}0 \\
         \end{array}$ \\
    \hline
     4 & $\begin{array}{ccccccc}
            1 & \hspace{2mm}2 & \hspace{2mm}3 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\

         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}-1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 \\
         \end{array}$ \\
    \hline
     5 & $\begin{array}{ccccccc}
            1 & \hspace{2mm}2 & \hspace{2mm}4 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\

         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}0 & \hspace{2mm}-1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\
         \end{array}$ \\
    \hline
     6 & $\begin{array}{ccccccc}
            1 & \hspace{2mm}3 & \hspace{2mm}4 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\

         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}-1 & \hspace{2mm}1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\
         \end{array}$ \\
    \hline
     7 & $\begin{array}{ccccccc}
            2 & \hspace{2mm}3 & \hspace{2mm}4 & \hspace{2mm}3 & \hspace{2mm}2 & \hspace{2mm}1 \\
              &  &  \hspace{2mm}2
         \end{array}$ &
         $\begin{array}{ccccccc}
            1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\

         \end{array}$ &
          $\begin{array}{ccccccc}
             \hspace{2mm}-1 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 & \hspace{2mm}0 \\
         \end{array}$ \\
    \hline
       \end{tabular}
  \vspace{2mm}
  \caption{\hspace{3mm} $7$ pairs of positive roots $\{\eta, \lambda\}$ such that $\eta^{\nabla} = -\lambda^{\nabla}$.
     There are also $7$ pairs of negative roots $\{\eta, \lambda\}$ such that $\eta^{\nabla} = -\lambda^{\nabla}$}
  \label{tab_pairs_roots_A6ext}
  \end{table}
~\\
 However, there are $8$ pairs of positive (resp. $8$ pairs of negative) roots  $\{\eta, \lambda\}$,
 where $\eta \in \varPhi(E_8)\backslash\varPhi(A_7)$ and $\lambda \in \varPhi(A_8)\backslash\varPhi(A_7)$
 such that the corresponding  linkage label vectors coincide up-to-sign:
 $$
   \eta^{\nabla} = -\lambda^{\nabla}.
 $$
 The pairs $\{\eta_i, \lambda_i\}$, where $1 \leq i \leq 8$ are depicted in Table \ref{tab_pairs_roots_A7extE8}.
 In other words, we have to subtract $16$ linkage label vectors from the estimate of $\mid \mathscr{L}_{E_8}(A_7) \mid$:
 \begin{equation}
   \label{eq_first_A7_2}
      \mid \mathscr{L}_{E_8}(A_7) \mid ~\leq~ 184 - 16 = 168.
 \end{equation}

\begin{remark}
{\rm
For any root $\gamma$ from the root system $\varPhi(A_l)$, we consider the sequence of coordinates
of the linkage label vector $\gamma^{\nabla}$
ordered as they lie in the diagram $A_l$, see $A$-components in Figs. \ref{A6_to_A7D7E7}, \ref{A7_to_A8D8_1}, i.e.,
 \index{linear order for the linkage diagram}
 \index{bicolored order}
\begin{equation}
  \label{lin_order}
    \gamma^{\nabla} = \{ a_1, b_1, a_2, b_2, \dots, a_i, b_i, \dots \}, \text{ where } a_i = (\alpha_i, \gamma), b_i = (\beta_i, \gamma).
\end{equation}
Then we say that the linkage diagram $\gamma^{\nabla}$ is given in a {\it linear order}. Note
that usually we consider coordinates of the linkage label vector $\gamma^{\nabla}$ in a {\it bicolored order} given as follows:
\begin{equation*}
    \gamma^{\nabla} = \{ a_1, a_2, \dots, b_1, b_2, \dots \}.
\end{equation*}
In Table \ref{tab_pairs_roots_A7extE8}, the linkage label vectors $\lambda^{\nabla}_i$ are given in
a linear order. The same vectors in the $A$-component in Fig. \ref{A7_to_A8D8_1} are given in the bicolored order.
\qed
}
\end{remark}

 \index{Weyl group ! - $W$}
 \index{$W$, Weyl group}
 \index{space of linkage labels $L^{\nabla}$ for $\varPhi(A_7)$}
 In addition, there are $28$ pairs of positive (resp. $28$ pairs of negative) roots  $\{\eta, \lambda\}$,
 where $\eta \in \varPhi(E_8)\backslash\varPhi(A_7)$ and $\lambda \in \varPhi(D_8)\backslash\varPhi(A_7)$
 such that the corresponding linkage label vectors coincide: $\eta^{\nabla} = \lambda^{\nabla}$.
 We do not present all of the $28$ pairs $\{\eta_i, \lambda_i\}$:
 It suffices to produce one pair, the remaining $27$ pairs are obtained by action of the Weyl group. Namely,
 let us take roots $\eta_1 \in \varPhi(E_8)\backslash\varPhi(A_7)$ and $\lambda_1 \in \varPhi(D_8)\backslash\varPhi(A_7)$
 such that $\eta_1^{\nabla} = \lambda_1^{\nabla}$;
 let $w \in W$, where $W$ is the Weyl group associated with $\varPhi(A_7)$.
 Though $w\eta_1$ and $w\lambda_1$ lie in different root systems,
 $w^*\eta^{\nabla}_1$ and $w^*\lambda^{\nabla}_1$ coincide:
 \begin{equation*}
    (w\eta_1)^{\nabla} = w^*\eta^{\nabla}_1 = w^*\lambda^{\nabla}_1 = (w\lambda_1)^{\nabla},
 \end{equation*}
 see Proposition \ref{prop_link_diagr_conn}(ii).
 Consider the following pair $\{\eta_1, \lambda_1\}$:
 \begin{equation*}
  \Small

    \eta_1 =
   \begin{array}{ccccccc}
      2 & 4 & 5 & 4 & 3 & 2 & 1 \\
      & & 2
   \end{array}  \in \varPhi(E_8)\backslash\varPhi(A_7), \qquad

    \lambda_1 =
   \begin{array}{ccccccc}
      0 & 0 & 0 & 0 & 0 & 0 & 0 \\
      &  -1
   \end{array} \in \varPhi(D_8)\backslash\varPhi(A_7).

 \end{equation*}
 Then
  \begin{equation*}
  \Small
    \eta^{\nabla}_1 = \lambda^{\nabla}_1 =
  \begin{cases}
   \begin{array}{ccccccc}
      0 & 1 & 0 & 0 & 0 & 0 & 0 \\
      \alpha_1 & \beta_1 & \alpha_2 & \beta_2 & \alpha_3 & \beta_3 & \alpha_4
   \end{array} \text{ in linear order,}
   \\ \\
   \begin{array}{ccccccc}
      0 & 0 & 0 & 0 & 1 & 0 & 0 \\
      \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 & \beta_1 & \beta_2 & \beta_3
   \end{array} \text{ in bicolored order.}
  \end{cases}
 \end{equation*}
The linkage label vector $\lambda^{\nabla}_1$ is the top element
in one of two $28$-element parts of the $D$-component of $\mathscr{L}(A_7)$, see Fig. \ref{A7_to_A8D8_1}.
Therefore, we have to subtract $2 \times 28 = 56$ linkage label vectors
from the estimate of $\mid \mathscr{L}_{E_8}(A_7) \mid$ in \eqref{eq_first_A7_2}:
 \begin{equation}
   \label{eq_first_A7_3}
      \mid \mathscr{L}_{E_8}(A_7) \mid ~\leq~ 168 - 56 = 112.
 \end{equation}
By \eqref{eq_first_A7_1}, \eqref{eq_first_A7_3}, we have
\begin{equation}
   \label{eq_first_A7_4}
      \mid \mathscr{L}_{A_8}(A_7) \mid ~\leq~ 16, \quad  \mid \mathscr{L}_{D_8}(A_7) \mid ~\leq~ 56, \quad
      \mid \mathscr{L}_{E_8}(A_7) \mid ~\leq~ 112.
 \end{equation}
In accordance to Figs. \ref{A7_to_A8D8_1} and \ref{A7_to_E8} we have
\underline{exactly $16 + 56 + 112 = 184$ linkages in $\mathscr{L}(A_7)$}.

  \begin{table}[H]
  \footnotesize
  \centering
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{|c|c|c|c|}
  \hline
       & $\eta \in \varPhi(E_8)\backslash\varPhi(A_7)$ &
         $\lambda \in \varPhi(A_8)\backslash\varPhi(A_7)$ &
         $\lambda^{\nabla} = \eta^{\nabla}$ \\
   \hline
     & $\begin{array}{ccccccc}
          \alpha_1  \hspace{2mm}\beta_1  \hspace{2mm}\alpha_2  \hspace{2mm}\beta_2  \hspace{2mm}\alpha_3
                    \hspace{2mm}\beta_3   \hspace{2mm}\alpha_4 \\
      \end{array}$ &
     $\begin{array}{cccccccc}
          & \hspace{2mm}\alpha_1  \hspace{2mm}\beta_1  \hspace{2mm}\alpha_2  \hspace{2mm}\beta_2  \hspace{2mm}\alpha_3
                    \hspace{2mm}\beta_3   \hspace{2mm}\alpha_4 \\
      \end{array}$ &
     $\begin{array}{ccccccc}
           \alpha_1  \hspace{2mm}\beta_1  \hspace{2mm}\alpha_2  \hspace{2mm}\beta_2  \hspace{2mm}\alpha_3
                    \hspace{2mm}\beta_3   \hspace{2mm}\alpha_4 \\
        \end{array}$  \\
    \hline
     1 & $\begin{array}{ccccccc}
            1 & 3 & 5 & 4 & 3 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            -1 & 0 & 0 & 0 & 0 & 0 & 0 \\
         \end{array}$  \\
    \hline
     2 & $\begin{array}{ccccccc}
            2 & 3 & 5 & 4 & 3 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
             1 & -1 & 0 & 0 & 0 & 0 & 0 \\
         \end{array}$ \\
    \hline
     3 & $\begin{array}{ccccccc}
            2 & 4 & 5 & 4 & 3 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 1 & -1 & 0 & 0 & 0 & 0 \\
         \end{array}$ \\
    \hline
     4 & $\begin{array}{ccccccc}
            2 & 4 & 6 & 4 & 3 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 1 & -1 & 0 & 0 & 0 \\
         \end{array}$ \\
    \hline
     5 & $\begin{array}{ccccccc}
            2 & 4 & 6 & 5 & 3 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0 & 1 & -1 & 0 & 0 \\
         \end{array}$ \\
    \hline
     6 & $\begin{array}{ccccccc}
            2 & 4 & 6 & 5 & 4 & 2 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0 & 0 & 1 & -1 & 0 \\
         \end{array}$ \\
    \hline
     7 & $\begin{array}{ccccccc}
            2 & 4 & 6 & 5 & 4 & 3 & 1 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0 & 0 & 0 & 1 & -1 \\
         \end{array}$ \\
     \hline
     8 & $\begin{array}{ccccccc}
            2 & 4 & 6 & 5 & 4 & 3 & 2 \\
              &  &  3
         \end{array}$ &
         $\begin{array}{cccccccc}
            1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
         \end{array}$ &
         $\begin{array}{ccccccc}
            0 & 0 & 0 & 0 & 0 & 0 & 1 \\
         \end{array}$ \\
    \hline
       \end{tabular}
  \vspace{2mm}
  \caption{\hspace{3mm} $8$ pairs of positive roots $\{\eta, \lambda\}$ such that $\eta^{\nabla} = \lambda^{\nabla}$.
     There are also $8$ pairs of negative roots $\{\eta, \lambda\}$ such that $\eta^{\nabla} = \lambda^{\nabla}$}
  \label{tab_pairs_roots_A7extE8}
  \end{table}

\subsection{The linkage systems  $\mathscr{L}(A_l)$ for $l \geq 8$}
    \label{sec_Al_lg8}
    \index{Dynkin extension ! - $A_l <_D D_{l+1}$}
    \index{$\Gamma <_D \Gamma'$, Dynkin extension}
    \index{linkage system  ! - $\mathscr{L}(A_l)$ for $l \geq 8$}

 For convenience, we introduce coordinates $\{x_i, y_j\}$, where $1 \leq i,j \leq l$, for every
 linkage diagram in the $D$-component of the linkage system
 $\mathscr{L}_{D_{l+1}}(A_l)$.
 In Fig. \ref{Al_coord}, the path $y_i$ (resp. $x_i$), where $1 \leq i \leq l$, consists of reflections acting
 in the direction from Nord-West to South-East (resp. from Nord-East to South-West).
 The linkage diagram lying in the intersection node of paths $x_i$ and $y_j$  has coordinates $\{x_i, y_j\}$.

 \begin{proposition}[On the $D$-component of the linkage systems  $\mathscr{L}(A_l)$]
  \label{ptop_Dcomp}
   Consider the Dynkin extension $A_l <_D D_{l+1}$.

  ${\rm (i)}$
   For $l > 3$, the $D$-component of the linkage systems  $\mathscr{L}(A_l)$ consists of two non-connected parts $\mathscr{L}^+$ and
   $\mathscr{L}^-$ corresponding to the positive (resp. negative) linkage roots in the root stratum $\varPhi(D_{l+1})\backslash\varPhi(A_l)$.
   For $l = 3$, components $\mathscr{L}^+$ and $\mathscr{L}^-$ coincide, see Fig. \ref{A3_to_A4D4}.

   For $l=2n$ (resp. $l=2n+1$), where $n \geq 2$ (resp. $n \geq 1$), reflections acting on linkage diagrams of
   $\mathscr{L}^+$ are given in Fig. \ref{Al_coord}$(a)$ (resp. Fig. \ref{Al_coord}$(b)$);
   the linkage diagram $\gamma^{\nabla}$ in the top of $\mathscr{L}^+$ (vertex $\{x_{2n}, y_1\}$ (resp. $\{x_{2n+1}, y_1\}$))
   depicted in Fig. \ref{A2n_top_root}$(a)$ (resp. $(b)$).

 \begin{figure}[H]
 \centering
 \includegraphics[scale=0.6]{A2n_top_root.eps}  \\
 \begin{equation*}
 \begin{array}{lllllllll}
  \gamma^{\nabla} = &\{0,~~ \dots, &0,~~~&1,~~0,\dots, &0 \} \qquad\qquad
  \gamma^{\nabla} = &\{0,~~ \dots, &0,~~~&1,~~0, \dots, &0 \}\\
    &~\alpha_1 &\alpha_n &\beta_1 &\beta_n &~\alpha_1 &\alpha_{n+1} &\beta_1 &\beta_n
 \end{array}
 \end{equation*}
 \caption{}
 \label{A2n_top_root}
 \end{figure}
   Remaining linkage diagrams of $\mathscr{L}^+$ are constructed from $\gamma$ by means of reflections
\begin{equation}
  \begin{split}
   & s^*_{\alpha_1}, s^*_{\beta_1}, s^*_{\alpha_2}, s^*_{\beta_2}, \dots, s^*_{\alpha_n}, s^*_{\beta_n} \text{ for } l = 2n, \text{ or }, \\
   & s^*_{\alpha_1}, s^*_{\beta_1}, s^*_{\alpha_2}, s^*_{\beta_2}, \dots, s^*_{\alpha_n}, s^*_{\beta_n}, s^*_{\alpha_{n+1}}
   \text{ for } l = 2n + 1.
  \end{split}
\end{equation}
   see Fig. \ref{Al_coord}.
   The three last lines of $\mathscr{L}^+$  corresponding to coordinates
   $y_{2n-2}$, $y_{2n-1}$ and $y_{2n}$ (resp. $y_{2n-1}$, $y_{2n}$ and $y_{2n+1}$ )
   are given in Fig. \ref{3_lines_A2n} (resp. Fig. \ref{3_lines_A2nPl1}).

   (For $3 \leq l \leq 7$, see Figs. \ref{A3_to_A4D4} - \ref{A7_to_A8D8_1}).
~\\

  ${\rm (ii)}$
   For $l > 3$, we have
 \begin{equation}
   \mid \mathscr{L}_{D_{l+1}(A_l)} \mid = l(l+1).
 \end{equation}
 \end{proposition}

   \PerfProof (i) For transitions
  $\mathscr{L}(A_5)  \Rightarrow \mathscr{L}(A_6)$ and $\mathscr{L}(A_6)  \Rightarrow \mathscr{L}(A_7)$,
  see Fig. \ref{A5_to_A6D6_pass}. For the transition $\mathscr{L}(A_7)  \Rightarrow \mathscr{L}(A_8)$,
  see Fig. \ref{A8_to_A9D9_mono}. We prove the proposition by induction.
~\\

  \underline{Transition $2n-1 \Rightarrow 2n$.} Consider the triangle
  $\Delta_{2n-2} = \{\{y_1, x_{2n}\}, \{y_{2n-2},x_{2n}\}, \{y_{2n-2},x_3\}\}$ is the linkage subsystem
  containing linkage diagrams with the coordinate $y_i$ for $i \leq 2n-2$, see Fig. \ref{Al_coord}$(a)$.
  To transit from $2n-1$ to $2n$ coordinates,
  we extend any linkage diagram  $\gamma^{\nabla}$ in the triangle $\Delta_{2n-2}$ and in the line $y_{2n-2}$
  in Fig. \ref{2_lines_A2nMin1} by the vertex $\beta_n$ non-connected with $\gamma$. In other words, we have
  $\gamma^{\nabla}_{\beta_n} = (\gamma, \beta_n) = 0,$ see Figs. \ref{A8_to_A9D9_mono}, \ref{Al_coord}$(a)$.
   Remember that any linkage diagram is equivalent to a certain
   linkage label vector, see \S\ref{sec_linkage_diagr_0}. For the extension of the linkage diagram and
   the equivalent linkage label vectors, see Fig. \ref{one_diagr_An}$(a)$.
 \begin{figure}[H]
\centering
\includegraphics[scale=0.8]{one_diagr_An.eps}
\caption{\hspace{3mm} Extension $\gamma^{\nabla} \rightarrow  \widetilde\gamma^{\nabla}$
of linkage diagrams $(a)$ and $(b)$ and equivalent linkage label vectors. Additional coordinates are in bold}

\label{one_diagr_An}
\end{figure}
~\\
  By induction hypothesis,
  any reflection $s^*_{\varphi}$, which acts within the triangle $\Delta_{2n-2}$,
  differs from $s^*_{\alpha_n}$ and $s^*_{\beta_n}$, see Fig. \ref{Al_coord}.
  So $s^*_{\varphi}$ \underline{do not touch the coordinate $\gamma^{\nabla}_{\beta_n}$}.
  We put $\gamma^{\nabla}_{\beta_n} = 0$ to every linkage $\gamma^{\nabla}$ from $\Delta_{2n-2}$ and
  the subsystem given by the triangle $\Delta_{2n-2}$ is saved in the transition $2n-1 \Rightarrow 2n$.
  We see this process of the extension by the vertex $\beta_n$ in lines $y_{2n-2}$ of diagrams in Fig. \ref{2_lines_A2nMin1}
  and Fig. \ref{3_lines_A2n}.

\begin{figure}[H]
\centering
 \vspace{1cm}
\includegraphics[scale=0.47]{Al_coord_4.eps}
\caption{\hspace{3mm} Coordinates $\{x_i, y_j\}$ in the $D$-component
of the linkage system $A_{2n+1}$}

\label{Al_coord}
\end{figure}
~\\
  By induction hypothesis, we have $\gamma^{\nabla}_{\alpha_n} = 1$
  for any linkage diagram $\gamma^{\nabla}$ in the line $y_{2n-2}$ in $\Delta_{2n-2}$, see Fig. \ref{2_lines_A2nMin1}.
  The same holds for
  extensions of these diagrams in the line $y_{2n-2}$ in Fig. \ref{3_lines_A2n}.  Consider now
  the last lines of the linkage system $\mathscr{L}(A_{2n})$ in  Fig. \ref{3_lines_A2n}.
  By acting $s^*_{\alpha_n}$ on every linkage diagram $\gamma^{\nabla}$ in the line $y_{2n-2}$, we get linkage diagrams
  with $\gamma^{\nabla}_{\beta_n} = 1$  in the line $y_{2n-1}$.
  Really, by \eqref{dual_refl} coordinates
  $\gamma^{\nabla}_{\alpha_n}$ and $\gamma^{\nabla}_{\beta_n}$
  for any linkage diagram $\gamma^{\nabla}$ in the line $y_{2n-2}$ are transformed as follows:
  \begin{equation*}
     (s^*_{\alpha_n}\gamma^{\nabla})_{\beta_n} = \gamma^{\nabla}_{\beta_n} + \gamma^{\nabla}_{\alpha_n}, \qquad
     (s^*_{\alpha_n}\gamma^{\nabla})_{\alpha_n} = -\gamma^{\nabla}_{\alpha_n},
  \end{equation*}
  see \eqref{dual_refl_alpha_beta}.
  The linkage diagram $\{x_2, y_{2n-1}\}$ in the line $y_{2n-1}$ in Fig. \ref{3_lines_A2n}
  is obtained by acting $s^*_{\beta_{n-1}}$ on the linkage diagram $\{x_3, y_{2n-1}\}$.
  Further, by acting $s^*_{\beta_n}$ on every linkage diagram
  (except for linkage diagrams $\{x_2, y_{2n}\}$ and $\{x_1, y_{2n}\}$)
  in the line $y_{2n-1}$ we get the last line with $\gamma^{\nabla}_{\alpha_n} = 0$ and $\gamma^{\nabla}_{\beta_n} = -1$.
  The linkage diagram $\{x_2, y_{2n}\}$ (resp. $\{x_1, y_{2n}\}$) is obtained
  by acting $s^*_{\beta_{n-1}}$ (resp. $s^*_{\alpha_n}$) on the linkage diagram $\{x_3, y_{2n}\}$ (resp. $\{x_2, y_{2n}\}$).
~\\

  \underline{Transition $2n \Rightarrow 2n+1$} is considered in a similar way.
~\\

  (ii) It is easy to see from Fig. \ref{Al_coord} that
  \begin{equation*}
    \mid \mathscr{L}^+ \mid =  \mid \mathscr{L}^+ \mid = \frac{l(l+1)}{2}.
  \end{equation*}
  Since $\mathscr{L}_{D_{l+1}(A_l)} = \mathscr{L}^+ \coprod \mathscr{L}^-$ the statement is proved.

\qed

 \begin{proposition}[On the $A$-component of the linkage systems  $\mathscr{L}(A_l)$]
   The $A$-component of the linkage systems  $\mathscr{L}(A_l)$ consists of two non-connected parts $\mathscr{L}^+$ and
   $\mathscr{L}^-$ corresponding to the positive (resp. negative) linkage roots in the Dynkin extension $A_l <_D A_{l+1}$.
   The number of linkage diagrams in the $A$-component of the linkage systems  $\mathscr{L}(A_l)$ is equal to $2(l+1)$.
 \end{proposition}

 \PerfProof This statement is also proved by induction. Consider, the \underline{transition ${2n-1} \Rightarrow 2n$}.
 For $n = 3$ this process is shown in Fig. \ref{A5_to_A6D6_pass}, see $A_5 \Rightarrow A_6$.
 The first $2n-1$ linkage diagrams are extended by the vertex $\gamma^{\nabla}_{\beta_{n}} = 0$.
 Under the action of $s^*_{\alpha_n}$ the ($2n$)th linkage diagram is extended by the coordinate $\gamma^{\nabla}_{\beta_n} = 1$.
 Under the action of $s^*_{\beta_n}$ the ($2n+1$)th linkage diagram is added,
 the coordinate $\gamma^{\nabla}_{\beta_{n}}$ of this linkage diagram is equal $-1$.
 \qed

\clearpage
 \begin{figure}[H]
\centering
 \vspace{1cm}
\includegraphics[scale=0.5]{A6_to_A7D7E7_1.eps}
\caption{\hspace{3mm}The linkage system $A_6$ has $6$ components: The two parts
 of the $A$-component, the two $21$-element parts of the $D$-component, and the two $35$-element parts of the $E$-component}

\label{A6_to_A7D7E7}
\end{figure}

 \begin{figure}[H]
\centering

\includegraphics[scale=0.5]{A7_to_A8D8_1.eps}

\vspace{1cm}
\caption{\hspace{3mm} The linkage system $A_7$. One of the two $8$-element parts
 of the $A$-component (see Table \ref{tab_pairs_roots_A7extE8}) and one of the two $28$-element parts of the $D$-component}

\label{A7_to_A8D8_1}
\end{figure}

\clearpage
 \begin{figure}[H]
\centering
 \vspace{1cm}
\includegraphics[scale=0.6]{A7_to_E8.eps}
\caption{\hspace{3mm} The linkage system $A_7$ (cont). One of the two $56$-element parts
 of the $E$-component}

\label{A7_to_E8}
\end{figure}

 \begin{figure}[H]
\centering
 \vspace{1cm}
\includegraphics[scale=0.7]{2_lines_A2nMin1.eps}
\caption{\hspace{3mm} The last $2$ lines of the $D$-component of $A_{2n-1}$}

\label{2_lines_A2nMin1}
 \vspace{1cm}
\includegraphics[scale=0.7]{3_lines_A2n.eps}
\caption{\hspace{3mm} The last $3$ lines of the $D$-component of $A_{2n}$}

\label{3_lines_A2n}
 \vspace{1cm}
\includegraphics[scale=0.7]{3_lines_A2nPl1.eps}
\caption{\hspace{3mm} The last $3$ lines of the $D$-component of $A_{2n+1}$}

\label{3_lines_A2nPl1}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.42]{A5_to_A6D6_pass_mono.eps}
\vspace{1cm}
\includegraphics[scale=0.48]{A6_to_A7D7_mono.eps}
\caption{\hspace{3mm}The transition
  $\mathscr{L}(A_5)  \Longrightarrow \mathscr{L}(A_6)$ and $\mathscr{L}(A_6)  \Longrightarrow \mathscr{L}(A_7)$.
  The new coordinate $\beta_3$ for the case $\mathscr{L}(A_6)$ (resp. $\alpha_4$ for the case $\mathscr{L}(A_7)$)
  and new linkage diagrams are in bold}

\label{A5_to_A6D6_pass}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.6]{A8_to_A9D9_mono.eps}
\caption{\hspace{3mm}The transition from $A$-components and
 $D$-components in the linkage system $A_7$ to the linkage system $A_8$.
 The new coordinate $\beta_4$ and new linkage diagrams are marked in bold}

\label{A8_to_A9D9_mono}
\end{figure}