# A remark on continued fractions for permutations
and D-permutations with a weight $-1$ per cycle

Bishal Deb1 and Alan D. Sokal1,2
1Department of Mathematics, University College London, London WC1E 6BT, UK
2Department of Physics, New York University, New York, NY 10003, USA

<EMAIL_ADDRESS><EMAIL_ADDRESS>

(20 June 2023)

###### Abstract

We show that very simple continued fractions can be obtained for the ordinary
generating functions enumerating permutations or D-permutations with a large
number of independent statistics, when each cycle is given a weight $-1$. The
proof is based on a simple lemma relating the number of cycles modulo 2 to the
numbers of fixed points, cycle peaks (or cycle valleys), and crossings.

Key Words: Permutation, D-permutation, continued fraction.

Mathematics Subject Classification (MSC 2020) codes: 05A19 (Primary); 05A05,
05A15, 05A30, 30B70 (Secondary).

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Continued fractions
    2. 2.2 Permutation statistics: The record-and-cycle classification
    3. 2.3 Permutation statistics: Crossings and nestings
  3. 3 Proof of Lemma 1.1
  4. 4 Results for permutations
    1. 4.1 Master J-fraction
    2. 4.2 $p,q$ J-fraction
    3. 4.3 Simple J-fraction
    4. 4.4 Corollary for cycle-alternating permutations
  5. 5 Results for D-permutations
    1. 5.1 Master T-fraction
    2. 5.2 $p,q$ T-fraction
    3. 5.3 Simple T-fraction
  6. Acknowledgments

##  1 Introduction

In a recent paper, Zeng and one of us [13] proved continued fractions
enumerating permutations with 10, 18 or infinitely many statistics that
implement the cycle classification of indices (cycle peak, cycle valley, cycle
double rise, cycle double fall, fixed point) together with an index-refined
count of crossings and nestings. Subsequently, the two present authors [3]
proved analogous results for D-permutations [8, 10, 9], which are a subclass
of permutations of $[2n]$ counted by the Genocchi and median Genocchi numbers:
our continued fractions enumerated D-permutations with 12, 22 or infinitely
many statistics that implement the parity-refined cycle classification of
indices (cycle peak, cycle valley, cycle double rise, cycle double fall, even
fixed point, odd fixed point) together with an index-refined count of
crossings and nestings. In both papers, we called these results our “first”
continued fractions.

In both cases, it was natural to try to extend these results by taking account
also of the number of cycles: that is, by including an additional weight
$\lambda^{{\rm cyc}(\sigma)}$. However, it turned out that it was possible to
do so only by renouncing some of the other statistics: for instance, by
counting cycle valleys only with respect to crossings + nestings, rather than
to crossings and nestings separately. We called these results our “second”
continued fractions.

Our purpose here is to make a simple but previously overlooked remark: that in
addition to the trivial case $\lambda=1$, there is one other case where one
need not renounce counting any other statistics, namely, $\lambda=-1$. The
reason for this is the following simple lemma, which relates the number of
cycles modulo 2 to the number of fixed points, cycle peaks (or cycle valleys),
and crossings:

######  Lemma 1.1.

Let $\sigma\in{\mathfrak{S}}_{n}$ be a permutation. Then the following
identity holds:

${\rm cyc}&={\rm fix}+{\rm cpeak}+{\rm ucross}+{\rm lcross}\pmod{2}{}\\\ ={\rm
fix}+{\rm cval}+{\rm ucross}+{\rm lcross}\pmod{2}\;.{}$ (1.1)

We will give a precise definition of ucross (number of upper crossings) and
lcross (number of lower crossings) in Section 2.3, and then a proof of this
lemma in Section 3.

Using Lemma 1.1, it is easy to obtain continued fractions for the case
$\lambda=-1$ as simple corollaries of those for $\lambda=1$. That is what we
shall do in this paper.

The plan of this paper is as follows: In Section 2 we give some preliminary
definitions concerning continued fractions and permutation statistics. In
Section 3 we give two proofs of Lemma 1.1: one topological, and one
combinatorial. Then, in Sections 4 and 5, we give our results for permutations
and D-permutations, respectively.

We remark that since Lemma 1.1 is a general fact concerning permutations, it
can be applied to any result concerning any subclass of permutations in which
the statistics ${\rm fix}$, ${\rm cpeak}$ and ${\rm ucross}+{\rm lcross}$ are
handled.

##  2 Preliminaries

###  2.1 Continued fractions

If $(a_{n})_{n\geq 0}$ is a sequence of combinatorial numbers or polynomials
with $a_{0}=1$, it is often fruitful to seek to express its ordinary
generating function as a continued fraction of either Stieltjes type
(S-fraction),

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\cfrac{\alpha_{1}t}{1-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\;,$
(2.1)

Thron type (T-fraction),

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\delta_{1}t-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\;,$
(2.2)

or Jacobi type (J-fraction),

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\gamma_{0}t-\cfrac{\beta_{1}t^{2}}{1-\gamma_{1}t-\cfrac{\beta_{2}t^{2}}{1-\cdots}}}\;\;.$
(2.3)

Both sides of these expressions are to be interpreted as formal power series
in the indeterminate $t$.

###  2.2 Permutation statistics: The record-and-cycle classification

Given a permutation $\sigma\in{\mathfrak{S}}_{N}$, an index $i\in[N]$ is
called an

  * •

excedance (exc) if $i<\sigma(i)$;

  * •

anti-excedance (aexc) if $i>\sigma(i)$;

  * •

fixed point (fix) if $i=\sigma(i)$.

Clearly every index $i$ belongs to exactly one of these three types; we call
this the excedance classification. We also say that $i$ is a weak excedance if
$i\leq\sigma(i)$, and a weak anti-excedance if $i\geq\sigma(i)$.

A more refined classification is as follows: an index $i\in[N]$ is called a

  * •

cycle peak (cpeak) if $\sigma^{-1}(i)<i>\sigma(i)$;

  * •

cycle valley (cval) if $\sigma^{-1}(i)>i<\sigma(i)$;

  * •

cycle double rise (cdrise) if $\sigma^{-1}(i)<i<\sigma(i)$;

  * •

cycle double fall (cdfall) if $\sigma^{-1}(i)>i>\sigma(i)$;

  * •

fixed point (fix) if $\sigma^{-1}(i)=i=\sigma(i)$.

Clearly every index $i$ belongs to exactly one of these five types; we refer
to this classification as the cycle classification. Obviously, excedance =
cycle valley or cycle double rise, and anti-excedance = cycle peak or cycle
double fall. We write

${\rm Cpeak}(\sigma)\;=\;\\{i\colon\>\sigma^{-1}(i)<i>\sigma(i)\\}$ (2.4)

for the set of cycle peaks and

${\rm cpeak}(\sigma)\;=\;|{\rm Cpeak}(\sigma)|$ (2.5)

for its cardinality, and likewise for the others.

On the other hand, an index $i\in[N]$ is called a

  * •

record (rec) (or left-to-right maximum) if $\sigma(j)<\sigma(i)$ for all $j<i$
[note in particular that the indices 1 and $\sigma^{-1}(N)$ are always
records];

  * •

antirecord (arec) (or right-to-left minimum) if $\sigma(j)>\sigma(i)$ for all
$j>i$ [note in particular that the indices $N$ and $\sigma^{-1}(1)$ are always
antirecords];

  * •

exclusive record (erec) if it is a record and not also an antirecord;

  * •

exclusive antirecord (earec) if it is an antirecord and not also a record;

  * •

record-antirecord (rar) (or pivot) if it is both a record and an antirecord;

  * •

neither-record-antirecord (nrar) if it is neither a record nor an antirecord.

Every index $i$ thus belongs to exactly one of the latter four types; we refer
to this classification as the record classification.

The record and cycle classifications of indices are related as follows:

>   * (a)
>
> Every record is a weak excedance, and every exclusive record is an
> excedance.
>
>   * (b)
>
> Every antirecord is a weak anti-excedance, and every exclusive antirecord is
> an anti-excedance.
>
>   * (c)
>
> Every record-antirecord is a fixed point.
>
>

Therefore, by applying the record and cycle classifications simultaneously, we
obtain 10 disjoint categories [13]:

  * •

ereccval: exclusive records that are also cycle valleys;

  * •

ereccdrise: exclusive records that are also cycle double rises;

  * •

eareccpeak: exclusive antirecords that are also cycle peaks;

  * •

eareccdfall: exclusive antirecords that are also cycle double falls;

  * •

rar: record-antirecords (these are always fixed points);

  * •

nrcpeak: neither-record-antirecords that are also cycle peaks;

  * •

nrcval: neither-record-antirecords that are also cycle valleys;

  * •

nrcdrise: neither-record-antirecords that are also cycle double rises;

  * •

nrcdfall: neither-record-antirecords that are also cycle double falls;

  * •

nrfix: neither-record-antirecords that are also fixed points.

Clearly every index $i$ belongs to exactly one of these 10 types; we call this
the record-and-cycle classification.

When studying D-permutations, we will use the parity-refined record-and-cycle
classification, in which we distinguish even and odd fixed points.

###  2.3 Permutation statistics: Crossings and nestings

We now define (following [13]) some permutation statistics that count
crossings and nestings.

First we associate to each permutation $\sigma\in{\mathfrak{S}}_{N}$ a
pictorial representation (Figure 1) by placing vertices $1,2,\ldots,N$ along a
horizontal axis and then drawing an arc from $i$ to $\sigma(i)$ above (resp.
below) the horizontal axis in case $\sigma(i)>i$ [resp. $\sigma(i)<i$]; if
$\sigma(i)=i$ we do not draw any arc.

1234567891011 Figure 1:  Pictorial representation of the permutation
$\sigma=9\,3\,7\,4\,6\,11\,2\,8\,10\,1\,5=(1,9,10)\,(2,3,7)\,(4)\,(5,6,11)\,(8)\in{\mathfrak{S}}_{11}$.

Each vertex thus has either out-degree = in-degree = 1 (if it is not a fixed
point) or out-degree = in-degree = 0 (if it is a fixed point). Of course, the
arrows on the arcs are redundant, because the arrow on an arc above (resp.
below) the axis always points to the right (resp. left); we therefore omit the
arrows for simplicity.

We then say that a quadruplet $i<j<k<l$ forms an

  * •

upper crossing (ucross) if $k=\sigma(i)$ and $l=\sigma(j)$;

  * •

lower crossing (lcross) if $i=\sigma(k)$ and $j=\sigma(l)$;

  * •

upper nesting (unest) if $l=\sigma(i)$ and $k=\sigma(j)$;

  * •

lower nesting (lnest) if $i=\sigma(l)$ and $j=\sigma(k)$.

We also consider some “degenerate” cases with $j=k$, by saying that a triplet
$i<j<l$ forms an

  * •

upper joining (ujoin) if $j=\sigma(i)$ and $l=\sigma(j)$ [i.e. the index $j$
is a cycle double rise];

  * •

lower joining (ljoin) if $i=\sigma(j)$ and $j=\sigma(l)$ [i.e. the index $j$
is a cycle double fall];

  * •

upper pseudo-nesting (upsnest) if $l=\sigma(i)$ and $j=\sigma(j)$;

  * •

lower pseudo-nesting (lpsnest) if $i=\sigma(l)$ and $j=\sigma(j)$.

These are clearly degenerate cases of crossings and nestings, respectively.
See Figure 2. Note that ${\rm upsnest}(\sigma)={\rm lpsnest}(\sigma)$ for all
$\sigma$, since for each fixed point $j$, the number of pairs $(i,l)$ with
$i<j<l$ such that $l=\sigma(i)$ has to equal the number of such pairs with
$i=\sigma(l)$; we therefore write these two statistics simply as

${\rm psnest}(\sigma)\;\stackrel{{\scriptstyle\rm def}}{{=}}\;{\rm
upsnest}(\sigma)\;=\;{\rm lpsnest}(\sigma)\;.$ (2.6)

And of course ${\rm ujoin}={\rm cdrise}$ and ${\rm ljoin}={\rm cdfall}$.

$i$$j$$k$$l$Upper crossing$i$$j$$k$$l$Lower crossing

$i$$j$$k$$l$Upper nesting$i$$j$$k$$l$Lower nesting

$i$$j$$l$Upper joining$i$$j$$l$Lower joining

$i$$j$$l$Upper pseudo-nesting$i$$j$$l$Lower pseudo-nesting

Figure 2:  Crossing, nesting, joining and pseudo-nesting.

$i$$j$$k$$l$Upper crossing of type cval$i$$j$$k$$l$Upper crossing of type
cdrise

$i$$j$$k$$l$Lower crossing of type cpeak$i$$j$$k$$l$Lower crossing of type
cdfall

$i$$j$$k$$l$Upper nesting of type cval$i$$j$$k$$l$Upper nesting of type cdrise

$i$$j$$k$$l$Lower nesting of type cpeak$i$$j$$k$$l$Lower nesting of type
cdfall

Figure 3:  Refined categories of crossing and nesting.

We can further refine the four crossing/nesting categories by examining more
closely the status of the inner index ($j$ or $k$) whose outgoing arc belonged
to the crossing or nesting: we say that a quadruplet $i<j<k<l$ forms an

  * •

upper crossing of type cval (ucrosscval) if $k=\sigma(i)$ and $l=\sigma(j)$
and ${\sigma^{-1}(j)>j}$;

  * •

upper crossing of type cdrise (ucrosscdrise) if $k=\sigma(i)$ and
$l=\sigma(j)$ and ${\sigma^{-1}(j)<j}$;

  * •

lower crossing of type cpeak (lcrosscpeak) if $i=\sigma(k)$ and $j=\sigma(l)$
and ${\sigma^{-1}(k)<k}$;

  * •

lower crossing of type cdfall (lcrosscdfall) if $i=\sigma(k)$ and
$j=\sigma(l)$ and ${\sigma^{-1}(k)>k}$;

  * •

upper nesting of type cval (unestcval) if $l=\sigma(i)$ and $k=\sigma(j)$ and
${\sigma^{-1}(j)>j}$;

  * •

upper nesting of type cdrise (unestcdrise) if $l=\sigma(i)$ and $k=\sigma(j)$
and ${\sigma^{-1}(j)<j}$;

  * •

lower nesting of type cpeak (lnestcpeak) if $i=\sigma(l)$ and $j=\sigma(k)$
and ${\sigma^{-1}(k)<k}$;

  * •

lower nesting of type cdfall (lnestcdfall) if $i=\sigma(l)$ and $j=\sigma(k)$
and ${\sigma^{-1}(k)>k}$.

See Figure 3. Please note that for the “upper” quantities the distinguished
index (i.e. the one for which we examine both $\sigma$ and $\sigma^{-1}$) is
in second position ($j$), while for the “lower” quantities the distinguished
index is in third position ($k$).

In fact, a central role in our work will be played (just as in [13, 3]) by a
yet further refinement of these statistics: rather than counting the total
numbers of quadruplets $i<j<k<l$ that form upper (resp. lower) crossings or
nestings of the foregoing types, we will count the number of upper (resp.
lower) crossings or nestings that use a particular vertex $j$ (resp. $k$) in
second (resp. third) position. More precisely, we define the index-refined
crossing and nesting statistics

${\rm ucross}(j,\sigma)&=\\#\\{i<j<k<l\colon\>k=\sigma(i)\hbox{ and
}l=\sigma(j)\\}\\\ {\rm
unest}(j,\sigma)=\\#\\{i<j<k<l\colon\>k=\sigma(j)\hbox{ and }l=\sigma(i)\\}\\\
{\rm lcross}(k,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(k)\hbox{ and
}j=\sigma(l)\\}\\\ {\rm
lnest}(k,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(l)\hbox{ and }j=\sigma(k)\\}$
(2.7)

