# Simple Juntas for Shifted Families

Peter Frankl  Andrey Kupavskii

###### Abstract

We say that a family $\mathcal{F}$ of $k$-element sets is a $j$-junta if there
is a set $J$ of size $j$ such that, for any $F$, its presence in
${\mathcal{F}}$ depends on its intersection with $J$ only. Approximating
arbitrary families by $j$-juntas with small $j$ is a recent powerful technique
in extremal set theory.

The weak point of all known junta approximation results is that they work in
the range $n>Ck$, where $C$ is an extremely fast growing function of the input
parameters, such as the quality of approximation or the number of families we
simultaneously approximate.

We say that a family ${\mathcal{F}}$ is shifted if for any
$F=\\{x_{1},\ldots,x_{k}\\}\in{\mathcal{F}}$ and any
$G=\\{y_{1},\ldots,y_{k}\\}$ such that $y_{i}\leq x_{i}$, we have
$G\in{\mathcal{F}}$. For many extremal set theory problems, including the
Erdős Matching Conjecture, or the Complete $t$-Intersection Theorem, it is
sufficient to deal with shifted families only.

In this paper, we present very general approximation by juntas results for
shifted families with explicit (and essentially linear) dependency on the
input parameters. The results are best possible up to some constant factors.
Moreover, they give meaningful statements for almost all range of values of
$n$. The proofs are shorter than the proofs of the previous approximation by
juntas results and are completely self-contained.

As an application of our junta approximation, we give a nearly-linear bound
for the multi-family version of the Erdős Matching Conjecture. More precisely,
we prove the following result. Let $n\geq 12sk\log(e^{2}s)$ and suppose that
the families ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k}$
do not contain $F_{1}\in{\mathcal{F}}_{1},\ldots,F_{s}\in{\mathcal{F}}_{s}$
such that $F_{i}$’s are pairwise disjoint. Then
$\min_{i}|{\mathcal{F}}_{i}|\leq{n\choose k}-{n-s+1\choose k}.$

title = Simple Juntas for Shifted Families, author = Peter Frankl and Andrey
Kupavskii, plaintextauthor = Peter Frankl, Andrey Kupavskii, plaintexttitle =
Simple Juntas for Shifted Families, runningtitle = Simple Juntas for Shifted
Families, runningauthor = Peter Frankl, Andrey Kupavskii, copyrightauthor = P.
Frankl, A. Kupavskii, keywords = extremal set theory, shifting, juntas,
year=2020, number=14, received=26 January 2019, published=3 September 2020,
doi=10.19086/da.14507,

[classification=text]

##  1 Introduction

Let $[n]:=\\{1,\ldots,n\\}$. We use the standard notation $2^{[n]}$ for the
power set of $[n]$ and ${[n]\choose k}$ for the family of all $k$-element
subsets of $[n]$. We say that a family $\mathcal{J}\subset 2^{[n]}$ is a
$j$-junta, if there exists a set $J\in{[n]\choose j}$ and a family
$\mathcal{J}^{*}\subset 2^{J}$ such that $\mathcal{J}=\\{F\subset[n]:F\cap
J\in\mathcal{J}^{*}\\}$. We call $J$ as above the center of the junta and
$\mathcal{J}^{*}$ the defining family.

We say that $\mathcal{F}\subset 2^{[n]}$ is $t$-intersecting if $|F_{1}\cap
F_{2}|\geq t$ for any two $F_{1},F_{2}\in{\mathcal{F}}$. We say “intersecting”
instead of “$1$-intersecting” for shorthand. Similarly, if for any
$A\in{\mathcal{A}}\subset 2^{[n]}$ and $B\in{\mathcal{B}}\subset 2^{[n]}$ we
have $|A\cap B|\geq t$, then we say that ${\mathcal{A}}$ and ${\mathcal{B}}$
are cross $t$-intersecting. We say “cross-intersecting” instead of “cross
$1$-intersecting” for shorthand. In a seminal paper [5], Dinur and Friedgut
proved the following theorem, which, informally speaking, states that the
structure of large intersecting families is governed by a small number of
coordinates.

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

There exist functions $j(r),c(r)$ such that for any integers $1<j(r)<k<n/2$,
if ${\mathcal{A}}\subset{[n]\choose k}$ is an intersecting family then there
exists an intersecting $j$-junta $\mathcal{J}$ with $j\leq j(r)$ and

$|\mathcal{F}\setminus\mathcal{J}|\leq c(r)\cdot{n-r\choose k-r}.$

This result is, in fact, a corollary of the analogous statement concerning
cross-intersecting families.

######  Theorem 2 ([5]).

There exist functions $j(r),c(r)\geq 1$ such that the following holds. Let
$n,a,b\in\mathbb{N}$ with $1<j(r)<b\leq a$ and $a+b<n$ and let
${\mathcal{A}}\subset{[n]\choose a},\ {\mathcal{B}}\subset{[n]\choose b}$ be
cross-intersecting.Then there exist cross-intersecting $j$-juntas
$\mathcal{J}$ and $\mathcal{I}$ with $j\leq j(r)$, such that

$|\mathcal{A}\setminus\mathcal{J}|\leq c(r)\cdot{n-r\choose a-r}\ \ \
\text{and}\ \ \ |\mathcal{B}\setminus\mathcal{J}|\leq c(r)\cdot{n-r\choose
b-r}.$

Clearly, these results are meaningful only for $n>Ck$ and $n>Ca$,
respectively, where $C=C(r)$ is sufficiently large (otherwise, say, in the
first result, we may have $C(r){n-r\choose k-r}\geq{n\choose k}$, in which
case the displayed inequality becomes trivial).

Recently, this result was greatly extended by Keller and Lifshitz [19] to the
so-called ‘Turan problems for expansions’. This, in particular, includes the
case of cross-dependent families. We say that
${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}$ are cross-dependent if there is
no choice $F_{1}\in{\mathcal{F}}_{1}\ldots,F_{s}\in{\mathcal{F}}_{s}$ such
that $F_{i}$ are pairwise disjoint.

######  Theorem 3 ([19]).

Let $s,r$ be some constants, $k<\frac{n}{2s}$, and consider cross-dependent
families ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k}$.
Then there exist $C=C(s,r)$ and cross-dependent $C$-juntas
$\mathcal{J}_{1},\ldots,\mathcal{J}_{s}\subset{[n]\choose k}$, such that for
each $i\in[s]$

$|\mathcal{F}_{i}\setminus\mathcal{J}_{i}|\leq C\cdot{n-r\choose k-r}.$

Again, the theorem only makes sense for $n>C^{\prime}(s,r)k$, and the
dependence of $C^{\prime}$ on $s,r$ is not explicit (and at least exponential
in $s,r$). In many cases, it is desirable to have a control of the behaviour
of $C^{\prime}(s,r)$. In particular, this is the case for the Erdős Matching
Conjecture (cf. [6], [10],[11]). We also note that, in some related settings,
the exponential dependence cannot be improved. This is, e.g., the case of
Friedgut’s junta theorem [13].

We say that the family ${\mathcal{F}}$ is shifted if for any
$F=\\{x_{1},\ldots,x_{k}\\}\in{\mathcal{F}}$ and any
$G=\\{y_{1},\ldots,y_{k}\\}$ such that $y_{i}\leq x_{i}$, we have
$G\in{\mathcal{F}}$. One makes the family shifted by performing shifts (see
definition in Section 3.2). We refer to the survey of the first author [9].
Shifting is a very useful combinatorial operation, which preserves many
properties of a family. In particular, it preserves the size of each set and
the family. Moreover, it preserves the property of being (cross-)
$t$-intersecting, cross-dependent etc. Thus, for many extremal problems
(including the Erdős Matching Conjecture, Ahlswede–Khachatrian theorem [2] and
their common generalization [12]), it is sufficient to restrict oneself to
shifted families.

The purpose of this note is to show that one can obtain junta-type results for
shifted families with essentially best possible dependencies on the parameters
(see the remark after Theorem 10) with purely combinatorial techniques.111All
previous junta-type theorems rely on results from discrete Fourier analysis.
In the next section, we illustrate our ideas by giving a simple proof of a
stronger version of Theorem 2 for shifted families. In Section 3, we give a
general junta approximation-type statement and deduce several of its
combinatorial implications, including a stronger version of Theorem 3 for
shifted families. In Section 4, we present the proofs of the junta
approximation results. In Section 5, we apply these results to obtain the
result on the multi-family version of the Erdős Matching Conjecture mentioned
in the abstract.

##  2 Cross $t$-intersecting families

Let us first illustrate our methods in the setting of Theorem 2.

######  Theorem 4.

Fix integers $a\geq b\geq r>t>0$ and shifted cross $t$-intersecting families
${\mathcal{A}}\subset{[n]\choose a}$ and ${\mathcal{B}}\subset{[n]\choose b}$.
Put $j:=2r-t-1$. If $n\geq 2a$ then there exist cross $t$-intersecting
$j$-juntas $\mathcal{J}$ and $\mathcal{I}$ with center $[j]$ such that

$|\mathcal{A}\setminus\mathcal{J}|\leq 2^{j}\cdot{n-j\choose a-r}\ \ \ \
\text{and}\ \ \ \ |\mathcal{B}\setminus\mathcal{I}|\leq 2^{j}\cdot{n-j\choose
b-r}.$ (1)