Note that ${\rm ucross}(j,\sigma)$ and ${\rm unest}(j,\sigma)$ can be nonzero
only when $j$ is an excedance (that is, a cycle valley or a cycle double
rise), while ${\rm lcross}(k,\sigma)$ and ${\rm lnest}(k,\sigma)$ can be
nonzero only when $k$ is an anti-excedance (that is, a cycle peak or a cycle
double fall).

When $j$ is a fixed point, we also define the analogous quantity for pseudo-
nestings:

${\rm psnest}(j,\sigma)\;\stackrel{{\scriptstyle\rm
def}}{{=}}\;\\#\\{i<j\colon\>\sigma(i)>j\\}\;=\;\\#\\{i>j\colon\>\sigma(i)<j\\}\;.$
(2.8)

(Here the two expressions are equal because $\sigma$ is a bijection from
$[1,j)\cup(j,n]$ to itself.) In [13, eq. (2.20)] this quantity was called the
level of the fixed point $j$ and was denoted ${\rm lev}(j,\sigma)$.

##  3 Proof of Lemma 1.1

We will give two proofs of Lemma 1.1: one topological, and one combinatorial.
The topological proof is extremely satisfying from an intuitive point of view,
but it requires some nontrivial results on the topology of the plane to make
it rigorous. The combinatorial proof is simple and manifestly rigorous, but it
relies on an identity for the number of inversions [5, Lemme 3.1] [12, eq.
(40)] [13, Proposition 2.24] whose proof is elementary but not entirely
trivial.

Topological Proof. Draw the diagram representing the permutation $\sigma$
(Figure 1) such that each arc is a $C^{1}$ non-self-intersecting curve that
has a vertical tangent at each cycle peak and cycle valley and a horizontal
tangent at each cycle double rise and cycle double fall, and such that each
pair of arcs intersects either zero times (if they do not represent a
crossing) or once transversally (if they do represent a crossing), and also
such that each intersection point involves only two arcs (see Figure 4 for the
example of Figure 1 redrawn according to these rules). Then each cycle becomes
a $C^{1}$ closed curve with a finite number of self-intersections, all of
which are transversal double points; following Whitney [18, pp. 280–281], we
call such a curve normal. The total number of intersections in the diagram is
${\rm ucross}+{\rm lcross}$.

Figure 4:  Diagram of the permutation
$\sigma=9\,3\,7\,4\,6\,11\,2\,8\,10\,1\,5=(1,9,10)\,(2,3,7)\,(4)\,(5,6,11)\,(8)\in{\mathfrak{S}}_{11}$
shown in Figure 1, drawn according to the rules stated in the text.

Each fixed point is of course a cycle. So we focus henceforth on cycles of
length $\geq 2$. We will prove the following two facts:

  * (a)

The number of self-intersections in a cycle is equal modulo 2 to the number of
cycle peaks (or alternatively, cycle valleys) in that cycle, plus 1.

  * (b)

The number of intersections between two distinct cycles is equal modulo 2 to
zero.

Together these facts will prove Lemma 1.1.

Proof of (a).  The rotation angle (or tangent winding angle) of a $C^{1}$
closed curve is the total angle through which the tangent vector turns while
traversing the curve.111 In [17, Section 3] and [1, Chapter 3], the rotation
angle divided by $2\pi$ is called the rotation index.  With the above
conventions for the arc diagram (with arcs traversed in the direction of the
arrows, i.e. clockwise) it is easy to see that the tangent turns by an angle
$-\pi$ from each cycle valley to the next cycle peak, and again by an angle
$-\pi$ from each cycle peak to the next cycle valley. Therefore, a cycle
containing $M$ cycle peaks (and hence $M$ cycle valleys) has a rotation angle
$-2\pi M$. On the other hand, Whitney [18, Theorem 2] proved that the rotation
angle for a $C^{1}$ normal closed curve $f$ is

$\gamma(f)\;=\;2\pi(\mu+N^{+}-N^{-})$ (3.1)

where $N^{+}$ (resp. $N^{-}$) is the number of positive (resp. negative)
crossings, and $\mu$ is either $+1$ or $-1$.222 The definition of positive and
negative crossings [18, p. 281] depends on the choice of a starting point on
the curve; if the crossing point is visited first with tangent vector ${\bf
v}_{1}$ and then with tangent vector ${\bf v}_{2}$, the crossing point is
called positive if ${\bf v}_{1}\times{\bf v}_{2}<0$ using the right-hand rule,
and negative if ${\bf v}_{1}\times{\bf v}_{2}>0$ using the right-hand rule.
The hypotheses of [18, Theorem 2] require that the starting point be an
outside starting point, i.e. the whole curve must lies on one side of the
tangent line to the curve at the starting point. That requirement is easily
fulfilled here, e.g. by taking the starting point to be the smallest or
largest element of the cycle. In this situation, [18, Theorem 2] also
specifies explicitly whether $\mu$ is $+1$ or $-1$; in the present case it is
$\mu=-1$. See also Umehara and Yamada [17, pp. 34–38] for an exposition of
Whitney’s proof. They use the term “generic” for what Whitney calls “normal”.
It follows that the number of self-intersections in this cycle, namely
$N^{+}+N^{-}$, equals $M+1$ modulo 2.

Proof of (b).  This is a general property of $C^{1}$ normal closed curves in
the plane that have finitely many mutual intersections, all of which are
transversal double points: in this situation the number of mutual
intersections is even. This intuitively obvious fact goes back at least to
Tait [15, statement III]. For completeness we give a proof:

Let ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ be $C^{1}$ normal closed
curves in the plane; and suppose that ${\mathcal{C}}_{1}$ and
${\mathcal{C}}_{2}$ have finitely many intersections, all of which are all
transversal double points. Consider first the case in which
${\mathcal{C}}_{1}$ is a simple closed curve, i.e. has no self-intersections.
Then the Jordan Curve Theorem tells us that
$\mathbb{R}^{2}\setminus{\mathcal{C}}_{1}$ has two connected components, an
interior and an exterior.333 See e.g. [16] or [14, Section 0.3] for proofs of
the Jordan Curve Theorem.  We put an orientation on ${\mathcal{C}}_{2}$ and
traverse ${\mathcal{C}}_{2}$ from some starting point. Each time
${\mathcal{C}}_{2}$ intersects ${\mathcal{C}}_{1}$, it must either go from the
interior to the exterior of ${\mathcal{C}}_{1}$ or vice versa (because the
intersections are transversal). Since ${\mathcal{C}}_{2}$ returns to its
starting point, the number of intersections between ${\mathcal{C}}_{2}$ and
${\mathcal{C}}_{1}$ must be even.

When ${\mathcal{C}}_{1}$ is not a simple closed curve but has finitely many
self-intersections, we can write it as a union of finitely many simple closed
curves ${\mathcal{C}}_{1}^{i}$ that are disjoint except for intersections at
the self-intersection points of ${\mathcal{C}}_{1}$. (The graph whose vertices
are the self-intersection points and whose edges are the arcs of
${\mathcal{C}}_{1}$ between two successive self-intersections is an Eulerian
graph; and an Eulerian graph can be written as the edge-disjoint union of
cycles.) Then ${\mathcal{C}}_{2}$ has an even number of intersections with
each ${\mathcal{C}}_{1}^{i}$, hence also with ${\mathcal{C}}_{1}$ (since by
hypothesis none of those intersections occur at the self-intersection points
of ${\mathcal{C}}_{1}$).444 Equivalently, the graph $G$ whose vertices are the
self-intersection points and whose edges are the arcs of ${\mathcal{C}}_{1}$
between two successive self-intersections is Eulerian; so its dual $G^{*}$ is
bipartite. Then the closed curve ${\mathcal{C}}_{2}$ must intersect the edges
of $G$ an even number of times.  This completes the proof.

This completes the proof of Lemma 1.1. $\square$

Combinatorial Proof. Let ${\rm cyc}(\sigma)=k$, and let $p_{1},\ldots,p_{k}$
be the sizes of the $k$ cycles of $\sigma$. Then

$n+k\;=\;\sum_{i=1}^{k}(p_{i}+1)\;\equiv\;\\#(\text{cycles of $\sigma$ of even
length})\pmod{2}\;.$ (3.2)

Therefore

$(-1)^{n+k}\;=\;(-1)^{\\#(\text{cycles of $\sigma$ of even length})}\;.$ (3.3)

Here the right-hand side is simply the parity of $\sigma$, usually denoted
$\mathop{\rm sgn}\nolimits(\sigma)$. As is well known (e.g. [11, section
7.4]), the parity of $\sigma$ is also given by

$\mathop{\rm sgn}\nolimits(\sigma)\;=\;(-1)^{{\rm inv}(\sigma)}\;,$ (3.4)

where

${\rm inv}(\sigma)\;\stackrel{{\scriptstyle\rm
def}}{{=}}\;\\#\\{(i,j)\colon\>i<j\textrm{ and }\sigma(i)>\sigma(j)\\}$ (3.5)

is the number of inversions in $\sigma$. We therefore have

$n+k\;\equiv\;{\rm inv}(\sigma)\pmod{2}\;.$ (3.6)

On the other hand, we recall a formula [13, Proposition 2.24] for the number
of inversions in terms of cycle, crossing and nesting statistics:

${\rm inv}\;=\;{\rm cval}+{\rm cdrise}+{\rm cdfall}+{\rm ucross}+{\rm
lcross}+2({\rm unest}+{\rm lnest}+{\rm psnest})\;.$ (3.7)

Combining (3.6) and (3.7) yields

$n+k\;\equiv\;({\rm cval}+{\rm cdrise}+{\rm cdfall})+({\rm ucross}+{\rm
lcross})\pmod{2}\;,$ (3.8)

which can be rewritten as

$k\;\equiv\;({\rm cpeak}+{\rm fix})+({\rm ucross}+{\rm lcross})\pmod{2}$ (3.9)

since $n={\rm cpeak}+{\rm cval}+{\rm cdrise}+{\rm cdfall}+{\rm fix}$. This
proves (LABEL:eq.cyc.formula.a). Then (LABEL:eq.cyc.formula.b) follows because
${\rm cpeak}={\rm cval}$. $\square$

##  4 Results for permutations

We find it convenient to start from the first “master” J-fraction for
permutations [13, Theorem 2.9] and then to specialize.

###  4.1 Master J-fraction

Following [13, Section 2.7], we introduce five infinite families of
indeterminates ${\mbox{{{a}}}}=({{\sf
a}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{b}}}}=({{\sf
b}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{c}}}}=({{\sf
c}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{d}}}}=({{\sf
d}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{e}}}}=({{\sf
e}}_{\ell})_{\ell\geq 0}$ and then define the polynomials

$\displaystyle
P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},\lambda)\;=\;$
$\displaystyle\sum_{\sigma\in{\mathfrak{S}}_{n}}\lambda^{{\rm
cyc}(\sigma)}\prod\limits_{i\in{\rm Cval}(\sigma)}\\!{{\sf a}}_{{\rm
ucross}(i,\sigma),\,{\rm unest}(i,\sigma)}\prod\limits_{i\in{\rm
Cpeak}(\sigma)}\\!\\!{{\sf b}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\;\;\,\prod\limits_{i\in{\rm
Cdfall}(\sigma)}\\!\\!{{\sf c}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\;\prod\limits_{i\in{\rm Cdrise}(\sigma)}\\!\\!{{\sf
d}}_{{\rm ucross}(i,\sigma),\,{\rm unest}(i,\sigma)}\,\prod\limits_{i\in{\rm
Fix}(\sigma)}{{\sf e}}_{{\rm psnest}(i,\sigma)}\;.\quad$ (4.1)

(This is [13, eq. (2.77)] with a factor $\lambda^{{\rm cyc}(\sigma)}$
included.) Then the first master J-fraction for permutations [13, Theorem 2.9]
handles the case $\lambda=1$: it states that the ordinary generating function
of the polynomials
$P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},1)$
has the J-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},1)\>t^{n}\;=\;$
(4.2)

with coefficients

$\gamma_{n}&=\biggl{(}\sum_{\ell=0}^{n-1}{{\sf
c}}_{\ell,n-1-\ell}\biggr{)}\,+\,\biggl{(}\sum_{\ell=0}^{n-1}{{\sf
d}}_{\ell,n-1-\ell}\biggr{)}\,+\,{{\sf e}}_{n}\\\
\beta_{n}=\biggl{(}\sum_{\ell=0}^{n-1}{{\sf
a}}_{\ell,n-1-\ell}\biggr{)}\>\biggl{(}\sum_{\ell=0}^{n-1}{{\sf
b}}_{\ell,n-1-\ell}\biggr{)}$ (4.3)

By Lemma 1.1, we obtain the case $\lambda=-1$ by inserting a factor $-1$ for
each fixed point, for each cycle peak (or alternatively, cycle valley), and
for each lower or upper crossing. We therefore have:

######  Proposition 4.1 (Master J-fraction for permutations, $\lambda=-1$).

The ordinary generating function of the polynomials
$P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},-1)$
has the J-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},-1)\>t^{n}\;=\;$

with coefficients

$\gamma_{n}&=\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
c}}_{\ell,n-1-\ell}\biggr{)}\,+\,\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
d}}_{\ell,n-1-\ell}\biggr{)}\,-\,{{\sf e}}_{n}\\\
\beta_{n}=-\,\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
a}}_{\ell,n-1-\ell}\biggr{)}\>\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
b}}_{\ell,n-1-\ell}\biggr{)}$ (4.5)

###  4.2 $\bm{p,q}$ J-fraction

Consider now the polynomial [13, eq. (2.92)]

$\displaystyle
P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},{\mathbf{w}},p_{+1},p_{+2},p_{-1},p_{-2},q_{+1},q_{+2},q_{-1},q_{-2},s,\lambda)\;=\;$
$\displaystyle\qquad\sum_{\sigma\in{\mathfrak{S}}_{n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}{\mathbf{w}}^{{\mathbf{fix}}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\>p_{+1}^{{\rm ucrosscval}(\sigma)}p_{+2}^{{\rm
ucrosscdrise}(\sigma)}p_{-1}^{{\rm lcrosscpeak}(\sigma)}p_{-2}^{{\rm
lcrosscdfall}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\>q_{+1}^{{\rm unestcval}(\sigma)}q_{+2}^{{\rm
unestcdrise}(\sigma)}q_{-1}^{{\rm lnestcpeak}(\sigma)}q_{-2}^{{\rm
lnestcdfall}(\sigma)}s^{{\rm psnest}(\sigma)}\lambda^{{\rm cyc}(\sigma)}\;,$
(4.6)

where the various statistics have been defined in [13, Sections 2.3 and 2.5].
In order to distinguish records and antirecords, we use the following general
fact about permutations [13, Lemma 2.10]:

  * (a)

If $i$ is a cycle valley or cycle double rise, then $i$ is a record if and
only if ${\rm unest}(i,\sigma)=0$; and in this case it is an exclusive record.

  * (b)

If $i$ is a cycle peak or cycle double fall, then $i$ is an antirecord if and
only if ${\rm lnest}(i,\sigma)=0$; and in this case it is an exclusive
antirecord.

It follows that the polynomial (4.6) is obtained from (4.1) by making the
specializations [13, eq. (2.81)]

${{\sf
a}}_{\ell,\ell^{\prime}}&=p_{+1}^{\ell}q_{+1}^{\ell^{\prime}}\,\times\,\begin{cases}y_{1}&\textrm{if
$\ell^{\prime}=0$}\\\ v_{1}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
b}}_{\ell,\ell^{\prime}}=p_{-1}^{\ell}q_{-1}^{\ell^{\prime}}\,\times\,\begin{cases}x_{1}&\textrm{if
$\ell^{\prime}=0$}\\\ u_{1}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
c}}_{\ell,\ell^{\prime}}=p_{-2}^{\ell}q_{-2}^{\ell^{\prime}}\,\times\,\begin{cases}x_{2}&\textrm{if
$\ell^{\prime}=0$}\\\ u_{2}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
d}}_{\ell,\ell^{\prime}}=p_{+2}^{\ell}q_{+2}^{\ell^{\prime}}\,\times\,\begin{cases}y_{2}&\textrm{if
$\ell^{\prime}=0$}\\\ v_{2}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf e}}_{\ell}=s^{\ell}w_{\ell}$ (4.7)