For a family ${\mathcal{F}}\subset 2^{[n]}$ and sets $X\subset S\subset[n]$ we
use the following notation:

${\mathcal{F}}(X,S):=\big{\\{}F\setminus X\ :\ F\in{\mathcal{F}},\ F\cap
S=X\big{\\}}.$

Note that ${\mathcal{F}}(X,S)$ is regarded as a subfamily of $2^{[n]\setminus
S}$.

In the proof of this theorem, we will use the following two lemmas. The first
lemma was proved by the first author (cf., e.g., Proposition 9.3 in [9]).

######  Lemma 5.

Assume that ${\mathcal{A}},{\mathcal{B}}$ are cross $t$-intersecting and
shifted. Fix $X,Y,s$, such that $X,Y\subset[s]$ and $|X\cap Y|\leq t-1$. Then
${\mathcal{A}}(X,[s])$ and ${\mathcal{B}}(Y,[s])$ are cross
$(t+s-|X|-|Y|)$-intersecting.

The second lemma was essentially proven in [7]. We give its proof for
completeness.

######  Lemma 6.

Let ${\mathcal{A}}^{\prime}\subset{[n^{\prime}]\choose a^{\prime}}$ and
${\mathcal{B}}^{\prime}\subset{[n^{\prime}]\choose b^{\prime}}$ be cross
$t^{\prime}$-intersecting. If $n^{\prime}\geq
2\max\\{a^{\prime},b^{\prime}\\}$ then either
$|{\mathcal{A}}^{\prime}|\leq{n^{\prime}\choose a^{\prime}-t^{\prime}}$ or
$|{\mathcal{B}}^{\prime}|\leq{n^{\prime}\choose b^{\prime}-t^{\prime}}$.

For the sake of completeness, we shall give its proof.

###### Proof of Lemma 6.

The proof consists of two propositions. Let us say that a set $F\subset[n]$
has property $t^{\prime}$ if there exists some $i\geq 0$ such that

$|F\cap[t^{\prime}+2i]|\geq t^{\prime}+i.$

######  Proposition 7 ([7]).

The number of sets $F\in{[n]\choose k}$, $k\geq t^{\prime}$, having property
$t^{\prime}$ is ${n\choose k-t^{\prime}}.$

###### Proof.

Interpret each $k$-element set $F$ as a random walk on $\mathbb{Z}^{2}$ from
point $(0,-t^{\prime})$ to $(n-k,k-t^{\prime})$, where at step $i$ we go one
up or one right depending on whether the $i$’th element belongs or does not
belong to $F$, respectively. Then the sets having property $t^{\prime}$ are
exactly the ones that correspond to random walks that hit the line $x=y$. By
reflection principle, the number of such walks is equal to the number of
shortest paths from $(-t^{\prime},0)$ to $(n-k,k-t^{\prime})$, which is
exactly ${n\choose k-t^{\prime}}$. ∎

######  Proposition 8.

Suppose that the shifted families
${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}\subset 2^{[n]}$ are cross
$t^{\prime}$-intersecting. Then either all $A\in{\mathcal{A}}^{\prime}$ have
property $t^{\prime}$ or all $B\in{\mathcal{B}}^{\prime}$ have property
$t^{\prime}+1$.

###### Proof.

Suppose that $A\in{\mathcal{A}}^{\prime}$ does not have property $t^{\prime}$.
Then, by shiftedness, a subset
$(1,2,\ldots,t^{\prime}-1,t^{\prime}+1,t^{\prime}+3,t^{\prime}+5,\ldots)$ is
in ${\mathcal{A}}^{\prime}$. By the cross $t^{\prime}$-intersecting property,
no subset of
$(1,2,\ldots,t^{\prime},t^{\prime}+2,t^{\prime}+4,t^{\prime}+6,\ldots)$ is in
${\mathcal{B}}^{\prime}$. By shiftedness, this implies that
${\mathcal{B}}^{\prime}$ has property $t^{\prime}+1$. ∎

Together, these two propositions imply that either
$|{\mathcal{A}}^{\prime}|\leq{n^{\prime}\choose a^{\prime}-t^{\prime}}$ or
$|{\mathcal{B}}^{\prime}|\leq{n^{\prime}\choose b^{\prime}-t^{\prime}-1}$. ∎

###### Proof of Theorem 4.

Let us put

$\displaystyle\mathcal{J}^{*}:=\ $ $\displaystyle\Big{\\{}J\subset[j]\ :\
|{\mathcal{A}}(J,[j])|>{n-j\choose a-r}\Big{\\}},\ \ \ \ $
$\displaystyle\mathcal{J}:=\ \Big{\\{}A\in{n\choose a}\ :\
A\cap[j]\in\mathcal{J}^{*}\Big{\\}};$ $\displaystyle\mathcal{I}^{*}:=\ $
$\displaystyle\Big{\\{}I\subset[j]\ :\ |{\mathcal{B}}(I,[j])|>{n-j\choose
b-r}\Big{\\}},\ \ \ \ $ $\displaystyle\mathcal{I}:=\ \Big{\\{}B\in{n\choose
b}\ :\ B\cap[j]\in\mathcal{J}^{*}\Big{\\}}.$

Note that $\mathcal{J}^{*}$ and $\mathcal{I}^{*}$ may contain the empty set.
We claim that $\mathcal{J}$ and $\mathcal{I}$ are the desired juntas. First,
by the definition, it is clear that $|{\mathcal{A}}\setminus\mathcal{J}|\leq
2^{j}{n-j\choose a-r}$, and similarly for ${\mathcal{B}}$ and $\mathcal{I}$.

Second, assume that $\mathcal{J}^{*}$ and $\mathcal{I}^{*}$ are not cross
$t$-intersecting. This implies that there are two sets $X\in\mathcal{J}^{*}$
and $Y\in\mathcal{I}^{*}$ such that $|X\cap Y|\leq t-1$. Denote
$x:=|X|,y:=|Y|$. Consider, the families
${\mathcal{A}}^{\prime}:={\mathcal{A}}(X,[j])$ and
${\mathcal{B}}^{\prime}:={\mathcal{B}}(Y,[j])$. Note that the former family
contains $(a-x)$-element sets and the latter contains $(b-y)$-element sets.
Due to Lemma 5, ${\mathcal{A}}^{\prime}$ and ${\mathcal{B}}^{\prime}$ are
cross $t^{\prime}$-intersecting, where $t^{\prime}=t+j-x-y=2r-1-x-y$. At the
same time,

$\displaystyle|{\mathcal{A}}^{\prime}|>$ $\displaystyle\ {n-j\choose a-r},$
(2) $\displaystyle|{\mathcal{B}}^{\prime}|>$ $\displaystyle\ {n-j\choose b-r}$
(3)

by the definition of $\mathcal{J},\mathcal{I}$. In particular, $x,y\leq r-1$.

Applying Lemma 6 to our situation with $n^{\prime}:=n-j,$ $a^{\prime}:=a-x$,
$b^{\prime}:=b-y$, $t^{\prime}:=2r-1-x-y$, we get that at least one of the
following two inequalities is valid:

$\displaystyle|{\mathcal{A}}^{\prime}|\leq$ $\displaystyle\
{n-j\choose(a-x)-t^{\prime}},$ (4) $\displaystyle|{\mathcal{B}}^{\prime}|\leq$
$\displaystyle\ {n-j\choose(b-x)-t^{\prime}}.$ (5)

We have $x,y\leq r-1$ and $j\geq r$, and thus
$(a-x)-t^{\prime}=a-r-(r-1-y)\leq a-r$. Thus, (4) contradicts (2). But,
similarly, (5) contradicts (3). Therefore, we conclude that choosing such $X$
and $Y$ was impossible in the first place. That is, $\mathcal{J}^{*}$ and
$\mathcal{I}^{*}$, and therefore $\mathcal{J}$ and $\mathcal{I}$, are cross
$t$-intersecting. ∎

One may argue that the constants in (1) are still quite bad. Let us derive the
following corollary, showing that, at the expense of slightly worse bounds on
$n$ and $j$, one can get rid of the constants.

######  Corollary 9.

Fix integers $a\geq b\geq r>t>0$ and shifted cross $t$-intersecting families
${\mathcal{A}}\subset{[n]\choose a}$ and ${\mathcal{B}}\subset{[n]\choose b}$.
For any $\epsilon>0$, put $j=2cr-t-1$, where
$c:=1+\Big{(}\frac{2+\epsilon}{2\epsilon}\Big{)}^{2}\log_{e}4$. If
$n\geq(2+\epsilon)a$ then there exists cross $t$-intersecting $j$-juntas
$\mathcal{J}$ and $\mathcal{I}$ with center $[j]$ such that

$|\mathcal{A}\setminus\mathcal{J}|\leq{n-r\choose a-r}\ \ \ \ \text{and}\ \ \
\ |\mathcal{B}\setminus\mathcal{J}|\leq{n-r\choose b-r}.$ (6)

###### Proof.

Apply Theorem 4 ${\mathcal{A}},{\mathcal{B}}$ with $cr$ playing the role of
$r$. Then we get cross $t$-intersecting juntas $\mathcal{I},\mathcal{J}$ with
center $[j]$, satisfying (1). To prove the corollary, it is sufficient to show
the second inequality in the following chain of inequalities:

$2^{j}{n-2cr+t+1\choose k-cr}\leq 2^{2cr}{n-(2c-1)r\choose
k-cr}\leq{n-r\choose k-r},$

where $k\in\\{a,b\\}$. We have

$\displaystyle\frac{{n-(2c-1)r\choose k-cr}}{{n-r\choose k-r}}\leq$
$\displaystyle\
\Big{(}\frac{k(n-k)}{n^{2}}\Big{)}^{(c-1)r}\leq\Big{(}\frac{1+\epsilon}{(2+\epsilon)^{2}}\Big{)}^{(c-1)r}=4^{-(c-1)r}\Big{(}1-\Big{(}\frac{2\epsilon}{2+\epsilon}\Big{)}^{2}\Big{)}^{(c-1)r}$
$\displaystyle\leq$ $\displaystyle\
4^{-(c-1)r}e^{-(c-1)\big{(}\frac{2\epsilon}{2+\epsilon}\big{)}^{2}r}=4^{-cr},$

where the second inequality in the first line holds due to the bound on $n$
and the fact that $x(1-x)$ is the biggest if $x$ is as close to $1/2$ as
possible, and the last inequality holds due to the choice of $c$. ∎

##  3 The general statement and its implications

In this section, we state a general junta approximation result and then deduce
several corollaries for shifted families satisfying different properties. Let
us present a geometric interpretation of the property that we are working
with.

First, consider the case of one family ${\mathcal{F}}$. Imagine that we are
given an $(n+1)\times(n+1)$ grid (thought of as a subset of the plane) and we
are walking on the grid starting from $(0,0)$ and at each step we can either
go from $(i,j)$ to $(i+1,j)$ or to $(i+1,j+1)$. The steps
$\\{i_{1},\ldots,i_{s}\\}$ of the walk at which the random walk goes
“diagonally” give us a set in $2^{[n]}$ and, obviously, there is a one-to-one
correspondence between the subsets in $2^{[n]}$ and such walks. The walks with
exactly $k$ diagonal steps correspond to $k$-element subsets of $[n]$. Thus,
any family ${\mathcal{F}}$ corresponds to a collection of walks on this grid.

Next, consider the line $\lambda$ defined by $\alpha y=x+q$ for some
$\alpha,q>0$ (here, by $x$ and $y$ we mean the coordinates on the plane). The
property that we are interested in is “any walk from ${\mathcal{F}}$ hits
$\lambda$ for some $x$”, where by hitting $\lambda$ we simply mean that
$\alpha y\geq x+q$ for the corresponding $(x,y)$.222Of course, $(x,y)$ is an
integer point.

As was noted long time ago by the first author [7, 8], there is a close
relationship between different combinatorial properties of ${\mathcal{F}}$ and
the property that ${\mathcal{F}}$ hits $\lambda$ for appropriately chosen
$\lambda$. Here, we explore this relationship further. Actually, this
relationship is the most transparent for the case of several families (i.e.,
in the “cross setting”).

It is easy to generalize the property of “hitting the line” to the case of
several families ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}$. Consider a
hyperplane $\pi$ defined by $\sum_{i=1}^{s}\alpha_{i}y_{i}=x+q$ for some
$\alpha_{i},q>0$. Represent each $F_{i}\in{\mathcal{F}}_{i}$ as a walk in the
coordinate plane spanned by $y_{i}$ and $x$. Then we are interested in the
property that the “joint walk (represented by the points
$(x,y_{1},\ldots,y_{s})$) hits the hyperplane $\pi$”.

For example, let us show how the cross $t$-intersecting property is related to
“hitting the plane” property. Consider two families
${\mathcal{F}}_{1},{\mathcal{F}}_{2}$ and assume that they hit the plane $\pi$
for $\pi$ defined by $y_{1}+y_{2}=x+t$. Then it is easy to see that
${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are cross $t$-intersecting:
indeed, for any $F_{1}\in{\mathcal{F}}_{1},\ F_{2}\in{\mathcal{F}}_{2}$ find
an integer point $\mathbf{p}:=(x,y_{1},y_{2})$ such that the joint walk hits
the plane $\pi$ at $\mathbf{p}$. In terms of sets, it means that
$|F_{1}\cap[x]|+|F_{2}\cap[x]|\geq x+t$, and by pigeon-hole principle, these
two sets intersect in at least $t$ elements, even restricted to $[x]$. More
importantly, if ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are cross
$t$-intersecting and shifted, then they must hit the plane $\pi$ (cf. [9] for
the easy proof)!

Finally, let us describe the idea that is behind the junta approximation
result below. For some of the lines, as $x$ grows, it gets increasingly more
and more unlikely that a random walk (biased random walk, or random walk with
fixed number of diagonal steps) hits this line at point $x$. Thus, a bulk of
the family must cross the line for small $x$ and stay under it for large $x$.
But it is easy to see that this part of the family is an $x$-junta with the
same “hitting the line” property. We have a similar situation for several
families, i.e., “sums” of random walks “hitting a hyperplane”.

In what follows, all the logarithms have base $e$.

######  Theorem 10.

Let $n,s\geq 2$ and $k_{1},\ldots,k_{s}$ be positive integers and $q$ be a
non-negative real number. Fix some positive reals
$\alpha_{1},\ldots,\alpha_{s}$ and a subset of positive integers $S$. For
$i\in[s]$, let ${\mathcal{F}}_{i}\subset{[n]\choose k_{i}}$ be such that for
any $F_{i}\in{\mathcal{F}}_{i},$ $i\in[s]$, there exists $\ell\in S$ such that

$\sum_{i=1}^{s}\alpha_{i}\big{|}F_{i}\cap[\ell]\big{|}\geq\ell+q.$ (7)

Fix a positive real $r=r(s)$. Then there exist juntas
$\mathcal{J}_{1}\subset{[n]\choose
k_{1}},\ldots,\mathcal{J}_{s}\subset{[n]\choose k_{s}}$ with center $[j]$ such
that for any $F_{i}\in\mathcal{J}_{i}$, $i\in[s]$ the inequality (7) holds
with some $\ell\in S\cap[j]$ and, moreover,

$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|\leq\Big{(}\frac{k_{i}}{n}\Big{)}^{r}{n\choose
k_{i}},$

provided one of the three conditions below holds for some real
$\epsilon\in(0,1/3]$.

  1. (i)

We have
$j:=\max_{i\in[s]}\\{\frac{4\sigma}{\epsilon^{2}k_{i}}\big{(}r\log\frac{\sigma}{(1-\epsilon)k_{i}}+\log\frac{8}{\epsilon^{2}}\big{)},\frac{\sigma
r}{\epsilon k_{i}}\\}$ and $n\geq(1-\epsilon)^{-1}\sigma,$ where
$\sigma:=\sum_{i=1}^{s}\alpha_{i}k_{i}$ and $\sigma\geq k_{i}$ for every $i$.

  2. (ii)

We have
$j:=\max_{i\in[s]}\big{\\{}\frac{4\alpha_{i}s}{\epsilon^{2}}\big{(}r\log\frac{\alpha_{i}s}{1-\epsilon}+\log\frac{8}{\epsilon^{2}}\big{)},r\alpha_{i}s\epsilon^{-1}\big{\\}}$
and $n\geq\max_{i\in[s]}(1-\epsilon)^{-1}\alpha_{i}sk_{i}.$

  3. (iii)

For some $C\geq 2$ we have
$j:=\max_{i\in[s]}\alpha_{i}sr\log_{C}(Ce\alpha_{i}s)$ and
$n\geq\max_{i\in[s]}Ce\alpha_{i}sk_{i}.$

Remarks.

  * •

Conditions (i) and (ii) in the theorem coincide when
$\alpha_{1}k_{1}=\ldots=\alpha_{s}k_{s}$, which is the case in many potential
applications.

  * •

We note that, unlike the previous results, our junta approximations work for
essentially the full range of $n$. Indeed, one can easily see that in general
these problems only make sense for $n\geq\sum_{i\in[s]}\alpha_{i}k_{i}$.

  * •

We note that, in general, we can get rid of the $\log$ factor in the
definition of $j$ by putting $r=C\log^{-1}(\sigma/k_{i})$. However, if we want
to get an approximation with, say,
$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|\leq{n-1\choose k_{i}-1}$, then
cannot remove $\log(\sigma/k_{i})$ from Theorem 10 and make both $j$ linear in
$s$ and $n$ linear in $sk$. Indeed, consider the problem of approximating one
$s$-matching-free family and assume that $j=Csr$ and $n=C^{\prime}sr$ for some
absolute $C$, $C^{\prime}$. ($s$ is sufficiently large.) Clearly, the best
center $J$ of size $j$ to take is $[j]$. Then consider the following
$s$-matching-free family $\mathcal{F}:=\\{F\in{[n]\choose k}:|F\cap[2j-1]|\geq
2Cr\\}$. The part of ${\mathcal{F}}$ that is not contained in the junta, has
size at least ${j-1\choose 2Cr}{n-2j-1\choose
k-2Cr}=\Omega\Big{(}\big{(}\frac{s}{2}\big{)}^{2Cr}\big{(}\frac{n}{k}\big{)}^{2Cr-r}\Big{)}\cdot{n-r\choose
k-r}=\Omega(s^{r}){n-r\choose k-r}$, where the $\Omega$-notation depends on
$C,C^{\prime},r$ only. Thus, ${\mathcal{F}}$ is not well-approximated by the
junta, provided $s$ is large enough.

For a set $F\subset[n],$ let us define the $p$-biased measure of $F$ by
$\mu_{p}(F):=p^{|F|}(1-p)^{n-|F|}$. For a family ${\mathcal{F}}\subset
2^{[n]}$, we put $\mu_{p}({\mathcal{F}}):=\sum_{F\in{\mathcal{F}}}\mu_{p}(F)$.
We can prove the following $p$-biased non-uniform analogue of Theorem 10. (It
should be helpful to think of $p_{i}$ as $k_{i}/n$.)

######  Theorem 11.

Let $n,s\geq 2$ be positive integers and $q$ be a non-negative real number.
Fix some positive real $\alpha_{1},\ldots,\alpha_{s}$ and
$p_{1},\ldots,p_{s}\in(0,1)$. Fix a subset of positive integers $S$. For
$i\in[s]$, let ${\mathcal{F}}_{i}\subset 2^{[n]}$ be such that for any
$F_{i}\in{\mathcal{F}}_{i},$ $i\in[s]$, there exists $\ell\in S$ such that
$F_{i}$ satisfy (7).

Fix a positive real number $r=r(s)$. Then there exist juntas
$\mathcal{J}_{1},\ldots,\mathcal{J}_{s}\subset 2^{[n]}$ with center $[j]$ such
that for any $F_{i}\in\mathcal{J}_{i}$, $i\in[s]$ the inequality (7) holds
with some $\ell\in S\cap[j]$ and, moreover,

$\mu_{p_{i}}({\mathcal{F}}_{i}\setminus\mathcal{J}_{i})\leq p_{i}^{r},$

provided one of the three conditions below holds for some real
$\epsilon\in(0,1/3]$.

  1. (i)

We have
$j:=\max_{i\in[s]}\\{\frac{4\sigma}{\epsilon^{2}p_{i}}\big{(}r\log\frac{\sigma}{(1-\epsilon)p_{i}}+\log\frac{8}{\epsilon^{2}}\big{)},\frac{\sigma
r}{\epsilon p_{i}}\\}$ and $n\geq(1-\epsilon)^{-1}\sigma,$ where
$\sigma:=\sum_{i=1}^{s}\alpha_{i}p_{i}$ and $\sigma\geq p_{i}$ for every $i$.

  2. (ii)

We have
$j:=\max_{i\in[s]}\big{\\{}\frac{4\alpha_{i}s}{\epsilon^{2}}\big{(}r\log\frac{\alpha_{i}s}{1-\epsilon}+\log\frac{8}{\epsilon^{2}}\big{)},r\alpha_{i}s\epsilon^{-1}\big{\\}}$
and $\max_{i\in[s]}\alpha_{i}sp_{i}\leq(1-\epsilon).$

  3. (iii)

For some $C\geq 2$ we have
$j:=\max_{i\in[s]}\alpha_{i}rs\log_{C}(Ce\alpha_{i}s)$ and
$\max_{i\in[s]}Ce\alpha_{i}sp_{i}\leq 1.$

The proof of Theorem 11 is almost the same as that of Theorem 10. Moreover,
the calculations become easier.

###  3.1 Combinatorial consequences

The first consequence is for families satisfying a cross-union condition. Note
that the case $q=1$ corresponds to cross-dependence.

######  Theorem 12.

Let $s\geq 2$ be an integer and $\epsilon\in(0,1/3]$, $r=r(s)$ be positive
real numbers. For $i\in[s]$, let ${\mathcal{F}}_{i}\subset{[n]\choose k_{i}}$
be such that $|F_{1}\cup\ldots\cup F_{s}|\leq k_{1}+\ldots+k_{s}-q$ for some
integer $q>0$. Assume that ${\mathcal{F}}_{i}$ are shifted. Then there exist
juntas $\mathcal{J}_{1}\subset{[n]\choose
k_{1}},\ldots,\mathcal{J}_{s}\subset{[n]\choose k_{s}}$ with center $[j]$ such
that for each $i$

$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|\leq\Big{(}\frac{k_{i}}{n}\Big{)}^{r}{n\choose
k_{i}}$

and for any $F_{i}\in\mathcal{J}_{i}$, $i\in[s]$, we have
$|F_{1}\cup\ldots\cup F_{s}|\leq k_{1}+\ldots+k_{s}-q$, provided one of the
following conditions holds.

  1. (i)

We have
$j:=\max_{i\in[s]}\\{\frac{4\sigma}{\epsilon^{2}k_{i}}\big{(}r\log\frac{\sigma}{(1-\epsilon)k_{i}}+\log\frac{8}{\epsilon^{2}}\big{)},\frac{\sigma
r}{\epsilon k_{i}}\\}$ and $n\geq(1-\epsilon)^{-1}\sigma,$ where
$\sigma:=\sum_{i=1}^{s}k_{i}$.

  2. (ii)

We have
$j:=\frac{4s}{\epsilon^{2}}\big{(}r\log\frac{s}{1-\epsilon}+\log\frac{8}{\epsilon^{2}}\big{)}$
and $n\geq\max_{i\in[s]}(1-\epsilon)^{-1}sk_{i}.$

  3. (iii)

For some $C\geq 2$ we have $j:=rs\log_{C}(Ces)$ and
$n\geq\max_{i\in[s]}Cesk_{i}.$

Let us derive one particular corollary of this result.

######  Corollary 13.

For each $C,s\geq 2$ and $\epsilon=C^{-\alpha}$, $\alpha>0$ the following
holds. If $n=Cks$, and
${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k}$ are shifted
cross-dependent families, then there exist cross-dependent
$\big{(}2(1+\alpha)s\big{)}$-juntas $\mathcal{J}_{1},\ldots,\mathcal{J}_{s}$
on the same center, such that
$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|<\epsilon s\binom{n-1}{k-1}$ for
each $i$.

###### Proof.

Apply Theorem 12 (iii) with $k_{1}=\ldots=k_{s}=k$ and
$r=\log_{n/k}\frac{n}{{\varepsilon}ks}=\log_{Cs}C^{1+\alpha}=\frac{1+\alpha}{\log_{C}(Cs)}$.
Then
$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|\leq\big{(}\frac{k}{n}\big{)}^{r}{n\choose
k}=\frac{{\varepsilon}ks}{n}{n\choose k}={\varepsilon}s{n-1\choose k-1}$. At
the same time, we have

$j=rs\log_{C}(Ces)=(1+\alpha)s\frac{\log_{C}(Ces)}{\log_{C}(Cs)}<2(1+\alpha)s,$

where the last inequality is valid since $Cs>e$. ∎

The validity of Corollary 13 for not necessarily shifted families, but with
unspecified dependencies between constants $C,{\varepsilon}$ and $C^{\prime}$,
where the juntas have center of size $C^{\prime}s$, was announced by Keevash,
Lifshitz, Long, and Minzer as a consequence of general sharp threshold-type
results (for the latter, see [18]).

###### Proof of Theorem 12.

The following proposition is a consequence of the shiftedness of
${\mathcal{F}}_{i}$ (see [9]).

######  Proposition 14.

For any $F_{i}\in{\mathcal{F}}_{i}$, $i\in[s]$, there exists $\ell$ such that

$\sum_{i=1}^{s}|F_{i}\cap[\ell]|\geq\ell+q.$ (8)

###### Idea of the proof.

Assuming the contrary, it is not difficult to find shifts of $F_{i}$ that
would not satisfy $|F_{1}\cup\ldots\cup F_{s}|<k_{1}+\ldots+k_{s}-q$. ∎

Now we can apply Theorem 10 (in one of the three assumptions on $j,n$) to
${\mathcal{F}}_{i}$ with $\alpha_{1}=\ldots=\alpha_{s}=1$ and $S:=[n]$. This
gives us the juntas that satisfy (8). However, it is then clear that for any
$F_{i}\in\mathcal{J}_{i}$, $i\in[s]$, we have $|F_{1}\cup\ldots\cup F_{s}|\leq
k_{1}+\ldots+k_{s}-q$. ∎

######  Theorem 15.

Let $s\geq 2$, $t\geq 1$ be integers and $\epsilon\in(0,1/3]$, $r=r(s)$ be
positive real numbers. For $i\in[s]$, let ${\mathcal{F}}_{i}\subset{[n]\choose
k_{i}}$ be such that $|F_{1}\cap\ldots\cap F_{s}|\geq t$. Moreover, assume
that ${\mathcal{F}}_{i}$ are shifted. Then there exists juntas
$\mathcal{J}_{1}\subset{[n]\choose
k_{1}},\ldots,\mathcal{J}_{s}\subset{[n]\choose k_{s}}$ with center $[j]$ such
that for each $i$

$|{\mathcal{F}}_{i}\setminus\mathcal{J}_{i}|\leq\Big{(}\frac{k_{i}}{n}\Big{)}^{r}{n\choose
k_{i}}$

and such that for any $F_{i}\in\mathcal{J}_{i}$, $i\in[s]$, we have
$|F_{1}\cap\ldots\cap F_{s}|\geq t$, provided that one of the following
conditions holds.

  1. (i)

We have
$j:=\max_{i\in[s]}\\{\frac{4\sigma}{\epsilon^{2}k_{i}}\big{(}r\log\frac{\sigma}{(1-\epsilon)k_{i}}+\log\frac{8}{\epsilon^{2}}\big{)},\frac{\sigma
r}{\epsilon k_{i}}\\}$ and $n\geq(1-\epsilon)^{-1}\sigma,$ where
$\sigma:=\sum_{i=1}^{s}\frac{k_{i}}{s-1}$.

  2. (ii)

We have
$j:=\max\big{\\{}\frac{8}{\epsilon^{2}}\big{(}r\log\frac{s}{(s-1)(1-\epsilon)}+\log\frac{8}{\epsilon^{2}}\big{)},\frac{rs}{\epsilon(s-1)}\big{\\}}$
and $n\geq\max_{i\in[s]}(1-\epsilon)^{-1}\frac{s}{s-1}k_{i}.$

  3. (iii)

We have $j:=3sr$ and $n\geq 2e^{2}k.$

###### Proof.

The proof is very similar to the previous one. Due to shiftedness of
${\mathcal{F}}_{i}$, for any $F_{i}\in{\mathcal{F}}_{i},$ $i\in[r]$, we must
have

$\sum_{i=1}^{s}\frac{1}{s-1}\big{|}F_{i}\cap[\ell]\big{|}\geq\ell+\frac{t}{s-1}.$

Then apply Theorem 10 with $q:=\frac{t}{s-1}$,
$\alpha=\alpha_{i}:=\frac{1}{s-1}$ (and $C=e$ for part (iii)). ∎

Analogous consequences for non-uniform families can be obtained from the
$p$-biased Theorem 11. Since it is straightforward, we leave the details to
the reader.

###  3.2 Why do juntas necessarily have center $\mathbf{[j]}$?

In this subsection, we prove a simple and intuitive statement that juntas
approximating shifted families should have center $[j]$.

For a given pair of indices $1\leq u<v\leq n$ and a set $A\subset[n]$, define
its $(u\leftarrow v)$-shift $S_{u\leftarrow v}(A)$ as follows. If $u\in A$ or
$v\notin A$, then $S_{u\leftarrow v}(A)=A$. If $v\in A,u\notin A$, then
$S_{u\leftarrow v}(A):=(A-\\{v\\})\cup\\{u\\}$. That is, $S_{u\leftarrow
v}(A)$ is obtained from $A$ by replacing $v$ with $u$. The $(u\leftarrow
v)$-shift $S_{u\leftarrow v}(\mathcal{A})$ of a family $\mathcal{A}$ is as
follows:

$S_{u\leftarrow v}(\mathcal{A}):=\\{S_{u\leftarrow
v}(A)\,:\,A\in\mathcal{A}\\}\cup\\{A\,:\,A,S_{u\leftarrow
v}(A)\in\mathcal{A}\\}.$

######  Proposition 16.

Suppose that $\mathcal{I}\subset 2^{[n]}$ is a junta with center $I$ of size
$j$ defined by family $\mathcal{I}^{*}$. Assume that ${\mathcal{F}}\subset
2^{[n]}$ is shifted and satisfies $|{\mathcal{F}}\setminus\mathcal{I}|\leq w$.
Then, for any $u<v$, the junta $\mathcal{J}$ with center $S_{u\leftarrow
v}(I)$ and defined by the family $S_{u\leftarrow v}(\mathcal{I}^{*})$
satisfies $|{\mathcal{F}}\setminus\mathcal{J}|\leq w$.

Obviously, after several such $u\leftarrow v$-shifts, the center becomes $[j]$
for $j=|I|$. Moreover, if we are shifting several juntas with center $I$ at
the same time, their combinatorial properties are preserved, since the juntas
stay the same up to relabeling of the vertices.

###### Proof.

It is clearly sufficient to deal with the case $I\cap\\{u,v\\}=v$. Let us
construct an injective map $\phi$ from ${\mathcal{F}}\setminus\mathcal{J}$
into ${\mathcal{F}}\setminus\mathcal{I}$. If
$F\in{\mathcal{F}}\setminus\mathcal{J}$ satisfies $|F\cap\\{u,v\\}|\neq 1$,
then $F\in{\mathcal{F}}\setminus\mathcal{I}$ as well, and we put $\phi(F)=F$.
If $|F\cap\\{u,v\\}|=1$, then $F\in\mathcal{I}$ if and only if
$F\oplus\\{u,v\\}\in\mathcal{J}$. We then put $\phi(F)=F\oplus\\{u,v\\}$ if
$F\oplus\\{u,v\\}\in{\mathcal{F}}$. Due to shiftedness, we are only left to
deal with $F$, such that $F\cap\\{u,v\\}=\\{u\\}$ and such that
$F\oplus\\{u,v\\}\notin{\mathcal{F}}$. But if such $F$ does not belong to
$\mathcal{J}$, then $F$ does not belong to $\mathcal{I}$ (because
$S_{u\leftarrow v}(F)=F$). Therefore, we can put $\phi(F)=F$ for such $F$. ∎

##  4 Proofs of Theorems 10 and 11

###  4.1 Theorem 10

For each $i\in[s]$, let us put

${\mathcal{F}}^{\prime}_{i}:=\big{\\{}F\in{\mathcal{F}}_{i}:\big{|}F\cap[\ell]\big{|}\geq\ell\cdot\frac{k_{i}}{\sigma}\text{
for some }\ell>j\big{\\}},\ \ \ \
{\mathcal{F}}^{\prime\prime}_{i}:={\mathcal{F}}_{i}\setminus{\mathcal{F}}^{\prime}_{i}.$

Let us put

$\mathcal{J}_{i}:=\Big{\\{}G\in{[n]\choose k_{i}}:G\cap[j]=F\cap[j]\text{ for
some }F\in{\mathcal{F}}^{\prime\prime}_{i}\Big{\\}}.$

The following is the key property of sets in
${\mathcal{F}}^{\prime\prime}_{i}$.

######  Proposition 17.

For any
$F^{\prime\prime}_{1}\in{\mathcal{F}}^{\prime\prime}_{1}\ldots,F^{\prime\prime}_{s}\in{\mathcal{F}}^{\prime\prime}_{s}$,
the property (7) holds for some $\ell\in S\cap[j]$.

###### Proof.

If not, then (7) must hold for some $\ell>j$ by the hypothesis. But, by
definition of ${\mathcal{F}}^{\prime\prime}_{i}$, we have
$\alpha_{i}|F^{\prime\prime}_{i}\cap[\ell]|<\alpha_{i}k_{i}\ell/\sigma$ for
any $F^{\prime\prime}_{i}\in{\mathcal{F}}^{\prime\prime}_{i}$ and $\ell>j$,
and thus
$\sum_{i=1}^{s}\alpha_{i}|F^{\prime\prime}_{i}\cap[\ell]|<\ell\leq\ell+q$, a
contradiction.∎

Let us note the following simple facts:

  * •

Each $\mathcal{J}_{i}$ is a $j$-junta with center in $[j]$.

  * •

We have ${\mathcal{F}}^{\prime\prime}_{i}\subset\mathcal{J}_{i}$.

  * •

For any $F_{1}\in\mathcal{J}_{1},\ldots,F_{s}\in\mathcal{J}_{s}$ we have
$\sum_{i=1}^{s}\alpha_{i}|F_{i}\cap[\ell]|\geq\ell+q$ for some $\ell\in
S\cap[j]$. Indeed, by Proposition 17 this inequality holds for any
$F^{\prime\prime}_{1}\in{\mathcal{F}}^{\prime\prime}_{1},\ldots,F^{\prime\prime}_{s}\in{\mathcal{F}}^{\prime\prime}_{s}$.
But, by definition, $F_{i}\cap[j]=F^{\prime\prime}_{i}\cap[j]$ for some
$F^{\prime\prime}_{i}\in{\mathcal{F}}^{\prime\prime}_{i}$.

To conclude the proof that $\mathcal{J}_{i}$ are the desired juntas, we are
only left to show that

######  Proposition 18.

We have
$|{\mathcal{F}}^{\prime}_{i}|\leq\big{(}\frac{k_{i}}{n}\big{)}^{r}{n\choose
k_{i}}$.

###### Proof.

Partition $F\in{\mathcal{F}}^{\prime}_{i}$ into classes by the maximum value
of $\ell$, for which $|F\cap[\ell]|\geq k_{i}\ell/\sigma$. Obviously, $\ell$
must have the form $g(t):=\lfloor\sigma t/k_{i}\rfloor$ for integer
$t\in[k_{i}j/\sigma,k_{i}]$. Since it does not affect the calculations and
simplifies the presentation, in what follows we shall treat $\sigma t/k_{i}$
for each $t$ as an integer (and thus assume that $g(t)=\sigma t/k_{i}$). Thus,
we have

$|{\mathcal{F}}^{\prime}_{i}|\leq\sum_{t=k_{i}j/\sigma}^{k_{i}}{g(t)\choose
t}{n-g(t)\choose
k_{i}-t}=\sum_{t=k_{i}j/\sigma}^{k_{i}}h\big{(}t,n,k_{i},g(t)\big{)},$ (9)

where $h(x,n,k,T)=\Pr[X=x]$ for $X\sim H(n,k,T)$, the hypergeometric
distribution $H(n,k,T)$. Recall that $H(n,k,T)$ is the distribution of the
size of the intersection of a uniformly random $k$-element subset of $[n]$
with a fixed set of size $T$. Take a random variable $X\sim
H\big{(}n,k_{i},g(t)\big{)}$. Then the expectation $\mathrm{E}X$ of $X$
satisfies $\mathrm{E}X=\frac{g(t)k_{i}}{n}=\frac{\sigma
t}{n}\leq(1-{\varepsilon})t$ due to our choice of $n$. On the one hand,

$h(t,n,k_{i},g(t))\leq\Pr[X\geq t].$ (10)

On the other hand, it is known (see, e.g., [16, Theorem 2.10]) that

$\mathrm{E}e^{uX}\leq\mathrm{E}e^{uY}$ (11)

for any real $u$ and $Y\sim Bin(g(t),k_{i}/n)$ (note that
$\mathrm{E}Y=\mathrm{E}X\leq(1-{\varepsilon})t$).

Recall the following Chernoff-type inequality for $Y^{\prime}\sim Bin(m,p)$
and $a>0$ (cf., e.g., [3, Theorem A.1.11]):

$\Pr[Y^{\prime}-\mathrm{E}Y^{\prime}\geq
a]<e^{-\frac{a^{2}}{2pm}+\frac{a^{3}}{2(pm)^{2}}}.$

This inequality is proved using the moment generating function, and thus
applies to $X$ as well due to (11). Recall that $\epsilon\leq 1/3$ and take
$Y^{\prime}\sim Bin(g(t),p)$, where $p\geq\frac{k_{i}}{n}$ is such that
$\mathrm{E}Y^{\prime}=(1-{\varepsilon})t$. We get that

$\Pr[X\geq t]\leq\Pr[Y\geq
t]\leq\Pr\big{[}Y^{\prime}-\mathrm{E}Y^{\prime}\geq\epsilon
t\big{]}<\exp\Big{[}-\frac{\epsilon^{2}t}{2(1-\epsilon)}+\frac{\epsilon^{3}t}{2(1-\epsilon)^{2}}\Big{]}<\exp\Big{[}-\frac{\epsilon^{2}t}{4(1-\epsilon)}\Big{]}<e^{-\epsilon^{2}t/4}.$

Using the displayed bound above and (10), we get that

$\sum_{t=k_{i}j/\sigma}^{k_{i}}h\big{(}t,n,k_{i},g(t)\big{)}\leq\sum_{t=k_{i}j/\sigma}^{\infty}e^{-\epsilon^{2}t/4}\leq
e^{-\epsilon^{2}k_{i}j/(4\sigma)}\cdot\frac{1}{1-e^{-\epsilon^{2}/4}}\leq
e^{-\epsilon^{2}k_{i}j/(4\sigma)}\cdot\frac{8}{\epsilon^{2}},$

where the last bound is due to the fact $e^{-x}\leq 1-x/2$ for $x<1$. Due to
our choice of $j$, we get that

$\sum_{t=k_{i}j/\sigma}^{k_{i}}f_{t}\leq
e^{-r\log\frac{k_{i}}{(1-\epsilon)\sigma}-\log\frac{8}{\epsilon^{2}}}\cdot\frac{8}{\epsilon^{2}}=\Big{(}\frac{(1-\epsilon)k_{i}}{\sigma}\Big{)}^{r},$

and therefore $\sum_{t=k_{i}j/\sigma}^{k_{i}}f_{t}\cdot(n/k_{i})^{r}\leq 1$
for $n=(1-\epsilon)^{-1}\sigma$. As we have already mentioned, this implies
that the same inequality holds for $f_{t}(n)$ for any
$n\geq(1-\epsilon)^{-1}\sigma$. Combining everything together, we have
$|{\mathcal{F}}^{\prime}_{i}|/{n\choose
k_{i}}\leq\sum_{t=k_{i}j/\sigma}^{k}f_{t}(n)\leq(k_{i}/n)^{r}$. This concludes
the proof of the proposition. ∎

The second part of Theorem 10 is proven analogously, with the only difference
that we define ${\mathcal{F}}_{i}^{\prime},{\mathcal{F}}_{i}^{\prime\prime}$
as follows:

${\mathcal{F}}^{\prime}_{i}:=\big{\\{}F\in{\mathcal{F}}_{i}:|F\cap[\ell]|\geq\ell\cdot\frac{s}{\alpha_{i}}\text{
for some }\ell>j\big{\\}},\ \ \ \
{\mathcal{F}}^{\prime\prime}_{i}:={\mathcal{F}}_{i}\setminus{\mathcal{F}}^{\prime}_{i},$

and $g^{\prime}_{i}(t):=\alpha_{i}st$ (again assumed to be integer) plays the
role of $g(t)$.

For part (iii) of Theorem 10, we do a slightly different estimate in the proof
of Proposition 18. Put $t_{0}:=j/(\alpha_{i}s)$ and note that $t_{0}\geq
r\log_{C}(Ce\alpha_{i}s)=r+r\log(e\alpha_{i}s)$ by our choice of $j$. We have

$|{\mathcal{F}}^{\prime}_{i}|\leq\sum_{t=t_{0}+1}^{k_{i}}{g^{\prime}(t)\choose
t}{n-g^{\prime}(t)\choose k_{i}-t}.$ (12)

Note that if $g^{\prime}(t)<t$ then the corresponding term in the sum is zero.
Thus, in what follows we assume that $g^{\prime}(t)\geq t$. We show that
$|{\mathcal{F}}_{i}^{\prime}|\leq\big{(}\frac{k_{i}}{n}\big{)}^{r}{n\choose
k_{i}}$. Indeed,

$\Big{(}\frac{k_{i}}{n}\Big{)}^{r}{n\choose k_{i}}/{n-g^{\prime}(t)\choose
k_{i}-t}\geq\Big{(}\frac{n}{k_{i}}\Big{)}^{t-r}\geq(Ce\alpha_{i}s)^{t-r}.$
(13)

On the other hand,

${g^{\prime}(t)\choose
t}\leq\Big{(}\frac{eg^{\prime}(t)}{t}\Big{)}^{t}\leq(e\alpha_{i}s)^{t}.$

Combining the two bounds above, we obtain

$\frac{|{\mathcal{F}}_{i}^{\prime}|}{\big{(}\frac{k_{i}}{n}\big{)}^{r}{n\choose
k_{i}}}\
\leq\sum_{t=t_{0}+1}^{k_{i}}\frac{(e\alpha_{i}s)^{t}}{(Ce\alpha_{i}s)^{t-r}}=\sum_{t=t_{0}+1}^{k_{i}}\frac{(e\alpha_{i}s)^{r}}{C^{t-r}}\leq\frac{(e\alpha_{i}s)^{r}}{C^{t_{0}-r}}\leq\frac{(e\alpha_{i}s)^{r}}{C^{r\log_{C}(e\alpha_{i}s)}}=1.$

###  4.2 Theorem 11

The first part of the proof repeats word for word the proof of Theorem 10,
with an obvious replacement of ${[n]\choose k}$ by $2^{[n]}$ in the definition
of $\mathcal{J}_{i}$. The only difference is that we need another version of
Proposition 17:

######  Proposition 19.

We have $\mu_{p}({\mathcal{F}}^{\prime}_{i})\leq p_{i}^{r}$.

###### Proof.

With the same definition of $g(t)$ (and the same convention concerning
omitting integer parts), we get that

$\mu_{p}({\mathcal{F}}^{\prime}_{i})\leq\sum_{t=p_{i}j/\sigma}^{n}{g(t)\choose
t}p_{i}^{t}(1-p_{i})^{g(t)-t}.$

An individual term of this sum is $\Pr[Y=t]$, where $Y\sim Bin(g(t),p_{i})$.
It is at most $\Pr\big{[}Y^{\prime}-\mathrm{E}Y^{\prime}\geq\epsilon
t\big{]}$, where $Y^{\prime}\sim Bin(g(t),p)$ and $p\geq p_{i}$ is chosen so
that $\mathrm{E}Y^{\prime}=(1-{\varepsilon})t$. The remainder of the proof is
identical to that of part (i) of Theorem 10.

The proof goes similarly for the second and the third part of the theorem. ∎

##  5 Families with no cross-matching

As an application of Theorem 12, we prove an exact bound concerning cross-
dependent families. The following question was addressed by Aharoni and Howard
[1], as well as by Huang, Loh and Sudakov [14]. Given
${\mathcal{F}}_{1}\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k}$ that are
cross-dependent,333Recall that cross-dependence means that there are no sets
$F_{1}\in{\mathcal{F}}_{1},\ldots,F_{s}\in{\mathcal{F}}_{s}$ that are pairwise
disjoint. find $\min_{i\in[s]}|{\mathcal{F}}_{i}|$. (We note here that some
authors use the term “${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}$ contain a
rainbow matching” to refer to the situation, opposite to “cross-dependence”.)
In [14], Huang, Loh and Sudakov proved the following result.