Making these specializations in Proposition 4.1 — or equivalently, attaching a
minus sign to the variables $x_{1},u_{1},p_{+1},p_{+2},p_{-1},p_{-2},w_{i}$ in
[13, Theorem 2.7] — we obtain:

######  Proposition 4.2 ($p,q$ J-fraction for permutations, $\lambda=-1$).

The ordinary generating function of the polynomials (4.6) at $\lambda=-1$ has
the J-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},{\mathbf{w}},p_{+1},p_{+2},p_{-1},p_{-2},q_{+1},q_{+2},q_{-1},q_{-2},s,-1)\>t^{n}\;=\;$
(4.8)

with coefficients

$\gamma_{0}&=-w_{0}{}\\\
\gamma_{n}=\scalebox{0.87}{$((-p_{-2})^{n-1}x_{2}+q_{-2}\,[n-1]_{-p_{-2},q_{-2}}u_{2})\>+\>((-p_{+2})^{n-1}y_{2}+q_{+2}\,[n-1]_{-p_{+2},q_{+2}}v_{2})\>-\>s^{n}w_{n}$}\\\
\hskip 267.39877pt\quad\hbox{for $n\geq 1$}{}\\\
\beta_{n}=\scalebox{0.87}{$-\,((-p_{-1})^{n-1}x_{1}+q_{-1}\,[n-1]_{-p_{-1},q_{-1}}u_{1})\>((-p_{+1})^{n-1}y_{1}+q_{+1}\,[n-1]_{-p_{+1},q_{+1}}v_{1})$}{}$
(4.9)

###  4.3 Simple J-fraction

And finally, we can obtain the polynomials without crossing and nesting
statistics,

$\displaystyle
P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},{\mathbf{w}},\lambda)\;=\;$
$\displaystyle\qquad\sum_{\sigma\in{\mathfrak{S}}_{n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}{\mathbf{w}}^{{\mathbf{fix}}(\sigma)}\lambda^{{\rm
cyc}(\sigma)}\;,$ (4.10)

by setting $p_{+1}=p_{+2}=p_{-1}=p_{-2}=q_{+1}=q_{+2}=q_{-1}=q_{-2}=s=1$ in
(4.6). Making this same specialization in Proposition 4.2 and observing that

$[n-1]_{-1,1}\;=\;\begin{cases}1&\textrm{if $n$ is even}\\\ 0&\textrm{if $n$
is odd}\end{cases}$ (4.11)

we obtain:

######  Proposition 4.3 (Simple J-fraction for permutations, $\lambda=-1$).

The ordinary generating function of the polynomials (4.10) at $\lambda=-1$ has
the J-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},{\mathbf{w}},-1)\>t^{n}\;=\;$
$\displaystyle\\!\\!\\!\\!\cfrac{1}{1+w_{0}t+\cfrac{x_{1}y_{1}t^{2}}{1-(x_{2}\\!+\\!y_{2}\\!-\\!w_{1})t+\cfrac{(x_{1}\\!-\\!u_{1})(y_{1}\\!-\\!v_{1})t^{2}}{1-(-x_{2}\\!+\\!u_{2}\\!-\\!y_{2}\\!+\\!v_{2}\\!-\\!w_{2})t+\cfrac{x_{1}y_{1}t^{2}}{1-\cdots}}}}$
(4.12)

with coefficients

$\gamma_{0}&=-w_{0}{}\\\ \gamma_{n}=\begin{cases}x_{2}+y_{2}-w_{n}&\textrm{if
$n$ is odd}\\\ -x_{2}+u_{2}-y_{2}+v_{2}-w_{n}&\textrm{if $n$ is even and $\geq
2$}\end{cases}{}\\\ \beta_{n}=\begin{cases}-x_{1}y_{1}&\textrm{if $n$ is
odd}\\\ -(x_{1}-u_{1})(y_{1}-v_{1})&\textrm{if $n$ is even}\end{cases}{}$
(4.13)

###  4.4 Corollary for cycle-alternating permutations

We recall [6, 13, 4] that a cycle-alternating permutation is a permutation of
$[2n]$ that has no cycle double rises, cycle double falls, or fixed points;
Deutsch and Elizalde [6, Proposition 2.2] showed that the number of cycle-
alternating permutations of $[2n]$ is the secant number $E_{2n}$ (see also
Dumont [7, pp. 37, 40] and Biane [2, section 6]). In this subsection, we will
obtain continued fractions for cycle-alternating permutations at $\lambda=-1$
by specializing our master J-fraction (Proposition 4.1) to suppress cycle
double rises, cycle double falls and fixed points, and then using [4, Lemma
4.2] to interpret the parity of cycle peaks and cycle valleys in terms of
crossings and nestings.

Let $P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},\lambda)$ denote the polynomial (4.1)
specialized to ${\mbox{{{c}}}}={\mbox{{{d}}}}={\mbox{{{e}}}}={\bm{0}}$; it
enumerates cycle-alternating permutations according to the index-refined
crossing and nesting statistics associated to its cycle peaks and cycle
valleys. Note that $P_{n}$ is nonvanishing only for even $n$. The J-fraction
of Proposition 4.1 then becomes an S-fraction in the variable $t^{2}$; after
changing $t^{2}$ to $t$, we have:

######  Proposition 4.4 (Master S-fraction for cycle-alternating permutations,
$\lambda=-1$).

The ordinary generating function of the polynomials
$P_{2n}({\mbox{{{a}}}},{\mbox{{{b}}}},-1)$ has the S-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{2n}({\mbox{{{a}}}},{\mbox{{{b}}}},-1)\>t^{n}\;=\;\cfrac{1}{1+\cfrac{{{\sf
a}}_{00}{{\sf b}}_{00}t}{1+\cfrac{({{\sf a}}_{01}-{{\sf a}}_{10})({{\sf
b}}_{01}-{{\sf b}}_{10})t}{1+\cfrac{({{\sf a}}_{02}-{{\sf a}}_{11}+{{\sf
a}}_{20})({{\sf b}}_{02}-{{\sf b}}_{11}+{{\sf b}}_{20})t}{1-\cdots}}}}$

with coefficients

$\alpha_{n}\;=\;-\,\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
a}}_{\ell,n-1-\ell}\biggr{)}\>\biggl{(}\sum_{\ell=0}^{n-1}(-1)^{\ell}\,{{\sf
b}}_{\ell,n-1-\ell}\biggr{)}\;.$ (4.15)

We can use this master S-fraction to obtain a continued fraction that
distinguishes cycle peaks and cycle valleys according to their parity. To do
this, we use [4, Lemma 4.2]:

######  Lemma 4.5 (Key lemma from [4]).

If $\sigma$ is a cycle-alternating permutation of $[2n]$, then

$\hbox{\rm cycle valleys:}&\\!\\!{\rm ucross}(i,\sigma)\,+\,{\rm
unest}(i,\sigma)\;=\;i-1\>\pmod{2}\\\ \hbox{\rm cycle peaks:}\\!\\!{\rm
lcross}(i,\sigma)\,+\,{\rm lnest}(i,\sigma)\;=\;i\>\pmod{2}$ (4.16)

for all $i\in[2n]$.

Consider now the polynomials

$\displaystyle Q_{n}(x_{\rm e},y_{\rm e},u_{\rm e},v_{\rm e},x_{\rm o},y_{\rm
o},u_{\rm o},v_{\rm
o},p_{-1},p_{-2},p_{+1},p_{+2},q_{-1},q_{-2},q_{+1},q_{+2},\lambda)\;=\;$
$\displaystyle\qquad\sum_{\sigma\in{\mathfrak{S}}^{\rm ca}_{2n}}x_{\rm
e}^{{\rm eareccpeakeven}(\sigma)}y_{\rm e}^{{\rm ereccvaleven}(\sigma)}u_{\rm
e}^{{\rm nrcpeakeven}(\sigma)}v_{\rm e}^{{\rm
nrcvaleven}(\sigma)}\>\times\qquad\qquad$ $\displaystyle\qquad\qquad\;\,x_{\rm
o}^{{\rm eareccpeakodd}(\sigma)}y_{\rm o}^{{\rm ereccvalodd}(\sigma)}u_{\rm
o}^{{\rm nrcpeakodd}(\sigma)}v_{\rm o}^{{\rm
nrcvalodd}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\;\,p_{-1}^{{\rm
lcrosscpeakeven}(\sigma)}p_{-2}^{{\rm lcrosscpeakodd}(\sigma)}p_{+1}^{{\rm
ucrosscvalodd}(\sigma)}p_{+2}^{{\rm
ucrosscvaleven}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\;\,q_{-1}^{{\rm
lnestcpeakeven}(\sigma)}q_{-2}^{{\rm lnestcpeakodd}(\sigma)}q_{+1}^{{\rm
unestcvalodd}(\sigma)}q_{+2}^{{\rm unestcvaleven}(\sigma)}\lambda^{{\rm
cyc}(\sigma)}\;,$ (4.17)

where the various statistics are defined as

${\rm eareccpeakeven}(\sigma)\;=\;|{\rm Eareccpeakeven}(\sigma)|\;=\;|{\rm
Arec}(\sigma)\cap{\rm Cpeak}(\sigma)\cap{\rm Even}|$ (4.18) ${\rm
lcrosscpeakeven}(\sigma)\;=\;\sum_{k\in{\rm Cpeak}(\sigma)\,\cap\,{\rm
Even}}{\rm lcross}(k,\sigma)$ (4.19)

and likewise for the others. These polynomials are the same as the polynomials
[4, eq. (4.29)] except for the extra factor $\lambda^{{\rm cyc}(\sigma)}$. As
before, we use [13, Lemma 2.10] to distinguish records and antirecords; we
also use Lemma 4.5 to distinguish cycle peaks and cycle valleys according to
their parity. It follows that the polynomials (4.17) can be obtained from the
master polynomials $P_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},\lambda)$ by making
the specializations [4, eq. (4.33)]

${{\sf a}}_{\ell,\ell^{\prime}}&=\begin{cases}p_{+1}^{\ell}y_{\rm
o}&\textrm{if $\ell^{\prime}=0$ and $\ell+\ell^{\prime}$ is even}\\\
p_{+1}^{\ell}q_{+1}^{\ell^{\prime}}v_{\rm o}&\textrm{if $\ell^{\prime}\geq 1$
and $\ell+\ell^{\prime}$ is even}\\\ p_{+2}^{\ell}y_{\rm e}&\textrm{if
$\ell^{\prime}=0$ and $\ell+\ell^{\prime}$ is odd}\\\
p_{+2}^{\ell}q_{+2}^{\ell^{\prime}}v_{\rm e}&\textrm{if $\ell^{\prime}\geq 1$
and $\ell+\ell^{\prime}$ is odd}\end{cases}\\\ {{\sf
b}}_{\ell,\ell^{\prime}}=\begin{cases}p_{-1}^{\ell}x_{\rm e}&\textrm{if
$\ell^{\prime}=0$ and $\ell+\ell^{\prime}$ is even}\\\
p_{-1}^{\ell}q_{-1}^{\ell^{\prime}}u_{\rm e}&\textrm{if $\ell^{\prime}\geq 1$
and $\ell+\ell^{\prime}$ is even}\\\ p_{-2}^{\ell}x_{\rm o}&\textrm{if
$\ell^{\prime}=0$ and $\ell+\ell^{\prime}$ is odd}\\\
p_{-2}^{\ell}q_{-2}^{\ell^{\prime}}u_{\rm o}&\textrm{if $\ell^{\prime}\geq 1$
and $\ell+\ell^{\prime}$ is odd}\end{cases}$ (4.20)

Inserting these specializations into Proposition 4.4, we obtain:

######  Proposition 4.6 ($p,q$ S-fraction for cycle-alternating permutations,
$\lambda=-1$).

The ordinary generating function of the polynomials (4.17) at $\lambda=-1$ has
the S-type continued fraction

$\sum_{n=0}^{\infty}Q_{n}(x_{\rm e},y_{\rm e},u_{\rm e},v_{\rm e},x_{\rm
o},y_{\rm o},u_{\rm o},v_{\rm
o},p_{-1},p_{-2},p_{+1},p_{+2},q_{-1},q_{-2},q_{+1},q_{+2},-1)\>t^{n}\\\
\;=\;\cfrac{1}{1+\cfrac{x_{\rm e}y_{\rm o}t}{1+\cfrac{(-p_{-2}x_{\rm
o}\\!+\\!q_{-2}u_{\rm o})(-p_{+2}y_{\rm e}\\!+\\!q_{+2}v_{\rm
e})t}{1+\cfrac{(p_{-1}^{2}x_{\rm e}\\!+\\!q_{-1}[2]_{-p_{-1},q_{-1}}u_{\rm
e})(p_{+1}^{2}y_{\rm o}\\!+\\!q_{+1}[2]_{-p_{+1},q_{+1}}v_{\rm
o})t}{1-\cdots}}}}$ (4.21)

with coefficients

$\alpha_{2k-1}&=-(p_{-1}^{2k-2}x_{\rm e}+q_{-1}[2k-2]_{-p_{-1},q_{-1}}u_{\rm
e})\>(p_{+1}^{2k-2}y_{\rm o}+q_{+1}[2k-2]_{-p_{+1},q_{+1}}v_{\rm o})\\\
\mbox{}\\\ \alpha_{2k}=-(-p_{-2}^{2k-1}x_{\rm
o}+q_{-2}[2k-1]_{-p_{-2},q_{-2}}u_{\rm o})\>(-p_{+2}^{2k-1}y_{\rm
e}+q_{+2}[2k-1]_{-p_{+2},q_{+2}}v_{\rm e})\\\ \mbox{}$ (4.22)

Finally, denote by $Q_{n}(x_{\rm e},y_{\rm e},u_{\rm e},v_{\rm e},x_{\rm
o},y_{\rm o},u_{\rm o},v_{\rm o},\lambda)$ the polynomial (4.17) specialized
to $p_{+1}=p_{+2}=p_{-1}=p_{-2}=q_{+1}=q_{+2}=q_{-1}=q_{-2}=1$. Setting
$\lambda=-1$, we obtain:

######  Proposition 4.7 (Simple S-fraction for cycle-alternating permutations,
$\lambda=-1$).

The ordinary generating function of the polynomials $Q_{n}(x_{\rm e},y_{\rm
e},u_{\rm e},v_{\rm e},x_{\rm o},y_{\rm o},u_{\rm o},v_{\rm o},-1)$ has the
S-type continued fraction

$\sum_{n=0}^{\infty}Q_{n}(x_{\rm e},y_{\rm e},u_{\rm e},v_{\rm e},x_{\rm
o},y_{\rm o},u_{\rm o},v_{\rm o},-1)\>t^{n}\;=\;\cfrac{1}{1+\cfrac{x_{\rm
e}y_{\rm o}t}{1+\cfrac{(x_{\rm o}\\!-\\!u_{\rm o})(y_{\rm e}\\!-\\!v_{\rm
e})t}{1+\cfrac{x_{\rm e}y_{\rm o}t}{1-\cdots}}}}$ (4.23)

with coefficients

$\alpha_{2k-1}&=-x_{\rm e}y_{\rm o}\\\ \alpha_{2k}=-(x_{\rm o}-u_{\rm
o})\>(y_{\rm e}-v_{\rm e})$ (4.24)

This proves the continued fraction that was conjectured in [4, eq. (A.6)].

##  5 Results for D-permutations

We recall [8, 10, 9, 3] that a D-permutation is a permutation of $[2n]$
satisfying ${2k-1\leq\sigma(2k-1)}$ and ${2k\geq\sigma(2k)}$ for all $k$;
D-permutations provide a combinatorial model for the Genocchi and median
Genocchi numbers. We write ${\mathfrak{D}}_{2n}$ for the set of D-permutations
of $[2n]$.

We proceed in the same way as in the preceding section, beginning with the
“master” T-fraction and then obtaining the others by specialization.

###  5.1 Master T-fraction

Following [3, Section 3.4], we introduce six infinite families of
indeterminates ${\mbox{{{a}}}}=({{\sf
a}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{b}}}}=({{\sf
b}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{c}}}}=({{\sf
c}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{d}}}}=({{\sf
d}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{e}}}}=({{\sf
e}}_{\ell})_{\ell\geq 0}$, ${\mbox{{{f}}}}=({{\sf f}}_{\ell})_{\ell\geq 0}$
and then define the polynomials

$\displaystyle
Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},\lambda)\;=\;$
$\displaystyle\sum_{\sigma\in{\mathfrak{D}}_{2n}}\lambda^{{\rm
cyc}(\sigma)}\prod\limits_{i\in{\rm Cval}(\sigma)}\\!{{\sf a}}_{{\rm
ucross}(i,\sigma),\,{\rm unest}(i,\sigma)}\prod\limits_{i\in{\rm
Cpeak}(\sigma)}\\!\\!{{\sf b}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\;\;\;\,\prod\limits_{i\in{\rm
Cdfall}(\sigma)}\\!\\!{{\sf c}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\;\prod\limits_{i\in{\rm Cdrise}(\sigma)}\\!\\!{{\sf
d}}_{{\rm ucross}(i,\sigma),\,{\rm unest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\;\;\,\prod\limits_{i\in{\rm
Evenfix}(\sigma)}\\!\\!\\!{{\sf e}}_{{\rm
psnest}(i,\sigma)}\;\prod\limits_{i\in{\rm Oddfix}(\sigma)}\\!\\!\\!{{\sf
f}}_{{\rm psnest}(i,\sigma)}\;.\quad$ (5.1)

(This is [3, eq. (3.30)] with a factor $\lambda^{{\rm cyc}(\sigma)}$
included.) Then the first master T-fraction for D-permutations [3, Theorem
3.11] handles the case $\lambda=1$: it states that the ordinary generating
function of the polynomials
$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},1)$
has the T-type continued fraction

$\sum_{n=0}^{\infty}Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},1)\>t^{n}\;=\;\scalebox{0.95}{$\cfrac{1}{1-{{\sf
e}}_{0}{{\sf f}}_{0}t-\cfrac{{{\sf a}}_{00}{{\sf b}}_{00}t}{1-\cfrac{({{\sf
c}}_{00}+{{\sf e}}_{1})({{\sf d}}_{00}+{{\sf f}}_{1})t}{1-\cfrac{({{\sf
a}}_{01}+{{\sf a}}_{10})({{\sf b}}_{01}+{{\sf b}}_{10})t}{1-\cfrac{({{\sf
c}}_{01}+{{\sf c}}_{10}+{{\sf e}}_{2})({{\sf d}}_{01}+{{\sf d}}_{10}+{{\sf
f}}_{2})t}{1-\cdots}}}}}$}$ (5.2)

with coefficients

$\alpha_{2k-1}&=\biggl{(}\sum_{\ell=0}^{k-1}{{\sf
a}}_{\ell,k-1-\ell}\biggr{)}\biggl{(}\sum_{\ell=0}^{k-1}{{\sf
b}}_{\ell,k-1-\ell}\biggr{)}\\\ \alpha_{2k}=\biggl{(}{{\sf
e}}_{k}\,+\,\sum_{\ell=0}^{k-1}{{\sf
c}}_{\ell,k-1-\ell}\biggr{)}\biggl{(}{{\sf
f}}_{k}\,+\,\sum_{\ell=0}^{k-1}{{\sf d}}_{\ell,k-1-\ell}\biggr{)}\\\
\delta_{1}={{\sf e}}_{0}{{\sf f}}_{0}\\\ \delta_{n}=0\qquad\hbox{for $n\geq
2$}$ (5.3)

By Lemma 1.1, we obtain the case $\lambda=-1$ by inserting a factor $-1$ for
each even or odd fixed point, for each cycle peak (or alternatively, cycle
valley), and for each lower or upper crossing. We therefore have:

######  Proposition 5.1 (Master T-fraction for D-permutations, $\lambda=-1$).

The ordinary generating function of the polynomials
$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},-1)$
has the T-type continued fraction

$\sum_{n=0}^{\infty}Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},-1)\>t^{n}\;=\;\scalebox{0.95}{$\cfrac{1}{1-{{\sf
e}}_{0}{{\sf f}}_{0}t+\cfrac{{{\sf a}}_{00}{{\sf b}}_{00}t}{1-\cfrac{({{\sf
c}}_{00}-{{\sf e}}_{1})({{\sf d}}_{00}-{{\sf f}}_{1})t}{1+\cfrac{({{\sf
a}}_{01}-{{\sf a}}_{10})({{\sf b}}_{01}-{{\sf b}}_{10})t}{1-\cfrac{({{\sf
c}}_{01}-{{\sf c}}_{10}-{{\sf e}}_{2})({{\sf d}}_{01}-{{\sf d}}_{10}-{{\sf
f}}_{2})t}{1-\cdots}}}}}$}$ (5.4)

with coefficients

$\alpha_{2k-1}&=-\,\biggl{(}\sum_{\ell=0}^{k-1}(-1)^{\ell}\,{{\sf
a}}_{\ell,k-1-\ell}\biggr{)}\biggl{(}\sum_{\ell=0}^{k-1}(-1)^{\ell}\,{{\sf
b}}_{\ell,k-1-\ell}\biggr{)}\\\ \alpha_{2k}=\biggl{(}-{{\sf
e}}_{k}\,+\,\sum_{\ell=0}^{k-1}(-1)^{\ell}\,{{\sf
c}}_{\ell,k-1-\ell}\biggr{)}\biggl{(}-{{\sf
f}}_{k}\,+\,\sum_{\ell=0}^{k-1}(-1)^{\ell}\,{{\sf
d}}_{\ell,k-1-\ell}\biggr{)}\\\ \delta_{1}={{\sf e}}_{0}{{\sf f}}_{0}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (5.5)

###  5.2 $\bm{p,q}$ T-fraction

Consider now the polynomial

$\displaystyle P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm
o},p_{-1},p_{-2},p_{+1},p_{+2},q_{-1},q_{-2},q_{+1},q_{+2},s_{\rm e},s_{\rm
o},\lambda)\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>p_{-1}^{{\rm
lcrosscpeak}(\sigma)}p_{-2}^{{\rm lcrosscdfall}(\sigma)}p_{+1}^{{\rm
ucrosscval}(\sigma)}p_{+2}^{{\rm ucrosscdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>q_{-1}^{{\rm
lnestcpeak}(\sigma)}q_{-2}^{{\rm lnestcdfall}(\sigma)}q_{+1}^{{\rm
unestcval}(\sigma)}q_{+2}^{{\rm unestcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>s_{\rm e}^{{\rm epsnest}(\sigma)}s_{\rm
o}^{{\rm opsnest}(\sigma)}\lambda^{{\rm cyc}(\sigma)}\;.$ (5.6)

(This is [3, eq. (3.22)] with a factor $\lambda^{{\rm cyc}(\sigma)}$
included.) The various statistics have been defined in [3, Sections 2.7 and
2.8 and eq. (3.22)]. This polynomial is obtained from (5.1) by making the
specializations [3, eqs. (6.40)-(6.45)]

${{\sf
a}}_{\ell,\ell^{\prime}}&=p_{+1}^{\ell}q_{+1}^{\ell^{\prime}}\,\times\,\begin{cases}y_{1}&\textrm{if
$\ell^{\prime}=0$}\\\ v_{1}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
b}}_{\ell,\ell^{\prime}}=p_{-1}^{\ell}q_{-1}^{\ell^{\prime}}\,\times\,\begin{cases}x_{1}&\textrm{if
$\ell^{\prime}=0$}\\\ u_{1}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
c}}_{\ell,\ell^{\prime}}=p_{-2}^{\ell}q_{-2}^{\ell^{\prime}}\,\times\,\begin{cases}x_{2}&\textrm{if
$\ell^{\prime}=0$}\\\ u_{2}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf
d}}_{\ell,\ell^{\prime}}=p_{+2}^{\ell}q_{+2}^{\ell^{\prime}}\,\times\,\begin{cases}y_{2}&\textrm{if
$\ell^{\prime}=0$}\\\ v_{2}&\textrm{if $\ell^{\prime}\geq 1$}\end{cases}\\\
{{\sf e}}_{k}=\begin{cases}z_{\rm e}&\textrm{if $k=0$}\\\\[2.84526pt] s_{\rm
e}^{k}w_{\rm e}&\textrm{if $k\geq 1$}\end{cases}\\\ {{\sf
f}}_{k}=\begin{cases}z_{\rm o}&\textrm{if $k=0$}\\\\[2.84526pt] s_{\rm
o}^{k}w_{\rm o}&\textrm{if $k\geq 1$}\end{cases}$ (5.7)

Making these specializations in Proposition 5.1 — or equivalently, attaching a
minus sign to the variables $x_{1},u_{1},p_{+1},p_{+2},p_{-1},p_{-2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o}$ in [3, Theorem 3.9] — we obtain:

######  Proposition 5.2 ($p,q$ T-fraction for D-permutations, $\lambda=-1$).

The ordinary generating function of the polynomials (5.6) at $\lambda=-1$ has
the T-type continued fraction

(5.8)

with coefficients

$\alpha_{2k-1}&=\scalebox{0.85}{$-\bigl{(}(-p_{-1})^{k-1}x_{1}+q_{-1}[k-1]_{-p_{-1},q_{-1}}u_{1}\bigr{)}\>\bigl{(}(-p_{+1})^{k-1}y_{1}+q_{+1}[k-1]_{-p_{+1},q_{+1}}v_{1}\bigr{)}$}\\\
\alpha_{2k}=\scalebox{0.85}{$\bigl{(}(-p_{-2})^{k-1}x_{2}+q_{-2}[k-1]_{-p_{-2},q_{-2}}u_{2}-s_{\rm
e}^{k}w_{\rm
e}\bigr{)}\>\bigl{(}(-p_{+2})^{k-1}y_{2}+q_{+2}[k-1]_{-p_{+2},q_{+2}}v_{2}-s_{\rm
o}^{k}w_{\rm o}\bigr{)}$}\\\ \\\ \delta_{1}=z_{\rm e}z_{\rm o}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (5.9)

###  5.3 Simple T-fraction

Finally, denote by
$P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm e},w_{\rm
o},z_{\rm e},z_{\rm o},\lambda)$ the polynomial (5.6) specialized to
$p_{+1}=p_{+2}=p_{-1}=p_{-2}=q_{+1}=q_{+2}=q_{-1}=q_{-2}=s_{\rm e}=s_{\rm
o}=1$. This polynomial was introduced in [3, eq. (4.2)]. Making this same
specialization in Proposition 5.2 and using (4.11), we obtain:

######  Proposition 5.3 (Simple T-fraction for D-permutations, $\lambda=-1$).

The ordinary generating function of the polynomials
$P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm e},w_{\rm
o},z_{\rm e},z_{\rm o},-1)$ has the T-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},-1)\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-z_{\rm e}z_{\rm
o}\,t+\cfrac{x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!-\\!w_{\rm
e})(y_{2}\\!-\\!w_{\rm
o})\,t}{1+\cfrac{(x_{1}\\!-\\!u_{1})(y_{1}\\!-\\!v_{1})\,t}{1-\cfrac{(x_{2}\\!-\\!u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!-\\!v_{2}\\!+\\!w_{\rm
o})\,t}{1+\cfrac{x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!-\\!w_{\rm
e})(y_{2}\\!-\\!w_{\rm o})\,t}{1-\cdots}}}}}}}$ (5.10)

with coefficients

$\alpha_{2k-1}&=\begin{cases}-x_{1}y_{1}&\textrm{if $k$ is odd}\\\
-(x_{1}-u_{1})(y_{1}-v_{1})&\textrm{if $k$ is even}\end{cases}\\\
\alpha_{2k}=\begin{cases}(x_{2}-w_{\rm e})(y_{2}-w_{\rm o})&\textrm{if $k$ is
odd}\\\ (x_{2}-u_{2}+w_{\rm e})(y_{2}-v_{2}+w_{\rm o})&\textrm{if $k$ is
even}\end{cases}\\\ \delta_{1}=z_{\rm e}z_{\rm o}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (5.11)

Finally, as a special case of Proposition 5.3, we can obtain a J-fraction that
was conjectured in [3, Appendix, case $\lambda=-1$]. It suffices to specialize
the polynomials $P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},\lambda)$ by setting $x_{1}=x_{2}=z_{\rm
e}=z_{\rm o}=x$, ${y_{1}=y_{2}=y}$, and $u_{1}=u_{2}=v_{1}=v_{2}=w_{\rm
e}=w_{\rm o}=1$; this yields the polynomials

$P_{n}(x,y,\lambda)\;=\;\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
arec}(\sigma)}y^{{\rm erec}(\sigma)}\lambda^{{\rm cyc}(\sigma)}$ (5.12)

that were introduced in [3, eqs. (4.1) and (A.1)]. Inserting this
specialization in Proposition 5.3 gives, for $\lambda=-1$, a T-fraction with
coefficients

$\alpha_{2k-1}&=\begin{cases}-xy&\textrm{if $k$ is odd}\\\
-(x-1)(y-1)&\textrm{if $k$ is even}\end{cases}\\\
\alpha_{2k}=\begin{cases}(x-1)(y-1)&\textrm{if $k$ is odd}\\\ xy&\textrm{if
$k$ is even}\end{cases}\\\ \delta_{1}=x^{2}\\\ \delta_{n}=0\qquad\hbox{for
$n\geq 2$}$ (5.13)

Using the even contraction for T-fractions with
$\delta_{2}=\delta_{4}=\delta_{6}=\ldots=0$ [3, Proposition 2.1], we can
rewrite this as a J-fraction:

######  Corollary 5.4.

The ordinary generating function of the polynomials (5.12) has the J-type
continued fraction

$\sum_{n=0}^{\infty}P_{n}(x,y,-1)\;=\;\cfrac{1}{1-x(x\\!-\\!y)\,t+\cfrac{xy\>(x-1)(y-1)\,t^{2}}{1+\cfrac{xy\>(x-1)(y-1)\,t^{2}}{1+\cfrac{xy\>(x-1)(y-1)\,t^{2}}{1+\cdots}}}}$
(5.14)

with coefficients

$\gamma_{0}&=x(x-y)\\\ \gamma_{n}=0\quad\hbox{for $n\geq 1$}\\\
\beta_{n}=-xy(x-1)(y-1)$ (5.15)

This J-fraction was conjectured in [3, Appendix, case $\lambda=-1$].

## Acknowledgments

One of us (B.D.) wishes to thank Jakob Stein for helpful discussions
concerning the topology of the plane.