######  Theorem 20.

If $n>3sk^{2}$ and
${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k}$ are cross-
dependent then

$\min_{i\in[s]}|{\mathcal{F}}_{i}|\leq{n\choose k}-{n-s+1\choose k}.$ (14)

Later, a version of this theorem for families with different uniformity was
obtained by Lu and Yu [21]. They have also managed to obtain an inequality of
the product of sizes of cross-dependent families, partially answering one of
the questions of [14]. In [15], Huang, Li and Wang obtained a similar result
for a stronger notion of a rainbow matching.

As it is easily guessed from the formula, the bound is attained by the
families ${\mathcal{F}}_{1}=\ldots={\mathcal{F}}_{s}=\\{F\in{[n]\choose
k}:F\cap[s-1]\neq\emptyset\\}$.

The bound (14) was obtained for $n>f(s)k$ with some unspecified and very fast
growing function $f(s)$ by Keller and Lifshitz in [19] as an application of
the junta method. We recommend the reader to consult [19] for more advanced
applications of the junta method. The proof of the next theorem follows the
framework proposed by the authors of [19]. Our junta approximation gives an
almost linear bound.

######  Theorem 21.

The statement of Theorem 20 holds for $n\geq 12ks\log(e^{2}s)$.

###### Proof.

Since shifting maintains cross-dependence (cf. [9]), we may assume that
${\mathcal{F}}_{i}$, $i\in[s]$, are shifted. Let us apply Theorem 12 part
(iii) with $q=1$, $k_{1}=\ldots=k_{s}=k$, $C=e$ and $r=3$. We get cross-
dependent $j$-juntas $\mathcal{J}_{1},\ldots,\mathcal{J}_{s}$ with
$j=3s\log(e^{2}s)$ and such that
$|\mathcal{J}_{i}\setminus{\mathcal{F}}_{i}|\leq\frac{k^{3}}{n^{3}}{n\choose
k}$. In particular, if $\min_{i\in[s]}|{\mathcal{F}}_{i}|\geq{n\choose
k}-{n-s+1\choose k}$, then $\min_{i\in[s]}|\mathcal{J}_{i}|\geq{n\choose
k}-{n-s+1\choose k}-\frac{k^{3}}{n^{3}}{n\choose k}$.