## References

  * [1] H. Alencar, W. Santos and G. Silva Neto, Differential Geometry of Plane Curves, Student Mathematical Library, vol. 96 (Providence RI, American Mathematical Society, 2022).
  * [2] P. Biane, Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, European J. Combin. 14, 277–284 (1993).
  * [3] B. Deb and A.D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, preprint (December 2022), arXiv:2212.07232 [math.CO].
  * [4] B. Deb and A.D. Sokal, Continued fractions for cycle-alternating permutations preprint (April 2023), arXiv:2304.06545 [math.CO].
  * [5] A. de Médicis and X.G. Viennot, Moments des $q$-polynômes de Laguerre et la bijection de Foata–Zeilberger, Adv. Appl. Math. 15, 262–304 (1994).
  * [6] E. Deutsch and S. Elizalde, Cycle-up-down permutations, Australas. J. Combin. 50, 187–199 (2011).
  * [7] D. Dumont, Pics de cycle et dérivées partielles, Séminaire Lotharingien de Combinatoire 13, article B13a (1986).
  * [8] A.L. Lazar, The homogenized Linial arrangement and its consequences in enumerative combinatorics, Ph.D. thesis, University of Miami (August 2020), https://scholarship.miami.edu/discovery/delivery/01UOML_INST:ResearchRepository/12367619000002976?l#13367618990002976
  * [9] A. Lazar, Ferrers graphs, D-permutations, and surjective staircases, Ramanujan J. 60, 391–426 (2023).
  * [10] A. Lazar and M.L. Wachs, The homogenized Linial arrangement and Genocchi numbers, Combin. Theory 2, issue 1, paper no. 2 (2022), 34 pp.
  * [11] N.A. Loehr, Combinatorics, 2nd ed. (CRC Press, Boca Raton, FL, 2018).
  * [12] H. Shin and J. Zeng, The $q$-tangent and $q$-secant numbers via continued fractions, European J. Combin. 31, 1689–1705 (2010).
  * [13] A.D. Sokal and J. Zeng, Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions, Adv. Appl. Math. 138, 102341 (2022).
  * [14] J. Stillwell, Classical Topology and Combinatorial Group Theory, 2nd ed. (Springer-Verlag, New York, 1993).
  * [15] P.G. Tait, Some elementary properties of closed plane curves, Messenger of Mathematics (2) 6, 132–133 (1877). [Reprinted in P.G. Tait, Scientific Papers, vol. 1 (University Press, Cambridge, 1898), pp. 270–272. Available on-line at http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-99438 or https://babel.hathitrust.org/cgi/pt?id=hvd.32044080804735&view=1up&seq=298]
  * [16] H. Tverberg, A proof of the Jordan curve theorem, Bull. London Math. Soc. 12, 34–38 (1980).
  * [17] M. Umehara and K. Yamada, Differential Geometry of Curves and Surfaces, translated from the Japanese by W. Rossman (World Scientific, Singapore, 2017).
  * [18] H. Whitney, On regular closed curves in the plane, Compositio Math. 4, 276–284 (1937).


#  Turán number for bushes

Zoltán Füredi Alfréd Rényi Institute of Mathematics, Budapest, Hungary.
E-mail<EMAIL_ADDRESS>Research partially supported by National
Research, Development and Innovation Office NKFIH grants 132696 and 133819.
Alexandr Kostochka University of Illinois at Urbana-Champaign, Urbana, IL
61801 and Sobolev Institute of Mathematics, Novosibirsk 630090, Russia.
E-mail<EMAIL_ADDRESS>Research supported in part by NSF grant
DMS-2153507 and NSF RTG grant DMS-1937241.

###### Abstract

Let $a,b\in{\bf Z}^{+}$, $r=a+b$, and let $T$ be a tree with parts
$U=\\{u_{1},u_{2},\dots,u_{s}\\}$ and $V=\\{v_{1},v_{2},\dots,v_{t}\\}$. Let
$U_{1},\dots,U_{s}$ and $V_{1},\dots,V_{t}$ be disjoint sets, such that
$|U_{i}|=a$ and $|V_{j}|=b$ for all $i,j$. The $(a,b)$-blowup of $T$ is the
$r$-uniform hypergraph with edge set ${\\{U_{i}\cup V_{j}:u_{i}v_{j}\in
E(T)\\}.}$

We use the $\Delta$-systems method to prove the following Turán-type result.
Suppose $a,b,{s}\in{\bf Z}^{+}$, $r=a+b\geq 3$, $a\geq 2$, and $T$ is a fixed
tree of diameter $4$ in which the degree of the center vertex is ${s}$. Then
there exists a $C=C(r,{s},T)>0$ such that $|\mathcal{H}|\leq({s}-1){n\choose
r-1}+Cn^{r-2}$ for every $n$-vertex $r$-uniform hypergraph $\mathcal{H}$ not
containing an $(a,b)$-blowup of $T$. This is asymptotically exact when
${s}\leq|V(T)|/2$. A stability result is also presented.

Mathematics Subject Classification: 05D05, 05C65, 05C05.
Keywords: Hypergraph trees, extremal hypergraph theory, Delta-systems.

##  1 Introduction

### 1.1 Basic definitions and notation

An $r$-uniform hypergraph (an $r$-graph, for short), is a family of
$r$-element subsets of a finite set. We associate an $r$-graph ${\mathcal{H}}$
with its edge set and call its vertex set $V({\mathcal{H}})$. Often we take
$V({\mathcal{H}})=[n]$, where $[n]:=\\{1,2,3,\dots,n\\}$. Given an $r$-graph
${\mathcal{F}}$, let the Turán number of ${\mathcal{F}}$,
${\rm{ex}}_{r}(n,{\mathcal{F}})$, denote the maximum number of edges in an
$r$-graph on $n$ vertices that does not contain a copy of ${\mathcal{F}}$.

Since a (graph) tree is connected and bipartite, it uniquely defines the parts
in its bipartition. So, we say a tree $T$ is an $(s,t)$-tree if one part of
$V(T)$ has $s$ vertices and the other has $t$ vertices.

Let $s,t,a,b>0$ be integers, $r=a+b$, and let $T=T(U,V)$ be an $(s,t)$-tree
with parts $U=\\{u_{1},u_{2},\dots,u_{s}\\}$ and
$V=\\{v_{1},v_{2},\dots,v_{t}\\}$. Let $U_{1},\dots,U_{s}$ and
$V_{1},\dots,V_{t}$ be pairwise disjoint sets, such that $|U_{i}|=a$ and
$|V_{j}|=b$ for all $i,j$. So $\left|\bigcup U_{i}\cup V_{j}\right|=as+bt$.
The $(a,b)$-blowup of $T$, denoted by ${\mathcal{T}}(T,a,b)$, is the
$r$-uniform hypergraph with edge set

${\mathcal{T}}(T,a,b):=\\{U_{i}\cup V_{j}:u_{i}v_{j}\in E(T)\\}.$

${\bf\quad\Rightarrow\quad}$

Figure 1: An example of a $(4,2)$-blowup.

The goal of this paper is to find the asymptotics of the Turán number for
$(a,b)$-blowups of many trees of radius $2$ using the $\Delta$-systems method.
Earlier, $(a,b)$-blowups of different classes of trees and different pairs
$(a,b)$ were considered in [7]. The main result in [7] is the following.

######  Theorem 1 ([7]).

Suppose $r\geq 3$, $s,t\geq 2$, $a+b=r$, $b<a<r$. Let $T$ be an $(s,t)$-tree
and let ${\mathcal{T}}={\mathcal{T}}(T,a,b)$ be its $(a,b)$-blowup. Then (as
$n\to\infty$) any $\mathcal{T}$-free $n$-vertex $r$-graph ${\mathcal{H}}$
satisfies

$|{\mathcal{H}}|\leq(t-1){n\choose r-1}+o(n^{r-1}).$

This is asymptotically sharp whenever $t\leq s$.

This theorem asymptotically settles about a half of possible cases, but when
$t>s$ it is expected that the asymptotic is different. More is known on
$(a,b)$-blowups of paths.

Let $P_{\ell}$ denote the (graph) path with $\ell$ edges. The first edge of
the path corresponds to $A_{1}\cup B_{1}$, the second edge to $B_{1}\cup
A_{2}$, etc. The case of $P_{2}$ was resolved asymptotically by Frankl [3]
(for $b=1$) and by Frankl and Füredi [4] (for all $1\leq a\leq r-2$ and
$b=r-a$):

${\rm{ex}}_{r}(n,{\mathcal{T}}(P_{2},a,b))=\Theta\left(n^{\max\\{a-1,b\\}}\right).$

The case of $P_{3}$ was fully solved for large $n$ by Füredi and Özkahya [8].
They showed that for fixed $1\leq a,b<r$ with $r=a+b\geq 3$ and for
$n>n_{0}(r)$,

${\rm{ex}}_{r}(n,{\mathcal{T}}(P_{3},a,b))=\binom{n-1}{r-1}.$

For longer paths, the following was proved in [7].

######  Theorem 2 (Theorem 1 in [7]).

Let $a+b=r$, $a,b\geq 1$ and $\ell\geq 3$. Suppose further that (i) $\ell$ is
odd, or (ii) $\ell$ is even and $a>b$, or (iii) $(\ell,a,b)=(4,1,2)$. Then

${\rm{ex}}_{r}(n,{\mathcal{T}}(P_{\ell},a,b))={\left\lfloor\frac{\ell-1}{2}\right\rfloor}{n\choose
r-1}+o(n^{r-1}).$

So, the situation with blowups of $P_{\ell}$ is not resolved for the case when
$\ell\geq 4$ is even and $a\leq b$ apart from the case $(\ell,a,b)=(4,1,2)$.

In this paper, we consider $(a,b)$-blowups of trees of radius $2$.

A graph bush $B_{{s},h}$ is the radius 2 tree obtained from the star
$K_{1,{s}}$ by joining each vertex of degree one to $h$ new vertices. So
$B_{{s},h}$ has $1+{s}+{s}h$ vertices. Let ${t}=1+{s}h$. Then $B_{{s},h}$ is
an $(s,t)$-tree with ${t}>{s}$.

Suppose that $a,b,{s},h$ are positive integers, $a+b=r$ and ${s}\geq 2$. By
$(a,b,{s},h)$-bush, ${\mathcal{B}}_{{s},h}(a,b)$, we will call the
$(a,b)$-blowup of $B_{{s},h}$. This means the center vertex of $B_{{s},h}$ is
replaced by an $a$-set $A$, its neighbors by the $b$-sets $B_{1},\dots,B_{s}$
and its second neighbors by $a$-sets $A_{i,j}$, $i\in[{s}]$, $j\in[h]$. In
particular, the $(a,b)$-blowup of the path $P_{4}$ is the $(a,b,2,1)$-bush
${\mathcal{B}}_{2,1}(a,b)$.

### 1.2 New results, bushes and shadows

Since ${\mathcal{B}}_{{s},h}(a,b)$ has ${s}$ disjoint edges $B_{i}\cup
A_{i,1}$ for $i=1,\ldots,{s}$, the example of the $r$-uniform hypergraph with
vertex set $[n]$ in which every edge intersects the set $[{s}-1]$ shows that

${\rm{ex}}_{r}(n,{\mathcal{B}}_{{s},h}(a,b))\geq{n\choose r}-{n-{s}+1\choose
r}\sim({s}-1){n\choose r-1}.$ (1)

We will use the $\Delta$-systems approach to show that this is asymptotically
correct in many cases. For $a>b\geq 2$ the asymptotic equality follows from
Theorem 1. In this paper we deal with all cases and also present a somewhat
refined result by considering shadows of hypergraphs.

For an $r$-graph $\mathcal{H}$ the shadow, $\partial\mathcal{H}$, is the
collection of $(r-1)$-sets that lie in some edge of $\mathcal{H}$. Our first
main result is the following.

######  Theorem 3.

Suppose that $a,b,{s},h$ are positive integers, $r=a+b\geq 3$. Also suppose
that in case of $(a,b)=(1,r-1)$ we have $h=1$. Then there exists a
$C=C(r,{s},h)>0$ such that every $n$-vertex $r$-uniform family $\mathcal{H}$
satisfying

$|\mathcal{H}|>({s}-1)|\partial\mathcal{H}|+Cn^{r-2}$ (2)

contains the bush ${\mathcal{B}}_{{s},h}(a,b)$.

This implies that (1) is asymptotically exact in these cases as $r,{s},h$ are
fixed and $n\to\infty$. Note that for $(a,b)=(1,r-1)$ our proof works only for
$h=1$. In fact, in this case the theorem does not hold for $h\geq 2$. An
example is this: $V({\mathcal{H}})=[n],A=[{s}-1]$ and
${\mathcal{H}}={\mathcal{E}}_{1}\cup{\mathcal{E}}_{2}$, where
${\mathcal{E}}_{1}$ is the set of $r$-subsets of $[n]$ with exactly one vertex
in $A$ and ${\mathcal{E}}_{2}$ is the Steiner system $S_{1}(n-{s}+1,r,r-1)$ on
$[n]\setminus A$. This example has asymptotically
$({s}-1+\frac{1}{r}){n\choose r-1}$ edges and does not contain
${\mathcal{B}}_{{s},2}(1,r-1)$. By increasing $h$, we can get examples without
${\mathcal{B}}_{{s},h}(1,r-1)$ that have even more edges.

McLennan [9] proved that in the graph case ($a=b=1$),
${\rm{ex}}_{r}(n,B_{{s},h})=\frac{1}{2}({s}+{s}h-1)n+O(1)$. Vertex-disjoint
unions of complete graphs $K_{{s}+{s}h}$ are extremal. For the case ${s}=1$
the restriction (2) is too strong,
${\rm{ex}}_{r}(n,{\mathcal{B}}_{1,h}(a,b))=O(n^{r-2})$ is known for $a\geq 2$.
Even better bounds were proved in [5]. So we suppose that ${s}\geq 2$, $r\geq
3$.

Since each tree of diameter $4$ with the degree of the center equal to ${s}$
is a subgraph of a graph bush $B_{{s},h}$ for some $h$, Theorem 3 yields the
following more general result.

######  Theorem 4.

Suppose $a,b,{s}\in{\bf Z}^{+}$, $r=a+b\geq 3$ and $a\geq 2$. Let $T$ be a
fixed tree of diameter $4$ in which the degree of the center vertex is ${s}$.
Then there exists a $C=C(r,{s},T)>0$ such that every $n$-vertex $r$-graph
$\mathcal{H}$ satisfying

$|\mathcal{H}|>{({s}-1){n\choose r-1}+Cn^{r-2}}$

contains an $(a,b)$-blowup of $T$. The coefficient $({s}-1)$ is the best
possible (as $n\to\infty$).

We also use the $\Delta$-systems approach to show that for $a,b\geq 2$,
$a+b=r$, an $r$-uniform hypergraphs without ${\mathcal{B}}_{{s},h}(a,b)$ of
cardinality ”close” to extremal contains vertices of ”large” degrees.

######  Theorem 5.

Suppose that $a,b,{s},h$ are positive integers, $a,b\geq 2$ and $r=a+b\geq 5$.
Then for any $C_{0}>0$ there exist $n_{0}>0$ and $C_{1}>0$ such that the
following holds. If $n>n_{0}$, $\mathcal{H}$ is an $n$-vertex $r$-uniform
family not containing a bush ${\mathcal{B}}_{{s},h}(a,b)$ and
$|\mathcal{H}|>({s}-1){n\choose{r-1}}-C_{0}n^{r-2}$, then there are ${s}-1$
vertices in $[n]$ each of which is contained in at least
${n\choose{r-1}}-C_{1}n^{r-2}$ edges of ${\mathcal{H}}$.

The structure of this paper is as follows. In the next section, we discuss the
$\Delta$-system method and present a lemma by Füredi [6] from 1983 that will
be our main tool. In Section 3 we describe properties of so called
intersection structures. It allows us to prove the main case of Theorem 3 (the
case $a\geq 2$) in Section 4 and the case of $a=1$ and $h=1$ in Section 5. In
Section 6 we prove Theorem 5.

##  2 Definitions for the $\Delta$-system method and a lemma

A family of sets $\\{F_{1},\ldots,F_{q}\\}$ is a $q$-star or a $\Delta$-system
or a $q$-sunflower with kernel $A$, if $F_{i}\cap F_{j}=A$ for all $1\leq
i<j\leq q$. The sets $F_{i}\setminus A$ are called petals.

For a member $F$ of a family $\mathcal{F}$, let the intersection structure of
$F$ relative to $\mathcal{F}$ be

$\mathcal{I}(F,\mathcal{F})=\\{F\cap
F^{\prime}:F^{\prime}\in\mathcal{F}\setminus\\{F\\}\\}.$

An $r$-uniform family $\mathcal{F}\subseteq{[n]\choose r}$ is $r$-partite if
there exists a partition $(X_{1},\ldots,X_{r})$ of the vertex set $[n]$ such
that $|F\cap X_{i}|=1$ for each $F\in\mathcal{F}$ and each $i\in[r]$. For a
partition $(X_{1},\ldots,X_{r})$ of $[n]$ and a set $S\subseteq[n]$, the
pattern $\Pi(S)$ is the set $\\{i\in[r]:S\cap X_{i}\neq\emptyset\\}$.
Naturally, for a family $\mathcal{L}$ of subsets of $[n]$,

$\Pi(\mathcal{L})=\\{\Pi(S):S\in\mathcal{L}\\}\subseteq 2^{[r]}.$

######  Lemma 6 (The intersection semilattice lemma (Füredi [6])).

For any positive integers $q$ and $r$, there exists a positive constant
$c(r,q)$ such that every family $\mathcal{F}\subseteq{[n]\choose r}$ contains
a subfamily $\mathcal{F}^{*}\subseteq\mathcal{F}$ satisfying

1\. $|\mathcal{F}^{*}|\geq c(r,q)|\mathcal{F}|$.

2\. $\mathcal{F}^{*}$ is $r$-partite, together with an $r$-partition
$(X_{1},\ldots,X_{r})$.

3\. There exists a family $\mathcal{J}$ of proper subsets of $[r]$ such that
$\Pi(\mathcal{I}(F,\mathcal{F}^{*}))=\mathcal{J}$ holds for all
$F\in\mathcal{F}^{*}$.

4\. $\mathcal{J}$ is closed under intersection, i.e., for all
$A,B\in\mathcal{J}$ we have $A\cap B\in\mathcal{J}$, as well.

5\. For any $F\in\mathcal{F}^{*}$ and each
$A\in\mathcal{I}(F,\mathcal{F}^{*})$, there is a $q$-star in $\mathcal{F}^{*}$
containing $F$ with kernel $A$.

Remark 1. The proof of Lemma 6 in [6] yields that if $\mathcal{F}$ itself is
$r$-partite with an $r$-partition $(X_{1},\ldots,X_{r})$, then the
$r$-partition in the statement can be taken the same.

Remark 2. By definition, if for some $M\subset[r]$ none of the members of the
family $\mathcal{J}$ of proper subsets of $[r]$ in Lemma 6 contains $M$, then
for any two sets $F_{1},F_{2}\in\mathcal{F}^{*}$, their intersections with
$\bigcup_{j\in M}X_{j}$ are distinct. It follows that if $|M|=m$, then
$|\mathcal{F}^{*}|\leq\prod_{j\in
M}|X_{j}|\leq\left(\frac{n-(r-m)}{m}\right)^{m}$. Thus, if
$|\mathcal{F}^{*}|>\left(\frac{n-r+m}{m}\right)^{m}$, then every $m$-element
subset of $[r]$ is contained in some $B\in\mathcal{J}$.

Call a family $\mathcal{J}$ of proper subsets of $[r]$ $m$-covering if every
$m$-element subset of $[r]$ is contained in some $B\in\mathcal{J}$. In these
terms, Remark 2 says that

if $|\mathcal{F}^{*}|>\left(\frac{n-r+m}{m}\right)^{m}$, then the
corresponding $\mathcal{J}$ is $m$-covering. (3)

For $k=0,1,\ldots,r$, define the family $\mathcal{J}^{(k)}$ of proper subsets
of $[r]$ as follows. It contains
(a) the sets $[r]\setminus\\{i\\}$ for $1\leq i\leq k$,
(b) all $(r-2)$-element subsets of $[r]$ containing $\\{1,2,\ldots,k\\}$, and
(c) all the intersections of these subsets.

By definition, each $\mathcal{J}^{(k)}$ is $(r-2)$-covering. Moreover,

each $(r-2)$-covering family of proper subsets of $[r]$ closed under
intersections contains a subfamily isomorphic to some $\mathcal{J}^{(k)}$. (4)

Indeed, if an $(r-2)$-covering family $\mathcal{J}$ of proper subsets of $[r]$
contains exactly $k$ sets of size $r-1$, then it must contain as members all
$(r-2)$-element subsets of $[r]$ not contained in these $k$ sets, so
properties (a) and (b) of the definition hold. Part (c) follows since
$\mathcal{J}$ is closed under intersections.

##  3 General claims on intersection structures.

Call a set $B$ a $(b,q)$-kernel in a set system $\mathcal{F}$ if $B$ is the
kernel of size $b$ in a sunflower with $q$ petals formed by members of
$\mathcal{F}$.

######  Lemma 7.

If $a+b=r$ and an $r$-uniform family $\mathcal{H}$ does not contain
${\mathcal{B}}_{{s},h}(a,b)$, then there do not exist disjoint sets
$A_{0},B_{1},B_{2},\ldots,B_{s}$ with $|A_{0}|=a$, $|B_{1}|=\ldots=|B_{s}|=b$
such that all $B_{1},\ldots,B_{s}$ are $(b,{s}hr)$-kernels in $\mathcal{H}$
and the sets $A_{0}\cup B_{1},\ldots,A_{0}\cup B_{s}$ are edges of
$\mathcal{H}$.

###### Proof.

Suppose, there are such disjoint sets $A_{0},B_{1},B_{2},\ldots,B_{s}$. Let
$D_{0}=A_{0}\cup\bigcup_{j=1}^{s}B_{j}$. For $i=1,\ldots,{s}$, do the
following. Since $B_{i}$ is a $(b,{s}hr)$-kernel and $|D_{i-1}\setminus
B_{i}|=a+({s}-1)b+(i-1)ha\leq{s}hr-h$, there exist $h$ petals $A_{i,j}$
($1\leq j\leq h$) of a ${s}hr$-sunflower with kernel $B_{i}$ that are disjoint
from $D_{i-1}$. Let $D_{i}=D_{i-1}\cup\bigcup_{j=1}^{h}A_{i,j}$. After ${s}$
steps, we find a ${\mathcal{B}}_{{s},h}(a,b)$ whose edges are $A_{0}\cup
B_{i}$ and $B_{i}\cup A_{i,j}$ for $i=1,\ldots,{s}$, $j=1,2,\ldots,h$. ∎

Suppose $a+b=r$ and $\mathcal{G}\subset{[n]\choose r}$ with
$|\mathcal{G}|>\frac{1}{c(r,{s}hr)}n^{r-2}$ does not contain
${\mathcal{B}}_{{s},h}(a,b)$. By Lemma 6 and (3), there is
$\mathcal{G}^{*}\subseteq\mathcal{G}$ satisfying the lemma such that the
corresponding family $\mathcal{J}$ of proper subsets of $[r]$ is
$(r-2)$-covering. Let $(X_{1},\ldots,X_{r})$ be the corresponding partition.

######  Lemma 8.

Family $\mathcal{J}$ does not contain disjoint members $A$ and $B$ such that
$|A|=a$ and $|B|=b$.

###### Proof.

Suppose, it does. By renaming the elements of $\mathcal{J}$, we may assume
that $A=\\{1,\ldots,a\\}$ and $B=\\{a+1,\ldots,r\\}$. Let
$X=\\{x_{1},\ldots,x_{r}\\}\in\mathcal{G}^{*}$, where $x_{i}\in X_{i}$ for all
$i$. Since $A\in\mathcal{J}$, $\\{x_{1},\ldots,x_{a}\\}$ is an
$(a,{s}hr)$-kernel in $\mathcal{G}^{*}$. Let $B_{1},\ldots,B_{s}$ be some
${s}$ petals in the sunflower with kernel $\\{x_{1},\ldots,x_{a}\\}$. As
$[r]\setminus[a]=B\in\mathcal{J}$, each of $B_{1},\ldots,B_{s}$ is a
$(b,{s}hr)$-kernel in $\mathcal{G}^{*}$, contradicting Lemma 7. ∎

######  Lemma 9.

If $a+b=r$ and $2\leq a,b\leq r-2$, then for each $0\leq k\leq r-2$ and for
$k=r$ the family $\mathcal{J}^{(k)}$ has disjoint members $A$ and $B$ such
that $|A|=a$ and $|B|=b$, unless $(r,a,b,k)=(4,2,2,1)$.

If $(a,b)=(1,r-1)$ or $(a,b)=(r-1,1)$ and $r\geq 3$, then for each $1\leq
k\leq r-2$ and for $k=r$ the family $\mathcal{J}^{(k)}$ has disjoint members
$A$ and $B$ such that $|A|=a$ and $|B|=b$.

###### Proof.

If $k\geq a$, then we let $A=[a]$, $B=[r]\setminus[a]$, and represent them as
follows:

$A=\bigcap_{k+1\leq i<i^{\prime}\leq
r}([r]\setminus\\{i,i^{\prime}\\})\cap\bigcap_{a+1\leq i\leq
k}([r]\setminus\\{i\\}),\quad B=\bigcap_{1\leq i\leq a}([r]\setminus\\{i\\}).$

If $k\geq b$, then we have a symmetric representation. In particular, this
proves the claim for $(a,b)=(1,r-1)$ and $(a,b)=(r-1,1)$.

If $k\leq a-2$, then we again let $A=[a]$, $B=[r]\setminus[a]$, but represent
them as follows (using that $a\leq r-2$ and $k\leq a-2$):

$A=\bigcap_{a+1\leq i<i^{\prime}\leq r}([r]\setminus\\{i,i^{\prime}\\}),\quad
B=\bigcap_{1\leq i\leq k}([r]\setminus\\{i\\})\cap\bigcap_{k+1\leq
i<i^{\prime}\leq a}([r]\setminus\\{i,i^{\prime}\\}).$

By symmetry, the only remaining case is that $k=a-1=b-1$. So $r$ is even, and
$a=b=r/2=k+1$. In this case, if $r>4$, then we let $A=[k-1]\cup\\{k+1,k+2\\}$,
$B=([r]\setminus[k+2])\cup\\{k\\}$, and represent them as follows:

$A=\bigcap_{k+3\leq i<i^{\prime}\leq
r}([r]\setminus\\{i,i^{\prime}\\})\cap([r]\setminus\\{k\\}),\quad
B=\bigcap_{1\leq i\leq
k-1}([r]\setminus\\{i\\})\cap([r]\setminus\\{k+1,k+2\\}).$

∎

##  4 Proof of the main Theorem for $a>1$

In this section we prove the main part of Theorem 3: the case of $2\leq a\leq
r-1$. In Subsection 4.1 we describe a procedure of partitioning
${\mathcal{H}}$ into structured subfamilies, and in the next three subsections
we use this partition to find the required bush or to get a contradiction to
(2). We distinguish three cases: (i) $a,b\geq 2$ and $r\geq 5$ (discussed in
Subsection 4.2), (ii) $(a,b)=(2,2)$ and $r=4$ (Subsection 4.3), and (iii)
$(a,b)=(r-1,1)$ and $r\geq 3$ (Subsection 4.4).

### 4.1 Basic procedure

Assume that $2\leq a\leq r-1$ and that an $n$-vertex $r$-uniform family
$\mathcal{H}$ satisfies (2) but does not contain ${\mathcal{B}}_{{s},h}(a,b)$.
Define $C=C(r,{s},h):=1/c(r,{s}hr)$, where $c$ is from Lemma 6. For any
$r$-uniform family $\mathcal{G}$, let $\mathcal{G}^{*}$ denote a family
satisfying Lemma 6 and $\mathcal{J}(\mathcal{G}^{*})\subset 2^{[r]}$ denote
the corresponding intersection structure.

Do the following procedure. Let $\mathcal{H}_{1}=\mathcal{H}^{*}$ and
${\mathcal{J}}_{1}=\mathcal{J}(\mathcal{H}^{*})$. For $i=1,2,\ldots,$ if
$|\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j}|\leq Cn^{r-2}$, then
stop and let $m:=i$ and
$\mathcal{H}_{0}=\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j}$;
otherwise, let
$\mathcal{H}_{i+1}:=(\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j})^{*}$
and
${\mathcal{J}}_{i+1}=\mathcal{J}((\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j})^{*})$.