The proof consists of two steps. The first step is to show that the juntas
must have the structure of the (conjectured) extremal family. We will need the
following lemma proved by Huang, Loh and Sudakov [14].

######  Lemma 22.

Let ${\mathcal{G}}_{1}\subset{X\choose
t_{1}},\ldots,{\mathcal{G}}_{l}\subset{X\choose t_{l}}$ be cross-dependent and
$\sum_{i=1}^{l}t_{i}\leq|X|$. Then there exists $i$ such that
$|{\mathcal{G}}_{i}|\leq(l-1){|X|-1\choose t_{i}-1}$.

Recall that we use the following notation: for any family $\mathcal{G}\subset
2^{[m]}$ and $X\subset Y\subset[m]$, put

$\mathcal{G}(X,Y):=\big{\\{}G\setminus X:G\in{\mathcal{G}},G\cap
Y=X\big{\\}}.$

######  Lemma 23.

If $\min_{i\in[s]}|\mathcal{J}_{i}|\geq{n\choose k}-{n-s+1\choose
k}-\frac{k^{3}}{n^{3}}{n\choose k}$, then we have
$\mathcal{J}_{1}=\ldots=\mathcal{J}_{s}=\big{\\{}F\in{[n]\choose
k}:F\cap[s-1]\neq\emptyset\big{\\}}.$