This procedure provides a partition of $\mathcal{H}$,
$\mathcal{H}=\bigcup_{i=0}^{m}\mathcal{H}_{i}$. Let $\widehat{\mathcal{H}}$
denote $\bigcup_{i=1}^{m}\mathcal{H}_{i}$. By definition,
$|\mathcal{H}_{0}|\leq Cn^{r-2}$, so we get

$|\widehat{\mathcal{H}}|+Cn^{r-2}\geq|\mathcal{H}|.$ (5)

### 4.2 Case of $a,b\geq 2$ and $r\geq 5$

Here $2\leq a,b\leq r-2$ and $(a,b)\neq(2,2)$, so Lemmas 8 and 9 imply that
for each $1\leq i\leq m$, $\mathcal{J}(\mathcal{H}_{i})$ has exactly $r-1$
$(r-1)$-subsets, it contains $\mathcal{J}^{(r-1)}$. Hence for each hyperedge
$E\in\mathcal{H}_{i}\subset\widehat{\mathcal{H}}$ ($1\leq i\leq m$) there
exists an element $c(E)\in E$ such that each proper subset of $E$ containing
$c(E)$ is a kernel of an ${s}hr$-star in $\mathcal{H}_{i}$. Beware of the fact
that although each $\mathcal{H}_{i}$ is $r$-partite, the partitions might
differ for different values of $i$. This does not cause any problem in our
argument, we only need the existence of the element $c(E)$.

Define the function $\alpha$ on ${[n]\choose r-1}$ as follows: For each
$(r-1)$-set $Y\subset[n]$, let $\alpha(Y)$ be the number of edges
$E\in\widehat{\mathcal{H}}$ with $Y=E\setminus\\{c(E)\\}$.

######  Claim 10.

$\alpha(Y)\leq{s}-1$, for each $(r-1)$-subset $Y$ of $[n]$.

This Claim implies

$({s}-1)|\partial\widehat{\mathcal{H}}|\geq\sum\nolimits_{Y\in{[n]\choose
r-1}}\alpha(Y)=|\widehat{\mathcal{H}}|.$

This, together with (5) contradicts (2) and thus completes the proof of
Theorem 3 in this case.

We prove Claim 10 in two steps in a stronger form which will be useful in
Section 6 to handle the stability of the extremal systems (i.e., Theorem 5).
For every $Y\subset[n]$, let ${\mathcal{U}}(Y)$ be the set of vertices
$v\in[n]\setminus Y$ such that there is an edge $E\in\widehat{\mathcal{H}}$
containing $Y$ with $c(E)=v$.

######  Claim 11.

Suppose $Y\subset[n]$, $a\leq|Y|\leq r-1$, $v,v^{\prime}\in{\mathcal{U}}(Y)$,
$v\neq v^{\prime}$ and edges $E,E^{\prime}\in\widehat{\mathcal{H}}$ are such
that $v=c(E)$, $v^{\prime}=c(E^{\prime})$ and $Y\subseteq E\cap E^{\prime}$.
If $E\in{\mathcal{H}}_{i}$ and $E^{\prime}\in{\mathcal{H}}_{i^{\prime}}$, then
$i\neq i^{\prime}$.

###### Proof.

Suppose $v\neq v^{\prime}$, but $i=i^{\prime}$. We may assume that the
partition of $[n]$ corresponding to ${\mathcal{H}}_{i}$ is
$(X_{1},\ldots,X_{r})$ and $v,v^{\prime}\in X_{r}$. Let
$Z:=\\{j\in[r]:X_{j}\cap E\cap E^{\prime}\neq\emptyset\\}$. By symmetry, we
may also assume that $E\cap E^{\prime}\subset X_{1}\cup\ldots\cup X_{|Z|}$. So
$Z\in{\mathcal{J}}_{i}$ and we know that $a\leq|Z|\leq r-1$. The family
${\mathcal{J}}_{i}$ contains $\mathcal{J}^{(r-1)}$, namely
$[r]\setminus\\{j\\}\in{\mathcal{J}}_{i}$ for each $1\leq j\leq r-1$. Since
${\mathcal{J}}_{i}$ is intersection closed it must contain every subset of
$Z$, e.g., $[a]\in{\mathcal{J}}_{i}$, and it also contains every subset
containg the element $r$, e.g., $[r]\setminus[a]\in{\mathcal{J}}_{i}$. This
contradicts Lemma 8. ∎

######  Claim 12.

Suppose $Y\subset[n]$, $a\leq|Y|\leq r-1$. Then $|{\mathcal{U}}(Y)|\leq{s}-1$.

###### Proof.

Suppose to the contrary that there are ${s}$ distinct
$v_{1},\ldots,v_{s}\in[n]$ and distinct
$E_{1},\ldots,E_{s}\in\widehat{\mathcal{H}}$ such that $Y\subseteq
E_{1}\cap\ldots\cap E_{s}$ and $v_{i}=c(E_{i})$ for $i=1,\ldots,{s}$. Let
$E_{1}\in\mathcal{H}_{i_{1}},\ldots,E_{s}\in\mathcal{H}_{i_{s}}$. By Claim 11,
$i_{1},\ldots,i_{s}$ are all distinct. By relabelling we may suppose that
$E_{i}\in\mathcal{H}_{i}$.

We will find ${s}+1$ disjoint sets $A_{0},B_{1},B_{2},\ldots,B_{s}$
contradicting Lemma 7 using induction as follows. Fix a subset $A_{0}$ of $Y$
with $|A_{0}|=a$ and let $D_{0}:=A_{0}\cup\\{c(E_{1}),\dots,c(E_{s})\\}$. We
have $|D_{0}|=a+{s}$. We define the sets $E_{i}^{\prime},D_{i},B_{i}$ step by
step as follows. We will have $D_{i}:=D_{0}\cup\bigcup_{j\leq
i}E_{j}^{\prime}$ and $|D_{i}|=a+{s}+i(r-1-a)$. For $i=1,2,\dots,{s}$ consider
the family $\mathcal{H}_{i}$ and its member $E_{i}$ in it. By the intersection
structure of $\mathcal{H}_{i}$, the set $A_{0}\cup\\{c(E_{i})\\}$ is an
$(a+1,{s}hr)$-kernel in $\mathcal{H}_{i}$. One of the ${s}hr$ petals of the
sunflower in $\mathcal{H}_{i}$ with kernel $A_{0}\cup\\{c(E_{i})\\}$ should be
disjoint from $D_{i-1}$; let $E_{i}^{\prime}$ be the corresponding set in
$\mathcal{H}_{i}$. Since $c(E_{i})\in E_{i}^{\prime}$, and homogeneity gives
$c(E_{i}^{\prime})=c(E_{i})$, the set $B_{i}:=E_{i}^{\prime}\setminus A_{0}$
is a $(b,{s}hr)$-kernel. ∎

### 4.3 The case $(a,b)=(2,2)$

Lemmas 8 and 9 imply that for each $1\leq i\leq m$, either
— $\mathcal{J}^{(3)}$ is contained in $\mathcal{J}(\mathcal{H}_{i})$, it has
exactly three 3-subsets, so $[4]\setminus\\{1\\}$, $[4]\setminus\\{2\\}$, and
$[4]\setminus\\{3\\}$ are in $\mathcal{J}$ and $\mathcal{J}$ also contains all
subsets containing the element $4$ but it does not contain $[3]$, or
— $\mathcal{J}(\mathcal{H}_{i})$ is of $\mathcal{J}^{(1)}$ type, it has a
unique 3-subset, $\\{2,3,4\\}$, and
$\\{\\{1\\},\\{1,2\\},\\{1,3\\},\\{1,4\\}\\}\subset\mathcal{J}$.

Call $\mathcal{H}_{i}$ (and its edges) type $\alpha$ if
$\mathcal{J}(\mathcal{H}_{i})$ has three 3-subsets. Each of these edges
$E\in\mathcal{H}_{i}$ has an element $c(E)\in E$ such that each proper subset
of $E$ containing $c(E)$ is a kernel of a $4\cdot{s}\cdot h$-star in
$\mathcal{H}_{i}$. The union of the families $\mathcal{H}_{i}$ of type
$\alpha$ is $\widehat{\mathcal{H}}_{\alpha}$. Call $\mathcal{H}_{i}$ (and its
edges) type $\beta$ if $\mathcal{J}(\mathcal{H}_{i})$ has a unique 3-subset.
Each of these edges $E\in\mathcal{H}_{i}$ has an element $b(E)\in E$ such that
each set $K\subset E$ of the form $\\{b(E),x\\}$ ($x\in E\setminus\\{b(E)\\}$)
and the set $E\setminus\\{b(E)\\}$ is a kernel of a $4\cdot{s}\cdot h$-star in
$\mathcal{H}_{i}$. The union of the families $\mathcal{H}_{i}$ of type $\beta$
is $\widehat{\mathcal{H}}_{\beta}$.

Define the function $\alpha$ on ${[n]\choose 3}$ as follows: Given a $3$-set
$Y$, let $\alpha(Y)$ be the number of edges
$E\in\widehat{\mathcal{H}}_{\alpha}$ with $Y=E\setminus\\{c(E)\\}$. Define the
function $\beta$ on ${[n]\choose 3}$ as follows: Given a $3$-set $Y$, let
$\beta(Y)$ be the number of edges $E\in\widehat{\mathcal{H}}_{\beta}$ with
$b(E)\in Y\subset E$.

######  Claim 13.

$\alpha(Y)+\frac{1}{3}\beta(Y)\leq{s}-1$, for all $3$-subsets $Y$ of $[n]$.

###### Proof.

For brevity, let $\alpha=\alpha(Y)$ and $\beta=\beta(Y)$. Let
$E_{1}\in\mathcal{H}_{i_{1}},\ldots,E_{\alpha}\in\mathcal{H}_{i_{\alpha}}$ be
the $\alpha$ distinct edges $E$ with $E\in\widehat{\mathcal{H}}_{\alpha}$ and
$Y=E\setminus\\{c(E)\\}$ and let
$E_{\alpha+1}\in\mathcal{H}_{i_{\alpha+1}},\ldots,E_{\alpha+\beta}\in\mathcal{H}_{i_{\alpha+\beta}}$
be the $\beta$ distinct edges $E$ with $E\in\widehat{\mathcal{H}}_{\beta}$ and
$b(E)\in Y\subset E$. If $i_{j}=i_{j^{\prime}}$ for some $j\neq j^{\prime}$,
then the intersection structure of $\mathcal{H}_{i_{j}}$ would contain the
$3$-set $Y$, a contradiction. Thus $i_{1},i_{2},\ldots$ are all distinct. By
relabelling we may suppose that $E_{i}\in\mathcal{H}_{i}$.

Suppose that $\alpha+\frac{1}{3}\beta>{s}-1$, so
$\alpha+\lceil\beta/3\rceil\geq{s}$. Since $|Y|=3$, one can find an element
$y_{0}\in Y$ such that $b(E_{j})=y_{0}$ at least $\lceil\beta/3\rceil$ times.
So we may suppose that there are ${s}$ distinct $E_{i}\in\mathcal{H}_{i}$ such
that the elements $c(E_{1}),\dots,c(E_{\alpha})$ and $d(E_{j}):=E_{j}\setminus
Y$ for $\alpha<j\leq{s}$ are all distinct and $E_{i}=Y\cup\\{c(E_{i})\\}$,
$b(E_{j})=y_{0}$.

Let $A_{0}:=Y\setminus\\{y_{0}\\}$. Then $|A_{0}|=2$ and we can find ${s}+1$
disjoint sets $A_{0},B_{1},B_{2},\ldots,B_{s}$ contradicting Lemma 7 using
induction in the same way as we did in the proof of Claim 12. ∎

Claim 13 implies

$({s}-1)|\partial\widehat{\mathcal{H}}|\geq\sum\nolimits_{Y\in{[n]\choose
3}}\left(\alpha(Y)+\frac{1}{3}\beta(Y)\right)=|\widehat{\mathcal{H}}_{\alpha}|+|\widehat{\mathcal{H}}_{\beta}|.$

This, together with (5) contradicts (2) and thus completes the proof of
Theorem 3 in this case.

### 4.4 The case $(a,b)=(r-1,1)$

Call $\mathcal{H}_{i}$ (as above) of type $\alpha$ if
$\mathcal{J}(\mathcal{H}_{i})$ has $r-1$ $(r-1)$-subsets. Each of these edges
$E\in\mathcal{H}_{i}$ has an element $c(E)\in E$ such that each proper subset
of $E$ containing $c(E)$ is a kernel of a ${s}hr$-star in $\mathcal{H}_{i}$.
The union of these families $\mathcal{H}_{i}$ is
$\widehat{\mathcal{H}}_{\alpha}$. Call $\mathcal{H}_{j}$ (and its edges) type
$\beta$ if $\mathcal{J}(\mathcal{H}_{j})$ has no $(r-1)$-subset. Note that
each element $y$ of an edge $E\in\mathcal{H}_{j}$ is a kernel of a
${s}hr$-star in $\mathcal{H}_{j}$. The union of these $\mathcal{H}_{j}$
families is $\widehat{\mathcal{H}}_{\beta}$.

As in the previous subsections, for each $Y\in{[n]\choose r-1}$ let
$\alpha(Y)$ be the number of edges $E\in\widehat{\mathcal{H}}_{\alpha}$ with
$Y=E\setminus\\{c(E)\\}$. The definition of $\beta$ on ${[n]\choose r-1}$ is
even simpler: $\beta(Y)$ is the number of edges
$E\in\widehat{\mathcal{H}}_{\beta}$ with $Y\subset E$. If
$\alpha(Y)+\beta(Y)>{s}-1$, then taking $A_{0}:=Y$ and $B_{i}:=E_{i}\setminus
Y$, each $B_{i}$ is a kernel of a large star, contradicting Lemma 7.
Therefore, $\alpha(Y)+\beta(Y)\leq{s}-1$ for each $Y\in{[n]\choose r-1}$, and

$({s}-1)|\partial\widehat{\mathcal{H}}|\geq\sum_{Y\in{[n]\choose
r-1}}\left(\alpha(Y)+\beta(Y)\right)=|\widehat{\mathcal{H}}_{\alpha}|+r|\widehat{\mathcal{H}}_{\beta}|\geq|\widehat{\mathcal{H}}|,$

contradicting (2).

##  5 Hypergraphs without a bush ${\mathcal{B}}_{{s},1}(1,r-1)$

We will prove this part for $C=C(r,{s}):=1/c(r,q)$, where $q:=8r{s}^{2}$ and
$c$ is from Lemma 6. Suppose $\mathcal{H}$ is a counter-example with the
fewest edges. So ${\mathcal{H}}\subset{[n]\choose r}$, it is bush-free and
$|{\mathcal{H}}|-|\partial{\mathcal{H}}|$ satisfies the lower bound (2). In
particular, $|\mathcal{H}|>Cn^{r-2}$.

Call an $r$-graph ${\mathcal{G}}$ ${s}$-normal if it has no $(r-1)$-tuples of
vertices whose codegree is positive but less than ${s}$. If $\mathcal{H}$ is
not ${s}$-normal, then choose an $(r-1)$-tuple $Y$ of vertices whose codegree
is positive but less than ${s}$ and let $\mathcal{H}^{\prime}$ be obtained
from $\mathcal{H}$ by deleting the edges containing $Y$. Then
$|\mathcal{H}^{\prime}|-({s}-1)|\partial\mathcal{H}^{\prime}|\geq|\mathcal{H}|-({s}-1)|\partial\mathcal{H}|>Cn^{r-2}$,
so $\mathcal{H}^{\prime}$ satisfies (2) and is
${\mathcal{B}}_{{s},1}(1,r-1)$-free. This contradicts the minimality of
$|\mathcal{H}|$. From now on, we suppose that $\mathcal{H}$ is ${s}$-normal.

For every edge $Y\in\mathcal{H}$ and any $u\in Y$, let $Q(Y,u)=\\{z\in
V(\mathcal{H})\setminus Y:Y\setminus\\{u\\}\cup\\{z\\}\in\mathcal{H}\\}$.
Since $\mathcal{H}$ is ${s}$-normal, $|Q(Y,u)|\geq{s}-1$ for every edge
$Y\in\mathcal{H}$ and every $u\in Y$. For each $u\in Y\in{\mathcal{H}}$, fix a
subset $Q^{\prime}(Y,u)$ of $Q(Y,u)$ with
$|Q^{\prime}(Y,u)|=\min\\{s,|Q(Y,u)|\\}.$ Call a subfamily
${\mathcal{P}}^{\prime}\subset{\mathcal{H}}$ with
$u\in\bigcap{\mathcal{P}}^{\prime}$ separable if
$(\bigcup_{P\in{\mathcal{P}}}Q^{\prime}(P,u))\cap(\bigcup{\mathcal{P}}^{\prime})=\emptyset$.

######  Claim 14.

Suppose that $u$ is a kernel of a star ${\mathcal{P}}$ in $\mathcal{H}$, i.e.,
${\mathcal{P}}\subset{\mathcal{H}}$ such that $P_{1}\cap P_{2}=u$ for all
$P_{1},P_{2}\in{\mathcal{P}}$ whenever $P_{1}\neq P_{2}$. Then there exists a
separable ${\mathcal{P}}^{\prime}\subset{\mathcal{P}}$ with
$|{\mathcal{P}}^{\prime}|\geq|{\mathcal{P}}|/(2s+1)$.

###### Proof.

Let $G$ be the auxiliary directed graph with vertex set ${\mathcal{P}}$ where
the pair $\\{P_{1},P_{2}\\}\subset{\mathcal{P}}$ is an arc if $P_{2}\cap
Q^{\prime}(P_{1},u)\neq\emptyset$. Let $G^{\prime}$ be the underlying
undirected graph of $G$.

Since $Q^{\prime}(P,u)$ can meet at most ${s}$ members of ${\mathcal{P}}$, the
outdegree of each vertex in $G$ is at most ${s}$. So $G^{\prime}$ is
$2{s}$-degenerate and hence $(2{s}+1)$-colorable. In particular, $G^{\prime}$
has an independent set of size at least $|{\mathcal{P}}|/(2s+1)$. An
independent set in $G^{\prime}$ corresponds to a separable subfamily of
${\mathcal{P}}$. ∎

######  Claim 15.

Suppose that $u$ is a center of a separable star ${\mathcal{P}}^{\prime}$ in
$\mathcal{H}$. If $|{\mathcal{P}}^{\prime}|\geq r+2s-2$ then there exists a
unique $({s}-1)$-element set $T(u)$ such that $Q(P,u)=T(u)$ for all
$P\in{\mathcal{P}}^{\prime}$.
Moreover, $Q(Y,u)=T(u)$ for each $u\in Y\in{\mathcal{H}}$ with $Y\cap
T(u)=\emptyset$. I.e.,

$Y\setminus\\{u\\}\cup\\{z\\}\in{\mathcal{H}}\text{ for all }z\in
T(u)\cup\\{u\\}.$ (6)

Let $T^{+}(u):=T(u)\cup\\{u\\}$. Then $T^{+}(z)$ is defined for each $z\in
T^{+}(u)$ and coincides with $T^{+}(u)$.

###### Proof.

If there are ${s}$ members of ${\mathcal{P}}^{\prime}$, say
$P_{1},\dots,P_{s}$ such that $|\bigcup_{1\leq
i\leq{s}}Q^{\prime}(P_{i},u)|\geq{s}$, then the family
$\\{Q^{\prime}(P_{1},u)$,…,$Q^{\prime}(P_{s},u)\\}$ satisfies Hall’s
condition. So, there exists a set of distinct representatives
$\\{z_{1},\dots,z_{s}\\}$ such that $z_{i}\in Q^{\prime}(P_{i},u)$ for $1\leq
i\leq{s}$. Then the sets $P_{1},\dots,P_{s}$ together with the hyperedges
$P_{1}\setminus\\{u\\}\cup\\{z_{1}\\},\dots,P_{s}\setminus\\{u\\}\cup\\{z_{s}\\}$
form a bush ${\mathcal{B}}_{{s},1}(1,r-1)$ with central element $u$, a
contradiction.