###### Proof.

Consider the defining family $\mathcal{J}^{*}_{i}$ of $\mathcal{J}_{i}$. If
$\mathcal{J}^{*}_{i}$ contains $l$ singletons for some $l\in[s-1]$, then these
singletons must be $1,\ldots,l$ due to shiftedness. Clearly, if each
$\mathcal{J}^{*}_{i}$ contain $s-1$ singletons, then they cannot contain any
sets disjoint to $[s-1]$, and the claim is proved.

W.l.o.g., assume that $\mathcal{J}^{*}_{1}$ does not contain $\\{s-1\\}$.
Consider a bipartite graph $G$ between $\\{1\\},\ldots,\\{s-1\\}$ and
$\mathcal{J}^{*}_{2},\ldots,\mathcal{J}^{*}_{s}$, where an edge between a
singleton and a family is drawn if and only if the singleton belongs to the
family. Take a maximal (non-extendable) matching in this graph, such that the
singletons cover the initial segment $[s-l]$, where $l\geq 1$ is an integer.
W.l.o.g., assume the families that are not matched are
$\mathcal{J}^{*}_{1},\ldots,\mathcal{J}^{*}_{l}$ (note that
$\mathcal{J}^{*}_{1}$ is not matched since it was not included in the graph).
Consider the families
$\mathcal{I}^{*}_{i}:=\mathcal{J}^{*}_{i}(\emptyset,[s-l])$ and
$\mathcal{I}_{i}:=\mathcal{J}_{i}(\emptyset,[s-l])$, $i=1,\ldots,l$. The
former are the families on $2^{X}$ for $X:=[s-l+1,j]$ and none of these
families contain a singleton due to the maximality of the chosen matching.

If $l=1$ then $\mathcal{J}^{*}_{1}(\emptyset,[s-2])$ can only contain sets
containing $s-1$ (otherwise, $\mathcal{J}_{1},\ldots,\mathcal{J}_{s}$ are not
cross-dependent). Thus $|\mathcal{J}_{1}|\leq{n\choose k}-{n-s+1\choose
k}-{n-j\choose k-1}<{n\choose k}-{n-s+1\choose k}-\frac{k^{3}}{n^{3}}{n\choose
k}$, where the last inequality is valid for $n>2kj$.

From now on, we assume that $l\geq 2$. Our next goal is to prove that

$\text{one of }\mathcal{I}_{1},\ldots,\mathcal{I}_{l}\text{ has size smaller
than }{n-s+l\choose k}-{n-s+1\choose k}-\frac{k^{3}}{n^{3}}{n\choose k}.$ (15)

Since $|\mathcal{J}_{i}\setminus\mathcal{I}_{i}|\leq{n\choose k}-{n-s+l\choose
k}$, this and
$|\mathcal{J}_{i}|=|\mathcal{J}_{i}\setminus\mathcal{I}_{i}|+|\mathcal{I}_{i}|$
would lead to a contradiction.

For each $t=2,\ldots,k$, consider

$\mathcal{I}^{(t)}_{i}:=\mathcal{I}_{i}^{*}\cap{X\choose t}.$

The families $\mathcal{I}^{(t_{1})}_{1},\ldots,\mathcal{I}^{(t_{l})}_{l}$ are
cross-dependent for any $t_{1}\ldots,t_{l}$. The following claim is crucial in
bounding the size of $\mathcal{I}_{i}$.

######  Claim 24.

For any $\beta_{2},\ldots,\beta_{k}\geq 0,$ there is $i$ such that
$\sum_{t=2}^{k}\beta_{t}|\mathcal{I}_{i}^{(t)}|\leq\sum_{t=2}^{k}\beta_{t}l{j-1\choose
t-1}$.

###### Proof.

Assume that this does not hold. Then, for each $i\in[l]$, there is $t_{i}$
such that $|\mathcal{I}_{i}^{(t_{i})}|\geq l{j-1\choose
t_{i}-1}>l{|X|-1\choose t_{i}-1}$. Since
$\mathcal{I}_{i}^{(t_{i})}\subset{X\choose t_{i}}$, we have
$|\mathcal{I}_{i}^{(t_{i})}|\leq{|X|\choose t_{i}}$. Together, these two
inequalities imply $t_{i}\leq|X|/l$ and thus $\sum_{i=1}^{l}t_{i}\leq|X|$.
Applying Lemma 22, we get a contradiction with the fact that
$\mathcal{I}_{1}^{(t_{1})},\ldots,\mathcal{I}_{l}^{(t_{l})}$ are cross-
dependent. ∎

Let us put $\beta_{t}:={n-j\choose k-t}$ for every $t=2,\ldots,k$ and apply
the claim. Then there is $i\in[l]$, such that

$\sum_{t=2}^{k}{n-j\choose
k-t}|\mathcal{I}^{(t)}_{i}|\leq\sum_{t=2}^{k}{n-j\choose k-t}l{j-1\choose
t-1}.$ (16)

The left hand side of (16) is exactly $|\mathcal{I}_{i}|$! Finally, we are
left to estimate the right hand side of (16). Denote the $t$-th term of the
summation by $f(t)$. Recall that $n\geq 4jk$, and, due to $k\geq 2$ and $j\geq
2$, we have $n-j-k\geq 3jk$. We have

$\frac{f(t)}{f(t+1)}=\frac{n-j-k+t+1}{k-t}\cdot\frac{t}{j-t}>3t\geq 3.$

Thus, we get that (16) and the inequality above implies
$|\mathcal{I}_{i}|\leq\sum_{t=2}^{k}f(t)<f(1)\cdot\sum_{t=1}^{\infty}(1/3)^{t}=f(1)\cdot\frac{1/3}{1-1/3}=\frac{1}{2}f(1)=\frac{l}{2}{n-j\choose
k-1}$. On the other hand, ${n-s+l\choose k}-{n-s+1\choose
k}-\frac{k^{3}}{n^{3}}{n\choose k}\geq(l-1){n-j\choose k-1}$. Since $l\geq 2$,
the last expression is an upper bound on $|\mathcal{I}_{i}|$, which concludes
the proof of (15). ∎

The second step is to show that the families ${\mathcal{F}}_{i}$ must satisfy
$\mathcal{J}_{i}\setminus{\mathcal{F}}_{i}=\emptyset$ for each $i\in[s]$. This
part of the argument is similar to the proofs from [5, 19].