Hence $|\bigcup_{1\leq i\leq{s}}Q^{\prime}(P_{i},u)|\leq{s}-1$ for any ${s}$
distinct $P_{1},\dots,P_{s}\in{\mathcal{P}}^{\prime}$. This implies
$|Q^{\prime}(P_{i},u)|={s}-1$ for all $i$, so $|Q(P_{i},u)|={s}-1$. It also
follows that $Q(P_{i},u)=Q(P_{j},u)$ for $1\leq i\leq j\leq{s}$. This holds
for any pair from ${\mathcal{P}}^{\prime}$, so we get $Q(P,u)=Q(P_{1},u)$ for
all $P\in{\mathcal{P}}^{\prime}$. Define $T(u):=Q(P_{1},u)$.

Consider $Y\in{\mathcal{H}}$ with $u\in Y$ and $Y\cap T(u)=\emptyset$. The set
$(Y\setminus\\{u\\})\cup Q^{\prime}(Y,u)$ can meet at most $(r-1+{s})$ members
of ${\mathcal{P}}^{\prime}$. Since $|{\mathcal{P}}^{\prime}|\geq(r-1)+(2s-1)$
we can still find $P_{1},\dots,P_{{s}-1}\in{\mathcal{P}}^{\prime}$ such that
$P_{1},\dots,P_{{s}-1}$ and $Y$ form a separable star. This yields
$Q(Y,u)=T(u)$ and we are done.

The uniqueness of $T(u)$ also follows from the fact that having a $T_{2}(u)$
with similar properties one can find a $P\in{\mathcal{P}}^{\prime}$ avoiding
it, so $T_{2}(u)=Q(P,u)=T(u)$.

To prove the last statement, choose $z\in T(u)$. Equation (6) implies that the
family $\\{P\setminus\\{u\\}\cup\\{z\\}:P\in{\mathcal{P}}^{\prime}\\}$ is a
separable star (we have $T^{+}(u)\setminus\\{z\\}\subset
Q(P\setminus\\{u\\}\cup\\{z\\},z)$). So the first part of Claim 15 implies
that $Q(P\setminus\\{u\\}\cup\\{z\\},z)=T^{+}(u)\setminus\\{z\\}=T(z)$. ∎

Do the following procedure. Apply Lemma 6 for ${\mathcal{H}}$ to get
$\mathcal{H}_{1}=\mathcal{H}^{*}$ with the corresponding intersection
structure $\mathcal{J}_{1}\subset 2^{[r]}$. For $i=1,2,\ldots$, if
$|\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j}|\leq C\cdot n^{r-2}$,
then stop, let $m:=i$ and
$\widehat{\mathcal{H}}:=\bigcup_{j=1}^{i}\mathcal{H}_{j}$ and
$\mathcal{H}_{0}=\mathcal{H}\setminus\widehat{\mathcal{H}}$; otherwise, let
$\mathcal{H}_{i+1}:=(\mathcal{H}\setminus\bigcup_{j=1}^{i}\mathcal{H}_{j})^{*}$.
We have $|\mathcal{H}_{1}|>n^{r-2}$ because $|{\mathcal{H}}|>Cn^{r-2}$ and by
the choice of $C$. Similarly, $|{\mathcal{H}}_{i}|>n^{r-2}$ for each $1\leq
i\leq m$. By Lemmas 8 and 9, $\mathcal{J}_{i}$ contains a family isomorphic to
$\mathcal{J}^{(r-1)}$, or to $\mathcal{J}^{(0)}$. In both cases,
$\mathcal{J}_{i}$ contains a singleton, so ${\mathcal{H}}_{i}$ contains
$q$-stars with singleton kernels.

Case 1. There exists a $\mathcal{J}_{i}$ containing a family isomorphic to
$\mathcal{J}^{(r-1)}$.
We may assume that $\mathcal{J}_{i}$ contains all proper subsets of $[r]$
containing $1$ and $X_{1},\dots,X_{r}$ are the parts of ${\mathcal{H}}_{i}$.
There is an element $y_{1}\in X_{1}$ such that $\\{y_{1}\\}$ is a kernel of a
$q$-star in ${\mathcal{H}}_{i}$. Claims 14 and 15 imply the existence of
$T(y_{1})$ since $\frac{q}{2s+1}\geq r+2s-2$. We can choose a
$Y_{1}=\\{y_{1},\ldots,y_{r}\\}\in\mathcal{H}_{i}$ where $y_{j}\in X_{j}$ for
$j\in[r]$ with $Y\cap T(y_{1})=\emptyset$.

Since $\\{1,2\\}\in\mathcal{J}_{i}$, $\\{y_{1},y_{2}\\}$ is the kernel of a
$2{s}$-star $Y_{1},\dots,Y_{2{s}}\in{\mathcal{H}}_{i}$ (i.e, the sets
$Y_{j}\setminus\\{y_{1},y_{2}\\}$ are pairwise disjoint for $j\in[2{s}]$). At
most ${s}-1$ of them intersect $T(y_{1})$. So we may assume, e.g.,
$Y_{1},\ldots,Y_{s}$ are disjoint from $T(y_{1})$. Since
$Y_{j}\setminus\\{y_{2}\\}$ is a kernel of a $q$-star for each $j\in[{s}]$,
one can find distinct elements $x_{1},\dots,x_{s}$ from $X_{2}$ such that none
of them lies in $T(y_{1})$ and
$Y_{j}\setminus\\{y_{2}\\}\cup\\{x_{j}\\}\in{\mathcal{H}}_{i}$. Let
$T^{+}(y_{1}):=T(y_{1})\cup\\{y_{1}\\}=\\{z_{1},\dots,z_{s}\\}$ and apply (6)
for $Y_{j}\setminus\\{y_{2}\\}\cup\\{x_{j}\\}$. We obtain that
$Y_{j}\setminus\\{y_{1},y_{2}\\}\cup\\{z_{j},x_{j}\\}\in{\mathcal{H}}$.

Apply (6) for $Y_{j}$ (again with $T^{+}(y_{1})$). We get that
$Y_{j}\setminus\\{y_{1}\\}\cup\\{z_{j}\\}\in{\mathcal{H}}$. These edges,
together with the edges $Y_{j}\setminus\\{y_{1},y_{2}\\}\cup\\{z_{j},x_{j}\\}$
form a bush ${\mathcal{B}}_{{s},1}(1,r-1)$ with the central vertex $y_{2}$.
This contradiction leads to the last case.

Case 2. $\mathcal{J}_{i}$ contains a family isomorphic to $\mathcal{J}^{(0)}$
for each $1\leq i\leq m$.

By the structure of $\mathcal{J}^{(0)}$, each $v\in V(\mathcal{H}_{i})$ is a
kernel of a $q$-star in ${\mathcal{H}}_{i}$. So by Claims 14 and 15 for each
$u\in\bigcup\widehat{\mathcal{H}}$, $T^{+}(u)$ is well defined and
$|T^{+}(u)|=s$.

Since $\mathcal{J}^{(0)}$ does not contain sets of size $r-1$, each
$(r-1)$-element set $Y\in\partial\mathcal{H}_{i}$ is only in one set in
$\mathcal{H}_{i}$, thus $|\partial\mathcal{H}_{i}|=r|\mathcal{H}_{i}|$. As
$|\mathcal{H}_{0}|\leq Cn^{r-2}$ equation (2) implies
$|\widehat{\mathcal{H}}|>({s}-1)|\partial\mathcal{H}|\geq({s}-1)|\partial\widehat{\mathcal{H}}|$.
We obtain
$\sum_{i}|\partial\mathcal{H}_{i}|=r\sum_{i}|\mathcal{H}_{i}|=r|\widehat{\mathcal{H}}|>r({s}-1)|\partial\widehat{\mathcal{H}}|$.
Hence some $(r-1)$-tuple $S$ belongs to at least $r({s}-1)+1$ shadow families
$\partial\mathcal{H}_{i}$. Say, $S\cup\\{z_{i}\\}\in\mathcal{H}_{i}$ for
$i\in[r({s}-1)+1]$. Let $Z=\\{z_{1},\ldots,z_{r({s}-1)+1}\\}$.

For every $y\in S$, $|T(y)|={s}-1$; thus there is $z_{j}\in
Z\setminus\bigcup_{y\in S}T^{+}(y)$, say $z_{1}$. Let
$Y_{1}:=S\cup\\{z_{1}\\}$. We got that $T(z_{1})$ is disjoint from $Y_{1}$
while $z_{1}\in Y_{1}\in{\mathcal{H}}_{1}$. So Claim 15 implies that
$Q(Y_{1},z_{1})=T(z_{1})$. However $Q(Y_{1},z_{1})$ contains
$Z\setminus\\{z_{1}\\}$.

This final contradiction implies that the minimal counterexample
${\mathcal{H}}$ does not exist, completing the proof of Theorem 3.

##  6 Stability: Proof of Theorem 5

Let $\mathcal{H}$ be an $n$-vertex $r$-uniform family not containing a bush
${\mathcal{B}}_{{s},h}(a,b)$ with

$|\mathcal{H}|>({s}-1){n\choose{r-1}}-C_{0}n^{r-2}.$ (7)

Define $C$, $m$, ${\mathcal{H}}_{0},\ldots,{\mathcal{H}}_{m}$ and
$\widehat{\mathcal{H}}$ as in Subsection 4.1. By (7) and the definition of
${\mathcal{H}}_{0}$,

$|\widehat{\mathcal{H}}|\geq({s}-1){n\choose{r-1}}-(C+C_{0})n^{r-2}.$ (8)

As in Subsection 4.2, for each $1\leq i\leq m$, the intersection structure
$\mathcal{J}(\mathcal{H}_{i})$ contains $\mathcal{J}^{(r-1)}$. So, again for
each hyperedge $E\in\mathcal{H}_{i}\subset\widehat{\mathcal{H}}$ ($1\leq i\leq
m$) there is an element $c(E)\in E$ such that each proper subset of $E$
containing $c(E)$ is a kernel of an ${s}hr$-star in $\mathcal{H}_{i}$.

For $v\in[n]$, let ${\mathcal{H}}(v)=\\{E\in\widehat{\mathcal{H}}:v=c(E)\\}$
and ${\mathcal{G}}(v)=\\{E\setminus\\{v\\}:E\in{\mathcal{H}}(v)\\}$. Let
${\mathcal{G}}=\bigcup_{v\in[n]}{\mathcal{G}}(v)$. By Claim 11,
$|{\mathcal{G}}(v)|=|\widehat{\mathcal{H}}(v)|$ for each $v\in[n]$; in
particular, $\sum_{v}|{\mathcal{G}}(v)|=|\widehat{\mathcal{H}}|$. Furthermore,
Claim 12 implies that

each $(r-2)$-subset $Y$ of $[n]$ is in the shadow of at most ${s}-1$ families
${\mathcal{G}}(v)$.  (9)

Recall the Lovász form of the Kruskal-Katona Theorem:

######  Theorem 16.

If $x$ is a positive real, $1\leq k<n$, ${\mathcal{F}}\subseteq{[n]\choose k}$
and $|{\mathcal{F}}|={x\choose k}$, then $|\partial{\mathcal{F}}|\geq{x\choose
k-1}$.

Here ${x\choose k}$ is a non-negative real convex function defined as a degree
$k$ polynomial $x(x-1)\dots(x-k+1)/k!$ for $x\geq k-1$ and $0$ otherwise.

For every $j\in[n]$, there a real $x_{j}$ such that
$|{\mathcal{G}}(j)|={x_{j}\choose r-1}$. Inequality (8) gives

$\sum_{i}{x_{i}\choose r-1}\geq({s}-1){n\choose{r-1}}-(C+C_{0})n^{r-2},$ (10)

and (9) and Lovász theorem give

$({s}-1){n\choose
r-2}\geq\sum_{i}|\partial{\mathcal{G}}(j)|\geq\sum_{i}{x_{i}\choose r-2}.$
(11)

Let $b=3(r-1)!(C+C_{0})$.

######  Lemma 17.

Suppose that $n\geq r^{2}$ and $x_{1}\geq x_{2}\geq\ldots\geq x_{n}$. Then
inequalities (10) and (11) concerning $n,r,x_{1},\dots,x_{n}$ imply
$x_{1},\dots,x_{{s}-1}>n-b$.

###### Proof.

Pure college algebra. For brevity let $y:=x_{{s}}$. The case $y\leq r-2$ is
obvious (in this case the left hand side of (10) has at most ${s}-1$ nonzero
terms), so from now on we suppose that $y>r-2$. Multiply (11) by
$(y-r+2)/(r-1)$ and add it to (10). Using ${x\choose
r-1}=(x-r+2)/(r-1)\times{x\choose r-2}$ (for all reals $x>r-2\geq 1$) after
rearrangements we get

$\displaystyle(C+C_{0})n^{r-2}$ $\displaystyle\geq$
$\displaystyle\sum_{i\geq{s}}\frac{y-x_{i}}{r-1}{x_{i}\choose r-2}$
$\displaystyle+\sum_{1\leq i\leq{s}-1}\frac{n-x_{i}}{r-1}{n\choose r-2}$
$\displaystyle+\sum_{1\leq i\leq{s}-1}\frac{x_{i}-y}{r-1}\left({n\choose
r-2}-{x_{i}\choose r-2}\right).$

The first and the third rows are non-negative. We obtain

$(r-1)(C+C_{0})n^{r-2}/{n\choose r-2}\geq\sum_{1\leq i\leq{s}-1}(n-x_{i}).$

So the left hand side is at most $b$ for $n\geq r^{2}$. ∎

Now we are ready to finish the proof of the theorem. By Lemma 17, for every
$1\leq i\leq{s}-1$,

$|\widehat{\mathcal{H}}(i)|={x_{i}\choose r-1}\geq{n-b\choose
r-1}\geq{n\choose r-1}-b{n\choose r-2}\geq{n\choose
r-1}-\frac{b}{(r-1)!}n^{r-2}.$

This completes the proof of Theorem 5 for $C_{1}=\frac{b}{(r-1)!}=3(C+C_{0})$.

#### Acknowledgment.

We thank a referee for helpful comments.

## References

  * [1] M. Deza, P. Erdős and P. Frankl, Intersection properties of systems of finite sets, Proc. London Math. Soc. (3) 36 (1978), 369–384.
  * [2] P. Erdős, and T. Gallai, On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356.
  * [3] P. Frankl, On families of finite sets no two of which intersect in a singleton. Bull. Austral. Math. Soc. 17 (1977), 125–134.
  * [4] P. Frankl, and Z. Füredi, Forbidding just one intersection. J. Combin. Th., Ser. A 39 (1985), 160–176.
  * [5] P. Frankl, and Z. Füredi, Exact solution of some Turán-type problems. J. Combin. Th., Ser. A 45 (1987), 226–262.
  * [6] Z. Füredi, On finite set-systems whose every intersection is a kernel of a star, Discrete Math. 47 (1983), 129–132.
  * [7] Z. Füredi, T. Jiang, A. Kostochka, D. Mubayi, and J. Verstraëte, Extremal problems for hypergraph blowups of trees. SIDMA 37 (2023), 2397–2416.
  * [8] Z. Füredi, and L. Özkahya, Unavoidable subhypergraphs: $\mathbf{a}$-clusters. J. Combin. Th., Ser. A 118 (2011), 2246–2256.
  * [9] A. McLennan, The Erdős-Sós conjecture for trees of diameter four. J. Graph Theory 49 (2005), no. 4, 291–301.