Assume that, among $i\in[s]$, the density
$\alpha_{i}:={\mathcal{F}}_{i}(\emptyset,[s-1])/{n-s+1\choose k}$ is the
largest for $i=1$ and put
$\beta_{i}^{l}:={\mathcal{F}}_{i}(\\{l\\},[s-1])/{n-s+1\choose k-1}$ for each
$i=2,\ldots,s$, $l\in[s-1]$. For a family $\mathcal{G}\subset{[m]\choose k}$
and $t\geq k$, let $\bar{\partial}^{t}\mathcal{G}$ be the collection of all
sets in ${[m]\choose t}$ that contain at least one set from $\mathcal{G}$. The
following analytic corollary of the Kruskal–Katona [20, 17] theorem was proved
by Bollobás and Thomason [4]:

$\Big{|}\bar{\partial}^{t}\mathcal{G}/{n\choose
t}\Big{|}^{n-k}\geq\Big{|}\mathcal{G}/{n\choose k}\Big{|}^{n-t}.$

From here, we conclude that
$\alpha^{\prime}_{1}:=|\bar{\partial}^{(n+k)/2}{\mathcal{F}}_{1}(\emptyset,[s-1])|\geq\alpha_{1}^{1/2}$.

At the same time, for any bijection $\pi:[s-1]\to[2,s]$, the families
${\mathcal{F}}_{\pi(i)}(\\{i\\},[s-1]),$ $i\in[s-1]$, and
$\bar{\partial}^{(n+k)/2}{\mathcal{F}}_{1}(\emptyset,[s-1])$ are cross-
dependent. Since $(n+k)/2+(s-1)k<n$, we may take a random ordered matching
consisting of $s-1$ sets $M_{1},\ldots,M_{s-1}$ of size $k$ and one set
$M_{s}$ of size $(n+k)/2$. In any such matching, there are at most $s-1$
indices $i\in[s]$ such that: $M_{i}\in{\mathcal{F}}_{\pi(i)}(\\{i\\},[s-1])$
for $i\in[s-1]$, or
$M_{i}\in\bar{\partial}^{(n+k)/2}{\mathcal{F}}_{1}(\emptyset,[s-1])$ for
$i=s$. Computing the expectation of the number of such indices, we get

$\alpha^{\prime}_{1}+\sum_{i=1}^{s-1}\beta_{\pi(i)}^{i}\leq s-1.$

Therefore, there exists $i\in[2,s]$, such that
$\sum_{l=1}^{s-1}\beta_{i}^{l}\leq s-1-\alpha^{\prime}_{1}$. This implies that

$|{\mathcal{F}}_{i}|\leq{n\choose k}-{n-s+1\choose
k}+\frac{k^{3}}{n^{3}}{n\choose k}-\frac{k^{3/2}}{n^{3/2}}{n-s+1\choose
k-1}<{n\choose k}-{n-s+1\choose k},$

a contradiction. Here the last inequality is again due to our choice of $n$,
that is, $n>12ks\log(e^{2}s)$. ∎

Thanks to the Kruskal–Katona theorem, we can derive the following non-uniform
generalization of Theorem 21.

######  Theorem 25.

Fix integers $k_{1},\ldots,k_{s}$ and assume that $n\geq 12ks\log(e^{2}s)$ for
$k:=\max_{i\in[s]}k_{i}$. Assume that ${\mathcal{F}}_{1}\subset{[n]\choose
k_{1}},\ldots,{\mathcal{F}}_{s}\subset{[n]\choose k_{s}}$ are cross-dependent.
Then there exists $i\in[s]$ such that

$|{\mathcal{F}}_{i}|\leq{n\choose k_{i}}-{n-s+1\choose k_{i}}.$

###### Proof.

Suppose that $|{\mathcal{F}}_{i}|>{n\choose k_{i}}-{n-s+1\choose k_{i}}$ for
every $i$. Then the families
$\bar{\partial}^{k}{\mathcal{F}}_{1},\ldots,\bar{\partial}^{k}{\mathcal{F}}_{s}$
are cross-dependent as well. Moreover, we claim that

$|\bar{\partial}^{k}{\mathcal{F}}_{i}|>{n\choose k}-{n-s+1\choose k}$

for every $i\in[s]$. This would contradict Theorem 21, so we only need to
verify the displayed inequality.

Set ${\mathcal{G}}_{i}:=\\{[n]\setminus F:F\in{\mathcal{F}}_{i}\\}$.

$|{\mathcal{G}}_{i}|>{n-1\choose k_{i}-1}+\ldots+{n-s+1\choose
k_{i}-1}={n-1\choose n-k_{i}}+\ldots+{n-s+1\choose n-k_{i}-s+1}.$

By the Kruskal–Katona theorem [20, 17], its shadow on level $n-k$ will be

$|\partial^{n-k}{\mathcal{G}}_{i}|>{n-1\choose n-k}+\ldots+{n-s+1\choose
n-k-s+1}={n\choose k}-{n-s+1\choose k}.$

But $|\partial^{n-k}{\mathcal{G}}_{i}|=|\bar{\partial}^{k}{\mathcal{F}}_{i}|.$
∎

##  6 Concluding Remarks

We believe that Theorem 21 is only one example of the many possible scenarios
where the shifted juntas enable one to get better, concrete bounds which seem
to be elusive for the general juntas obtained by means of discrete Fourier
transform methods.

We note that the validity of Theorem 21 for $n>Csk$ with some large $C$ was
announced by Keevash, Lifshitz, Long, and Minzer as a consequence of general
sharp threshold-type results. In the proof, they use the aforementioned
variant of Corollary 13.

## Acknowledgments

We thank Noam Lifshitz and the anonymous referee for many helpful remarks.

The authors’ research was supported by the grant of the Russian Government N
075-15-2019-1926. The research of the second author was in part supported by
the Advanced Postdoc.Mobility grant no. P300P2_177839 of the Swiss National
Science Foundation.

## References

  * [1] R. Aharoni and D. Howard  Size conditions for the existence of rainbow matchings.  unpublished manuscript
  * [2] R. Ahlswede and L. Khachatrian.  The complete intersection theorem for systems of finite sets  Eur. J. Comb. 18(2): 125–136, 1997.
  * [3] N. Alon and J. Spencer.  The probabilistic method.  Third Edition, John Wiley & Sons, 2004.
  * [4] B. Bollobás and A.G. Thomason.  Threshold functions.  Combinatorica 7:35–38, 1987.
  * [5] I. Dinur and E. Friedgut.  Intersecting families are essentially contained in juntas.  Combinatorics, Probability and Computing 18:107–122, 2009.
  * [6] P. Erdős.  A problem on independent r-tuples.  Ann. Univ. Sci. Budapest 8:93–95, 1965.
  * [7] P. Frankl.  The Erdős-Ko-Rado theorem is true for n=ckt.  Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18:365–375, North-Holland.
  * [8] P. Frankl.  Families of finite sets satisfying an intersection conditon.  Bull. Austral. Math. Soc., 15:73–79, 1976.
  * [9] P. Frankl.  The shifting technique in extremal set theory.  Surveys in combinatorics, 123:81–110, 1987.
  * [10] P. Frankl.  Improved bounds for Erdős’ Matching Conjecture.  J. Comb. Theory Ser. A 120:1068–1072, 2013.
  * [11] P. Frankl and A. Kupavskii.  The Erdős Matching Conjecture and Concentration Inequalities.  2018, arXiv:1806.08855
  * [12] P. Frankl and A. Kupavskii.  Beyond the Erdős Matching Conjecture.  2019, arXiv:1901.09278
  * [13] E. Friedgut.  Boolean Functions With Low Average Sensitivity Depend On Few Coordinates.  Combinatorica 18:27–35, 1998.
  * [14] H. Huang, P. Loh, and B. Sudakov.  The size of a hypergraph and its matching number.  Combin. Probab. Comput. 21:442–450, 2012.
  * [15] H. Huang, T. Li, and G. Wang.  Rainbow matchings in properly-colored hypergraphs.  Electr. J. Comb. 26(1) P1.4, 2019.
  * [16] S. Janson, T. Łuczak, and A. Ruciński.  Random graphs.  Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
  * [17] G.O.H. Katona.  A theorem of finite sets.  Theory of Graphs, Proc. Coll. Tihany 1966, Akad, Kiado, Budapest, 1968; Classic Papers in Combinatorics 381–401, 1987.
  * [18] P. Keevash, N. Lifshitz, E. Long, D. Minzer.  Hypercontractivity for global functions and sharp thresholds.  2019, arXiv:1906.05568
  * [19] N. Keller and N. Lifshitz.  The Junta Method for Hypergraphs and Chvátal’s Simplex Conjecture.  2017, arXiv:1707.02643
  * [20] J.B. Kruskal.  The Number of Simplices in a Complex.  Mathematical optimization techniques 251:251–278, 1963.
  * [21] H. Lu and X. Yu.  On Rainbow Matchings for Hypergraphs.  SIAM J. Discrete Math. 32:382–393, 2018.

[peter] Peter Frankl
Rényi Institute
Budapest, Hungary
peter.franklgmailcom
https://users.renyi.hu/ pfrankl/ [andrey] Andrey Kupavskii
IAS, Princeton,
CNRS, France,
MIPT, Moscow kupavskiiyaru
http://kupavskii.com