# Self-testing in parallel with CHSH

Matthew McKague  Department of Electrical Engineering and Computer Science,
Queensland University of Technology<EMAIL_ADDRESS>
###### Abstract

Self-testing allows classical referees to verify the quantum behaviour of some
untrusted devices. Recently we developed a framework for building large self-
tests by repeating a smaller self-test many times in parallel. However, the
framework did not apply to the CHSH test, which tests a maximally entangled
pair of qubits. CHSH is the most well known and widely used test of this type.
Here we extend the parallel self-testing framework to build parallel CHSH
self-tests for any number of pairs of maximally entangled qubits. Our
construction achieves an error bound which is polynomial in the number of
tested qubit pairs.

##  1 Introduction

The most basic self-testing problem is this: given two non-communicating
quantum devices, verify through classical interaction alone that they share a
maximally entangled pair of qubits. This problem can also be phrased in the
language of non-local games. In a non-local game two non-communicating
players111Non-local games for more than two players are also possible., Alice
and Bob, receive questions from a referee and attempt to win the game by
providing answers which, together with the questions, satisfy some predicate.
For non-local games, self-testing says that for Alice and Bob to approach the
optimal quantum probability of winning, their strategy must approach some
particular ideal quantum strategy.

While it is interesting that it is possible to self-test a single pair of
maximally entangled qubits, many more applications are possible if many pairs
can be tested. This motivates the idea of repeated self-tests, whether in
series (as in [RUV13]) or parallel (as in [McK16]), to test many pairs of
maximally entangled qubits. From the players’ perspective, strategies for
serial repetition can be converted to parallel repetition but not the other
way around. Hence parallel self-testing results are more general and their
robustness bounds also apply to serial repetition.

The CHSH game [CHSH69] is arguably the most well-known non-local game and has
seen wide application. It is distinguished by its simplicity, with only
single-bit questions and answers for both Alice and Bob. Because of this
simplicity, the CHSH game is widely used, both in theory and experiment. Hence
it is a natural candidate for use with parallel repetition.

An important distinction to make is between self-tests where the number of
players is kept at two (as in [RUV13]), with self-tests where two new players
are added for each copy of the self-test, (as in [MMMO06]). Every additional
player introduces either additional assumptions, or restrictions on potential
experiments. Hence the two player scenario is more general and preferred. We
will be considering the two-player scenario here.

###  1.1 Previous work

The history of self-testing using CHSH goes back to Popescu and Rohrlich
[PR92] who characterised the optimal quantum strategies for CHSH. Although the
terminology and applications of self-testing were later introduced by Mayers
and Yao [MY04]. Robust proofs of self-testing with CHSH appeared with Bardyn
et al. [BLM+09] and McKague et al. [MYS12].

As a non-local game, parallel repetition of CHSH was considered by Cleve et
al. [CSUU08], although they did not consider self-testing. Reichardt et al.
[RUV13] looked at serial repetition of CHSH for self-testing. The first
parallel self-testing result using CHSH is due to Wu et al. [WBMS16] who used
semi-definite programming and numerical methods to give robust error bounds
for self-testing with two simultaneous games of CHSH. They also give an
analytic proof of self-testing for the ideal case, again for two copies of
CHSH.

Self-testing using parallel repetition with more than two repetitions first
appeared in [McK16], which used the Mayers-Yao test [MY04] and another CHSH-
like self-test. However, the robustness bound of the latter test scaled
exponentially with the amount of repetitions. Self-testing using parallel
repetition of CHSH was shown by Coladangelo222 We first became aware of
Coladangelo’s work after an early version of this manuscript was posted to the
arXiv.  in [Col16].

###  1.2 Contributions

Our main contribution here is to give a self-testing construction for parallel
repetition of the CHSH game. Informally, we prove that if Alice and Bob have a
strategy for playing $\frac{n}{2}$ rounds333i.e. for self-testing a state on
$n$ qubits of CHSH in parallel that achieves an average CHSH value of at least
$2\sqrt{2}-\epsilon$ (i.e. they are $\epsilon$ close to the quantum bound)
then their state is within $O(n^{\frac{9}{8}}\epsilon^{\frac{1}{8}})$ of
$\frac{n}{2}$ pairs of maximally entangled qubits.

As a step in our construction we also show that it is possible to self-test
many maximally entangled pairs of qubits using a modified parallel repetition
of CHSH with only a logarithmic number of questions (measurement settings).
This is analogous to a similar result built on the Mayers-Yao test in [McK16].

In order to achieve our construction we slightly generalise the parallel self-
testing framework given in [McK16]. Our construction is in some ways a
generalisation of the analytic proof of self-testing for two copies of CHSH
given in [WBMS16].

##  2 A framework for self-testing qubits

Before addressing our particular self-test, we will recall and slightly modify
the self-testing framework introduced in [McK16].

###  2.1 Technical preliminaries

We define $1_{k}$ to be the $n$-bit string which is 1 in the $k$-th position
and 0 everywhere else. For $x$ an $n$-bit string, let $|x|$ be the number of
1’s in $x$ (the Hamming weight). Further, when $n$ is even, define $x_{a}$ to
be the first $\frac{n}{2}$ bits of $x$. The string $x_{b}$ is the last
$\frac{n}{2}$ bits of $x$. Later, we will divide $x$ between Alice and Bob so
$x_{a}$ represents $x$ on Alice’s side, and $x_{b}$ is for Bob’s side. For
strings $x$ and $y$ of the same length, $x\cdot y=\sum_{j}x_{j}y_{j}$ is the
inner product of $x$ and $y$. Finally, $xy$ is the concatenation of $x$ and
$y$.

If we have operators $M_{1}\dots M_{n}$ then for a bit string
$t\in{\\{0,1\\}}^{n}$ we define

$M^{t}:=\prod_{k=1}^{n}M_{k}^{t_{k}}.$ (1)

The order of the product is important since we do not know whether the
operators all commute. Hence we will make the convention that the index
increases from left to right.

###  2.2 Sufficient conditions for self-testing

In [McK16] we developed a framework for self-testing states of many qubits,
and in particular derived sufficient conditions for self-testing many pairs of
maximally entangled qubits. Unfortunately, the framework in [McK16] is not
general enough for our purposes since the sufficient conditions require the
existence of a large set of commuting operators, but we will be unable to
provide them here. In this section we will modify our previous work to provide
a set of sufficient conditions which requires a smaller set of commuting
operators.

To begin with, we recall Lemma 4 from [McK16], which gives a very general set
of sufficient conditions for self-testing a many qubit state. Here we present
a version which is restricted to many pairs of maximally entangled qubits,
rather than the more general version in [McK16] which also applies to graph
states.

######  Lemma 1 (McKague [McK16], Lemma 4).

Let $\left|\,\psi\right\rangle$ be the $n$-qubit state

$\left|\,\psi\right\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{u_{a},u_{b}\in{\\{0,1\\}}^{n/2}}{(-1)}^{u_{a}\cdot
u_{b}}\left|\,u\right\rangle.$ (2)

Further suppose that $\left|\,\psi^{\prime}\right\rangle$ is a normalised
state in a Hilbert space $\mathcal{H}_{\mathcal{A}}$, and
${\\{X^{\prime}_{j}\\}}_{j=1}^{n}$, ${\\{Z^{\prime}_{j}\\}}_{j=1}^{n}$ are
unitary, Hermitian operators on $\mathcal{H}_{\mathcal{A}}$ such that for any
$s,t\in{\\{0,1\\}}^{n}$

$\left|\left|Z^{\prime t}X^{\prime
s}\left|\,\psi^{\prime}\right\rangle-{(-1)}^{s\cdot t}X^{\prime s}Z^{\prime
t}\left|\,\psi^{\prime}\right\rangle\right|\right|\leq\epsilon$ (3)

and

$\left|\left|Z^{\prime
s_{b}s_{a}}\left|\,\psi^{\prime}\right\rangle-{(-1)}^{s_{a}\cdot
s_{b}}X^{\prime
s}\left|\,\psi^{\prime}\right\rangle\right|\right|\leq\epsilon.$ (4)

Then there exists an isometry $\Phi$ and a state $\left|\,junk\right\rangle$
such that for any $p,q\in{(0,1)}^{n}$

$\left|\left|\Phi(X^{\prime q}Z^{\prime
p}\left|\,\psi^{\prime}\right\rangle)-\left|\,junk\right\rangle
X^{q}Z^{p}\left|\,\psi\right\rangle\right|\right|\leq O(\sqrt{\epsilon}).$ (5)

The ideal state $\left|\,\psi\right\rangle$ is the graph state corresponding
to $\frac{n}{2}$ isolated edges and is hence $\frac{n}{2}$ pairs of maximally
entangled states.

The conditions for this lemma involve products of many operators. In general
we will not be able to directly deduce properties of such complex products.
Hence we will derive a less general set of conditions which are easier to meet
from the limited information provided by measurement outcomes. In [McK16] this
step is provided by Lemma 5. However, the conditions used are too restrictive
to be applicable in our case. Hence we will prove a less restrictive version
of this lemma.

######  Lemma 2.

Suppose that $n$ is even and

  1. 1.

$\left|\,\psi^{\prime}\right\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
is a state

  2. 2.

${\\{X^{\prime}_{k}\\}}_{k=1}^{n/2}$ are pair-wise commuting operators on
$\mathcal{H}_{A}$

  3. 3.

${\\{Z^{\prime}_{k}\\}}_{x=1}^{\frac{n}{2}}$ are pair-wise commuting operators
on $\mathcal{H}_{A}$

  4. 4.

${\\{X^{\prime}_{k}\\}}_{k=\frac{n}{2}+1}^{n}$ are operators on
$\mathcal{H}_{B}$

  5. 5.

${\\{Z^{\prime}_{k}\\}}_{k=\frac{n}{2}+1}^{n}$ are operators on
$\mathcal{H}_{B}$

such that for all $k\neq\ell$

$\displaystyle\left|\left|X^{\prime}_{k}\right|\right|_{\infty},\left|\left|Z^{\prime}_{k}\right|\right|_{\infty}$
$\displaystyle\leq$ $\displaystyle 1$ (6)
$\displaystyle\left|\left|X^{\prime}_{k}Z^{\prime}_{\ell}\left|\,\psi^{\prime}\right\rangle-Z^{\prime}_{\ell}X^{\prime}_{k}\left|\,\psi^{\prime}\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle\epsilon_{1}$ (7)
$\displaystyle\left|\left|X^{\prime}_{k}\left|\,\psi^{\prime}\right\rangle-Z^{\prime}_{k+\frac{n}{2}}\left|\,\psi^{\prime}\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle\epsilon_{2}$ (8)
$\displaystyle\left|\left|Z^{\prime}_{k}X^{\prime}_{k}\left|\,\psi^{\prime}\right\rangle+X^{\prime}_{k}Z^{\prime}_{k}\left|\,\psi^{\prime}\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle\epsilon_{3}$ (9)

where $k+\frac{n}{2}$ is taken modulo $n$. Then

  1. 1.

for any $s,t\in{\\{0,1\\}}^{n}$

$\left|\left|Z^{\prime t}X^{\prime
s}\left|\,\psi^{\prime}\right\rangle-{(-1)}^{s\cdot t}X^{\prime s}Z^{\prime
t}\left|\,\psi^{\prime}\right\rangle\right|\right|\leq O(n^{2}\epsilon)$ (10)

  2. 2.

for any $s\in{\\{0,1\\}}^{n}$

$\left|\left|Z^{\prime
s_{b}s_{a}}\left|\,\psi^{\prime}\right\rangle-{(-1)}^{s_{a}\cdot
s_{b}}X^{\prime s}\left|\,\psi^{\prime}\right\rangle\right|\right|\leq
O(n^{2}\epsilon)$ (11)

where $\epsilon=\max\\{\epsilon_{1},\epsilon_{2},\epsilon_{3}\\}$.

The main difference between Lemma 5 in [McK16] and our version here is that we
have dropped several requirements on the operators. Explicit error bounds are
the same as in [McK16].

###### Proof.

First we address conclusion 1. We will not give the whole proof, but instead
refer the reader to the proof of Lemma 5 in [McK16] and note the modifications
we need to make. We first note that the proof never uses the fact that any
operators are Hermitian or unitary other than to bound the operator. Hence we
can drop these requirements in favour of the less restrictive requirements
$\left|\left|X^{\prime}_{k}\right|\right|_{\infty}\leq 1$ and
$\left|\left|Z^{\prime}_{k}\right|\right|_{\infty}\leq 1$. The proof does
implicitly use the fact that many operators commute, but it is possible to
remove these commutations through a careful choice of ordering of the steps.
In particular, for equations (50) to (53) in [McK16] the proof starts from
small indices and works to larger indices. Using this ordering requires that
the leftmost operators commute to the right, but by starting at highest
indices and working to lower indices the operators are already in the correct
order and no commutation is required.

Here we also need to point out that if we had chosen a different initial
ordering for the operators, for example decreasing indices from left to right,
then the proof would still apply, provided that the same ordering is used
throughout.

Now we turn our attention to conclusion 2. Again we will follow the same proof
as in [McK16]. We can remove implicit commutations by choosing a different
ordering. However, this would result in the $Z^{\prime}$ operators coming out
in the reverse order in the final bound. To fix this we need to use the fact
that all $X^{\prime}$ operators on $A$’s side commute, and also all
$Z^{\prime}$ operators on $A$’s side commute. First, we reverse the ordering
of the $X^{\prime}$s on $A$’s side. Then when these are converted to
$Z^{\prime}$’s on $B$’s side, they are reversed again and come out in the
correct order. Meanwhile the $X^{\prime}$’s on $B$’s side are left alone. They
come out in reverse order on $A$’s side, where we commute them around to the
correct ordering.

∎

The conclusions of Lemma 2 are nearly the conditions of Lemma 1, so it is
straightforward to join the two together. This will give us our sufficient
conditions for self-testing many maximally entangled qubits.

######  Corollary 1.

Under the conditions of Lemma 2, supposing that
${\\{X_{k},Z_{k}\\}}_{k=1}^{n}$ are also unitary and Hermitian, there exists a
local isometry $\Phi=\Phi_{A}\otimes\Phi_{B}$ and a state
$\left|\,junk\right\rangle$ such that for every $p,q\in{\\{0,1\\}}^{n}$

$\left|\left|\Phi(X^{\prime q}Z^{\prime
p}\left|\,\psi^{\prime}\right\rangle)-\left|\,junk\right\rangle
X^{q}Z^{p}\left|\,\psi\right\rangle\right|\right|\leq O(n\sqrt{\epsilon})$
(12)

where $\left|\,\psi\right\rangle$ is as in Lemma 1.

The proof is basically to patch together Lemma 1 and 2 and work out the
bounds. One aspect which requires a bit more attention is the fact that $\Phi$
is local. This is a consequence of the construction of $\Phi$ in the proof of
Lemma 1 and is discussed in [McK16].

##  3 Parallel CHSH is a self-test

Now that we have established a framework for self-testing many pairs of
maximally entangled qubits, we are ready to develop our self-test based on
parallel repetition of CHSH.

###  3.1 Definition of the non-local game

The non-local game that we will be using for self-testing is a straightforward
parallel repetition of the CHSH game:

  1. 1.

The referee selects question $q\in{\\{0,1\\}}^{n}$ uniformly at random and
sends $q_{a}$ to Alice and $q_{b}$ to Bob

  2. 2.

Alice and Bob respond with bit strings $x,y\in{\\{0,1\\}}^{\frac{n}{2}}$.

  3. 3.

The referee chooses $k\in\\{1\dots\frac{n}{2}\\}$ uniformly at random.

  4. 4.

Alice and Bob win if $q_{k}q_{k+\frac{n}{2}}=x_{k}\oplus y_{k}$

There are many possible rules for determining when Alice and Bob win. The
particular rule we use is quite weak in a sense. We throw away almost all of
the information that Alice and Bob provide, and use only one bit from each of
them. However, as we shall see, it is still powerful enough for self-testing
the entire state. The most important feature is that the expected value of
this game measures the average CHSH value over all subtests, which could be
measured in other ways.

Customarily the value of a CHSH strategy is calculated by assigning $1$ for a
win and $-1$ for a loss and summing over the expectations of the four possible
questions that can be asked. The value falls between $-4$ and $4$, with
quantum strategies between $-2\sqrt{2}$ and $2\sqrt{2}$ by the Cirel’son
inequality [Cir80]. We will take the convention of assigning $4$ to a win and
$-4$ to a loss, and then taking the expected value over all possible questions
and subtests (i.e. for various $k=1\dots\frac{n}{2}$). This corresponds to
averaging the customary CHSH value over all subtests, and is bounded by
$2\sqrt{2}$ for quantum strategies.

###  3.2 Modelling the players’ behaviour

In order to use Lemma 1 we will need to define some operators $X^{\prime}_{j}$
and $Z^{\prime}_{j}$. We will do so by way of Alice and Bob’s measurement
strategies. But first we need a model. Alice’s behaviour can be modelled as a
collection of projective measurements:444More generally, we could consider
POVMs. However, since the dimension of Alice and Bob’s systems are
unconstrained, we can instead represent any POVM as projective measurements
over a larger Hilbert space.

$\mathcal{M}_{q_{a}}={\\{\Pi^{q_{a}}_{a}\\}}_{a}$ (13)

where $q$ is the question, $a\in{\\{0,1\\}}^{\frac{n}{2}}$ is a string of
answers and
$\Pi^{q_{a}}_{a}\Pi^{q_{a}}_{a^{\prime}}=\delta_{a,a^{\prime}}\Pi^{q_{a}}_{a}$.
We can define projectors for individual symbols in the answer by

$\Gamma^{q_{a}}_{k,x}=\sum_{a:a_{k}=x}\Pi^{q_{a}}_{a}$ (14)

where $k\in\\{1\dots\frac{n}{2}\\}$, $a_{k}$ is the $k$-th symbol of $a$, and
$x\in\\{0,1\\}$. Note that for all $j,k,x,x^{\prime}$ the operators
$\Gamma^{q_{a}}_{j,x}$ and $\Gamma^{q_{a}}_{k,x^{\prime}}$ commute since
$\Pi^{q}_{a}$ and $\Pi^{q}_{a^{\prime}}$ commute for all $a,a^{\prime}$. We
can next define observables for each answer symbol by

$M^{\prime q_{a}}_{k}=\Gamma^{q_{a}}_{k,0}-\Gamma^{q_{a}}_{k,1}.$ (15)

Whenever $q_{a}=r_{a}$, $M^{\prime q_{a}}_{k}$ and $M^{\prime r_{a}}_{\ell}$
will commute by construction. Now measuring $\mathcal{M}_{q}$ is equivalent to
measuring $M^{\prime q}_{k}$ for each $k$ and returning the resulting
eigenvalues as a string (translating 1 to 0 and -1 to 1). Each $M^{\prime
q}_{k}$ is Hermitian and unitary.

We can model Bob’s behaviour in a similar way, defining $N^{\prime q_{b}}_{k}$
for $k\in\\{\frac{n}{2}+1\dots n\\}$ analogously to $M^{\prime q_{a}}_{k}$.
Then every $N^{\prime q_{b}}_{k}$ will commute with every $M^{\prime
q_{a}}_{\ell}$ since these operators are on different systems.

Let us set

$f(q_{a},q_{b},k):=\left\langle{}\psi^{\prime}\,\right|\left({(-1)}^{{(q_{a})}_{k}{(q_{b})}_{k}}M^{\prime
q_{a}}_{k}N^{\prime
q_{b}}_{k+\frac{n}{2}}+{(-1)}^{{(\overline{q}_{a})}_{k}{(q_{b})}_{k}}M^{\prime\overline{q}_{a}}_{k}N^{\prime
q_{b}}_{k+\frac{n}{2}}\right)\left|\,\psi^{\prime}\right\rangle+\\\
\left\langle{}\psi^{\prime}\,\right|\left({(-1)}^{{(q_{a})}_{k}{(\overline{q}_{b})}_{k}}M^{\prime
q_{a}}_{k}N^{\prime\overline{q}_{b}}_{k+\frac{n}{2}}+{(-1)}^{{(\overline{q}_{a})}_{k}{(\overline{q}_{b})}_{k}}M^{\prime\overline{q}_{a}}_{k}N^{\prime\overline{q}_{b}}_{k+\frac{n}{2}}\right)\left|\,\psi^{\prime}\right\rangle$
(16)

where $\overline{q}_{a}$ is $q_{a}$ with 0 and 1 interchanged, and analogously
for $q_{b}$.

We can interpret $f$ as the CHSH value that Alice and Bob would achieve for
subtest $k$ if they use the operators corresponding to questions $q_{a}$,
$q_{b}$, $\overline{q}_{a}$ and $\overline{q}_{b}$. The value of the non-local
game can be expressed as

$\frac{1}{n2^{n-1}}\sum_{q_{b}}\sum_{q_{a}}\sum_{k}f(q_{a},q_{b},k).$ (17)

This is the value of Alice and Bob’s strategy and is the average CHSH value
over all subtests $1\dots\frac{n}{2}$. It falls between $-2\sqrt{2}$ and
$2\sqrt{2}$ for quantum strategies by the Cirel’son bound [Cir80].

###  3.3 Self-testing from a few questions

In this section we develop a proof of self-testing in a special case. Our non-
local game has a very large number of questions and it is difficult to make
use of the information contained in the corresponding answers. In particular,
each question is asked with an exponentially small probability, so we will
know almost nothing about what happens when any particular question is asked.
For now we will ignore this problem and assume that for some particular
questions we know what the distribution of answers is. This will allow us to
draw conclusions about the players’ behaviour. In the next section we will
return to the full non-local game.

In the previous section we modelled Alice and Bob’s measurement strategies. We
next need to define $X^{\prime}_{j}$ and $Z^{\prime}_{j}$ so that we can use
Corollary 1. To do this we will make use of a result from [MYS12]:

######  Lemma 3 (McKague et al. [MYS12], Theorem 2).

Let $A_{0},A_{1}$ be Hermitian and unitary operators on $\mathcal{H}_{A}$,
$B_{0},B_{1}$ be Hermitian and unitary operators on $\mathcal{H}_{B}$, and
$\left|\,\psi\right\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ be a state
such that

$\left\langle{}\psi\,\right|\left(A_{0}B_{0}+A_{1}B_{0}+A_{0}B_{1}-A_{1}A_{1}\right)\left|\,\psi\right\rangle\geq
2\sqrt{2}-\delta$ (18)

for $0\leq\delta\leq 1$. Then setting

$\displaystyle X^{\prime}_{A}$ $\displaystyle=$ $\displaystyle A_{0}$ (19)
$\displaystyle Z^{\prime}_{A}$ $\displaystyle=$ $\displaystyle A_{1}$ (20)
$\displaystyle X^{\prime}_{B}$ $\displaystyle=$
$\displaystyle\frac{B_{0}+B_{1}}{|B_{0}+B_{1}|}$ (21) $\displaystyle
Z^{\prime}_{B}$ $\displaystyle=$
$\displaystyle\frac{B_{0}-B_{1}}{|B_{0}-B_{1}|}$ (22)

we have

$\displaystyle\left|\left|X^{\prime}_{A}Z^{\prime}_{A}\left|\,\psi\right\rangle+Z^{\prime}_{A}X^{\prime}_{A}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{2}}$ (23)
$\displaystyle\left|\left|X^{\prime}_{B}Z^{\prime}_{B}\left|\,\psi\right\rangle+Z^{\prime}_{B}X^{\prime}_{B}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{2}}$ (24)
$\displaystyle\left|\left|X^{\prime}_{A}\left|\,\psi\right\rangle-Z^{\prime}_{B}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{4}}$ (25)
$\displaystyle\left|\left|X^{\prime}_{B}\left|\,\psi\right\rangle-Z^{\prime}_{A}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{4}}$ (26)

where

$|M|:=\sqrt{M^{2}}$ (27)

for some operator $M$. Further, $X^{\prime}_{A}$, $X^{\prime}_{B}$,
$Z^{\prime}_{A}$ and $Z^{\prime}_{B}$ are all Hermitian and unitary.

Note that it is possible that zero is an eigenvalue of $|M|$. For theses cases
we must change $M$ on the associated subspace to remove zero eigenvalues and
avoid divide-by-zero problems. We can make the new eigenvalue as close to zero
as we like, which corresponds to a very small change in Bob’s measurements. By
making this change small enough, it will be negligible compared to the other
errors in the system.

In the next lemma we show how to link the above result with Corollary 1 to
obtain a self-testing result. Here we assume that we have very good
information about a small number of possible questions. This could be
accomplished, for example, by having the referee ask only a subset of possible
questions.

######  Lemma 4.

Suppose that:

  1. 1.

For each $k\in\\{1\dots\frac{n}{2}\\}$

$f(0\dots 0,0\dots 0,k)\geq 2\sqrt{2}-\delta$ (28)

  2. 2.

For every $u,v\in\\{1\dots\frac{n}{2}\\}$ with $u\neq v$ there exists a
question $q_{a}$ with ${(q_{a})}_{u}=0$ and ${(q_{a})}_{v}=1$ such that

$f(q_{a},0\dots 0,j)\geq 2\sqrt{2}-\delta$ (29)

for $j=u,v$.

Then there exist operators $X^{\prime}_{k}$ and $Z^{\prime}_{k}$ for each
$k\in\\{1\dots\frac{n}{2}\\}$ such that the conditions of Corollary 1 are
satisfied with $\epsilon_{1}=32{(\delta\sqrt{2})}^{\frac{1}{4}}$,
$\epsilon_{2}=4{(\delta\sqrt{2})}^{\frac{1}{4}}$ and
$\epsilon_{3}=4{(\delta\sqrt{2})}^{\frac{1}{2}}$.

###### Proof.

For each $k$, the conditions of Lemma 3 are satisfied by setting

$\displaystyle A_{0}$ $\displaystyle=$ $\displaystyle M^{\prime 0\dots 0}_{k}$
(30) $\displaystyle A_{1}$ $\displaystyle=$ $\displaystyle M^{\prime 1\dots
1}_{k}$ (31) $\displaystyle B_{0}$ $\displaystyle=$ $\displaystyle N^{\prime
0\dots 0}_{k+n/2}$ (32) $\displaystyle B_{1}$ $\displaystyle=$ $\displaystyle
N^{\prime 1\dots 1}_{k+n/2}$ (33)

Hence on Alice’s side ($k=1\dots\frac{n}{2}$) we set

$\displaystyle X^{\prime}_{k}$ $\displaystyle:=$ $\displaystyle M^{\prime
0\dots 0}_{k}$ (34) $\displaystyle Z^{\prime}_{k}$ $\displaystyle:=$
$\displaystyle M^{\prime 1\dots 1}_{k}$ (35)

for $k=1\dots\frac{n}{2}$. Note that by construction all $Z^{\prime}_{k}$
pairwise commute on Alice’s side, as do all $X^{\prime}_{k}$. For Bob’s side
($k=\frac{n}{2}+1\dots n$) we define

$\displaystyle X^{\prime}_{k}$ $\displaystyle:=$ $\displaystyle\frac{N^{\prime
0\dots 0}_{k}+N^{\prime 1\dots 1}_{k}}{\left|N^{\prime 0\dots 0}_{k}+N^{\prime
1\dots 1}_{k}\right|}$ (36) $\displaystyle Z^{\prime}_{k}$ $\displaystyle:=$
$\displaystyle\frac{N^{\prime 0\dots 0}_{k}-N^{\prime 1\dots
1}_{k}}{\left|N^{\prime 0\dots 0}_{k}-N^{\prime 1\dots 1}_{k}\right|}.$ (37)

Here it is possible that two $X^{\prime}_{j}$’s on Bob’s side do not commute.
With these definitions we can set
$\epsilon_{2}=4{(\delta\sqrt{2})}^{\frac{1}{4}}$ and
$\epsilon_{3}=4{(\delta\sqrt{2})}^{\frac{1}{2}}$ for Corollary 1.

Now fix $k,\ell$ with $k\neq\ell$. We want to know that $Z^{\prime}_{\ell}$
approximately commutes with $X^{\prime}_{k}$ to fix $\epsilon_{1}$. If $k$ is
on Alice’s side and $\ell$ is on Bob’s side (or vice versa) then the operators
commute exactly. Hence the two cases to check are where $k$ and $\ell$ are
both at most $\frac{n}{2}$ or when they are both larger than $\frac{n}{2}$.

Supposing that $k$ and $\ell$ are both larger than $\frac{n}{2}$, we use
condition 2 with $u=\ell-\frac{n}{2}$ and $v=k-\frac{n}{2}$ to find $q_{a}$
and define

$\displaystyle X^{\prime\prime}_{\ell-\frac{n}{2}}$ $\displaystyle:=$
$\displaystyle M^{\prime q_{a}}_{\ell-\frac{n}{2}}$ (38) $\displaystyle
Z^{\prime\prime}_{k-\frac{n}{2}}$ $\displaystyle:=$ $\displaystyle M^{\prime
q_{a}}_{k-\frac{n}{2}}.$ (39)

Applying Lemma 3 twice gives

$\displaystyle\left|\left|X^{\prime\prime}_{\ell-\frac{n}{2}}\left|\,\psi\right\rangle-Z^{\prime}_{\ell}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{4}}$ (40)
$\displaystyle\left|\left|Z^{\prime\prime}_{k-\frac{n}{2}}\left|\,\psi\right\rangle-X^{\prime}_{k}\left|\,\psi\right\rangle\right|\right|$
$\displaystyle\leq$ $\displaystyle 4{(\delta\sqrt{2})}^{\frac{1}{4}}$ (41)

Here Bob’s operators have not changed from their previous definition.
Moreover, since $X^{\prime\prime}_{\ell-\frac{n}{2}}$ and
$Z^{\prime\prime}_{k-\frac{n}{2}}$ are defined from the same question, they
commute with each other. Now it is a straightforward exercise to combine these
two estimates and show that for this case we can use
$\epsilon_{1}=16{(\delta\sqrt{2})}^{\frac{1}{4}}$. Roughly, we use the
estimates to move $X^{\prime}_{k}$ and $Z^{\prime}_{\ell}$ over to Alice’s
side as $X^{\prime\prime}_{\ell-\frac{n}{2}}$ and
$Z^{\prime\prime}_{k-\frac{n}{2}}$, where we can commute them, and then move
them back to Bob’s side.

For the other case, where $k$ and $\ell$ are less than $\frac{n}{2}$ so that
$X^{\prime}_{k}$ and $Z^{\prime}_{\ell}$ are on Alice’s side, we first move
$X^{\prime}_{k}$ and $Z^{\prime}_{\ell}$ over to Bob’s side, and then back to
Alice side, but as $X^{\prime\prime}_{k}$ and $Z^{\prime\prime}_{\ell}$, which
commute. Then they go back to $X^{\prime}_{k}$ and $Z^{\prime}_{\ell}$ via
Bob’s side. Here we end up with a worse estimate, and we finally set

$\epsilon_{1}=32{(\delta\sqrt{2})}^{\frac{1}{4}}.$ (42)

∎

Although this is not our main result, we now have a type of parallel CHSH
self-test. We simply need to estimate the values (for all $k$) of $f(0\dots
0,0\dots 0,k)$ and $f(q_{a},0\dots 0,k)$ for a suitable set of $q_{a}$. One
minimal set of such $q_{a}$ would be the strings indexed by $j$ where the
$k$th bit is 1 exactly when the $j$th bit of the binary representation of $k$
is 1. The total number of questions is then $O(\log n)$. Whenever $k\neq\ell$
their binary representations will differ in some position $j$. Then the
question with index $j$ will have bits $k$ and $\ell$ not equal. This is
analogous to the parallel Mayers-Yao test developed in [McK16].

The test is in a strict sense not parallel since the question for one subtest
is not independent of the questions for other subtests. Nevertheless, it does
provide a self-test and the small number of questions could be useful for some
applications.

###  3.4 Self-testing from parallel CHSH

In the previous section we showed self-testing, but only looked at a very
small number of possible questions. In the full non-local game we would not be
able to draw any strong conclusions about specific questions since they would
be asked with very small probability. In this section we take a different
approach. If the players’ value of the non-local game is very high then there
must be at least _some_ questions which are driving the value of the non-local
game up. These might not be the questions used in Lemma 4, but through various
symmetries of the non-local game we can expand the list of questions which
work for Lemma 4.

First let us discuss symmetries. Lemma 4 requires that questions $0\dots 0$
and $1\dots 1$ for Alice and Bob can be used to achieve a high CHSH value.
However, there is obvious symmetry in the non-local game and it is
straightforward to relabel the questions and answers so that many different
sets of questions can be used. In particular, the mapping

$\displaystyle q_{a}$ $\displaystyle\mapsto$ $\displaystyle q_{a}\oplus 1_{k}$
(43) $\displaystyle M^{\prime q_{a}}_{\ell}$ $\displaystyle\mapsto$
$\displaystyle M^{\prime q_{a}\oplus 1_{k}}_{\ell},\,\ell=1\dots\frac{n}{2}$
(44) $\displaystyle N^{\prime q_{b}}_{k+n/2}$ $\displaystyle\mapsto$
$\displaystyle{(-1)}^{{(q_{b})}_{k}}N^{\prime
q_{b}}_{k+n/2},\,k=1\dots\frac{n}{2}$ (45)

allows us to a flip bit $k$ in all questions on Alice’s side. An analogous map
allows us to flip any bit in all questions on Bob’s side. These mappings
preserve the value of the non-local game. Applying a suitable set of them
allows us to map any $q_{a}$ and $q_{b}$ to $0\dots 0$, necessarily taking
$\overline{q_{a}}$ and $\overline{q_{b}}$ to $1\dots 1$.

Now we attempt to find some questions which give $f(q_{a},q_{b},k)$ a large
value. The basic idea is that it is impossible for the value of every sub-test
to be below average. Suppose that the value of the non-local game is at least
$2\sqrt{2}-\epsilon$. We can view the value of the non-local game given in
(17) as an average over possible $q_{b}$ of some value depending on $q_{b}$.
At least one $q_{b}$ is at least average, so there exists some $q_{b}$ such
that

$\frac{1}{n2^{\frac{n}{2}-1}}\sum_{q_{a}}\sum_{k}f(q_{a},q_{b},k)\geq
2\sqrt{2}-\epsilon.$ (46)

Let us choose such a $q_{b}$ and then remap the non-local game so that $q_{b}$
maps to $0\dots 0$. We can now do the same trick with $q_{a}$ to find that
there is at least one $q_{a}$ such that

$\frac{2}{n}\sum_{k}f(q_{a},0\dots 0,k)\geq 2\sqrt{2}-\epsilon.$ (47)

Again we remap the non-local game so that this above average $q_{a}$ gets
mapped to $0\dots 0$.

In order to find a bound for each separate $k$, we observe that for each fixed
$k$ the summand is bounded above by $2\sqrt{2}$ using the Cirel’son
inequality. Supposing that all the error falls on one value of $k$, we find

$f(0\dots 0,0\dots 0,k)\geq 2\sqrt{2}-\frac{n}{2}\epsilon$ (48)

for all $k$. Hence we have satisfied the first condition of Lemma 4.

Turning our attention to the second condition of Lemma 4, we first use a
similar reasoning to above to find that for each $j$

$\frac{1}{2^{\frac{n}{2}}}\sum_{q_{a}}f(q_{a},0\dots 0,j)\geq
2\sqrt{2}-\frac{n}{2}\epsilon.$ (49)

Now let us fix $k,\ell$ and partition the possible $q_{a}$ into two sets. The
first set $S$ has either $({(q_{a})}_{k},{(q_{a})}_{\ell})=(0,0)$ or
$({(q_{a})}_{k},{(q_{a})}_{\ell})=(1,1)$. That is, questions in $S$ have the
$k$th and $\ell$th bits equal. The second set $T$ is the remaining $q_{a}$.
Note that sets are of equal size, and $q_{a}$ and $\overline{q}_{a}$ are in
the same set. Supposing that all the error falls on $T$ we find

$\frac{1}{2^{\frac{n}{2}}}\sum_{q_{a}\in T}f(q_{a},0\dots 0,j)\geq
2\sqrt{2}-n\epsilon.$ (50)

for $j=k,\ell$. Now at least one $q_{a}$ is at least average, so there is some
$q_{a}$ which differs in bits $k$ and $\ell$ which satisfies

$f(q_{a},0\dots 0,j)\geq 2\sqrt{2}-n\epsilon$ (51)

for $j=k,\ell$. From the definition of $f$, we see that the above must also
hold for $\overline{q}_{a}$. At least one of $q_{a}$ and $\overline{q}_{a}$
has the $k$th bit equal to 0 and the $\ell$th bit equal to 1. So, we have
satisfied the second condition of Lemma 4.

We have shown that if the value of the non-local game is high enough then the
conditions of Lemma 4 are satisfied with $\delta=O(n\epsilon)$, proving our
main result.

######  Theorem 1.

If the value of non-local game for $\frac{n}{2}$ copies of CHSH achieved by a
state
$\left|\,\psi^{\prime}\right\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
is at least $2\sqrt{2}-\epsilon$ then there exist

  * •

Hermitian and unitary $X^{\prime}_{k}$ and $Z^{\prime}_{k}$, defined on
$\mathcal{H}_{A}$ for $k\leq\frac{n}{2}$ and $\mathcal{H}_{B}$ for
$k>\frac{n}{2}$

  * •

a local isometry
$\Phi:\mathcal{H}_{A}\otimes\mathcal{H}_{B}\rightarrow\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{2}\otimes\mathcal{H}_{2}$

  * •

a state $\left|\,junk\right\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$

such that for any $p,q\in{\\{0,1\\}}^{n}$

$\left|\left|\Phi\left(X^{\prime q}Z^{\prime
p}\left|\,\psi^{\prime}\right\rangle\right)-\left|\,junk\right\rangle
X^{q}Z^{p}\left|\,\psi\right\rangle\right|\right|\leq
O(n^{\frac{9}{8}}\epsilon^{\frac{1}{8}}).$ (52)

where $\left|\,\psi\right\rangle$ is $\frac{n}{2}$ pairs of maximally
entangled qubits.

##  4 Discussion

We have shown that the CHSH game can be used for testing many pairs of
maximally entangled qubits, and that the error bound scales polynomially. This
opens the possibility of using CHSH in more applications. The two
constructions allow for either a strictly parallel CHSH test, where all
subtests are independent, or a construction which requires uses a logarithmic
number of questions.

Coladangelo [Col16] achieved a similar result to ours, allowing parallel self-
testing using CHSH. Their result is more general in that they considers the
tilted CHSH inequality as well, which allows for testing of non-maximally
entangled pairs of qubits. Robustness is $O(n^{3/2}\epsilon^{1/2})$ as
compared to our $O(n^{9/8}\epsilon^{1/8})$. While their scaling in $\epsilon$
is better, ours is better in the scaling in $n$.

The parallel CHSH self-test could be used in device independent quantum key
distribution to allow for parallel protocols. Device independent quantum key
distribution has been achieved for serial repetition [VV14] but not for
parallel repetition. The parallel self-test variant with a logarithmic number
of questions might be useful in device independent quantum random number
generators, where the smaller number of questions could reduce the about of
seed randomness required. See [MS16] for an example of a quantum random number
generator which utilises self-testing. Finally, parallel self-tests could
simplify protocols for interactive proofs, allowing for a smaller number of
rounds of communication as compared to serial repetition for constructions as
in [RUV13], or a reduced number of provers for constructions as in [McK13] or
[HPDF15].

## Acknowledgements

This work is partially funded by the Dodd-Walls Centre for Photonic and
Quantum Technologies.

## References

  * [BLM+09] Charles-Edwourd Bardyn, Timothy C. H. Liew, Serge Massar, Matthew McKague, and Valerio Scarani.  Device-independent state estimation based on Bell’s inequalities.  Physical Review A (Atomic, Molecular, and Optical Physics), 80(6):062327, 2009.  DOI: 10.1103/PhysRevA.80.062327.  eprint arXiv:0907.2170.
  * [CHSH69] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  Proposed experiment to test local hidden-variable theories.  Phys. Rev. Lett., 23(15):880–884, Oct 1969.  DOI: 10.1103/PhysRevLett.23.880.
  * [Cir80] B. S. Cirel’son.  Quantum generalizations of Bell’s inequality.  Letters in Mathematical Physics, 4(2):93–100, 03 1980.  DOI: 10.1007/BF00417500.
  * [Col16] Andrea W. Coladangelo.  Parallel self-testing of (tilted) EPR pairs via copies of (tilted) CHSH.  2016\.  eprint arXiv:1609.03687.
  * [CSUU08] Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay.  Perfect parallel repetition theorem for quantum XOR proof systems.  Computational Complexity, 17(2):282–299, 2008.  DOI: 10.1007/s00037-008-0250-4.  eprint arXiv:quant-ph/0608146v2.
  * [HPDF15] Michal Hajdusek, Carlos A. Perez-Delgado, and Joseph F. Fitzsimons.  Device-independent verifiable blind quantum computation.  2015\.  eprint arXiv:1502.02563 .
  * [McK13] Matthew McKague.  Interactive proofs for BQP via self-tested graph states.  Theory of Computing, 12(3):1–42, 2013.  DOI: 10.4086/toc.2016.v012a003.  eprint arxiv:1309.5675.
  * [McK16] Matthew McKague.  Self-testing in parallel.  New Journal of Physics, 18(4):045013, 2016.  DOI: 10.1088/1367-2630/18/4/045013.  eprint arXiv:1511.04194.
  * [MMMO06] Frédéric Magniez, Dominic Mayers, Michele Mosca, and Harold Ollivier.  Self-testing of quantum circuits.  In M Bugliesi et al., editor, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, number 4052 in Lecture Notes in Computer Science, pp. 72–83, 2006.  DOI: 10.1007/11786986“˙ 8.  eprint arXiv:quant-ph/0512111v1 .
  * [MS16] Carl A. Miller and Yaoyun Shi.  Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices.  J. ACM, 63(4):33:1–33:63, October 2016.  DOI: 10.1145/2885493.  eprint arXiv:1402.0489.
  * [MY04] Dominic Mayers and Andrew Yao.  Self testing quantum apparatus.  Quantum Information and Computation, 4(4):273–286, July 2004\.  eprint arXiv:quant-ph/0307205.
  * [MYS12] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani.  Robust self-testing of the singlet.  Journal of Physics A: Mathematical and Theoretical, 45(45):455304, 2012.  DOI: 10.1088/1751-8113/45/45/455304.  eprint arXiv:1203.2976.
  * [PR92] Sandu Popescu and Daniel Rohrlich.  Which states violate Bell’s inequality maximally?  Physics Letters A, 169(6):411 – 414, 1992.  DOI: 10.1016/0375-9601(92)90819-8.
  * [RUV13] Ben W. Reichardt, Falk Unger, and Umesh Vazirani.  Classical command of quantum systems.  Nature, 496(7446):456–460, 04 2013.  DOI: 10.1038/nature12035.
  * [VV14] Umesh Vazirani and Thomas Vidick.  Fully device-independent quantum key distribution.  Physical review letters, 113(14):140501, 2014.  DOI: 10.1103/PhysRevLett.113.140501.
  * [WBMS16] Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani.  Device-independent parallel self-testing of two singlets.  Phys. Rev. A, 93:062121, Jun 2016.  DOI: 10.1103/PhysRevA.93.062121.  eprint arXiv:1512.02074.


# Localized versions of extremal problems

David Malec  University of Maryland, College Park  Casey Tompkins  Alfréd
Rényi Institute of Mathematics

###### Abstract

We generalize several classical theorems in extremal combinatorics by
replacing a global constraint with an inequality which holds for all objects
in a given class. In particular we obtain generalizations of Turán’s theorem,
the Erdős-Gallai theorem, the LYM-inequality, the Erdős-Ko-Rado theorem and
the Erdős-Szekeres theorem on sequences.

##  1 Introduction

In this paper we will consider a systematic way to generalize some classical
problems in extremal combinatorics. In an extremal problem one typically seeks
to maximize the number of some object among a class of finite structures
(graphs, hypergraphs, sequences etc.) avoiding some other object. We seek to
reformulate such problems in the following more general setting. Rather than
considering structures of some class forbidding a given object, we define a
weight function which holds for arbitrary structures from that class. We then
prove a bound on this weight function that immediately implies the original
extremal theorem.

We begin by discussing the case of graphs. For a graph $G$, we denote the set
of vertices and edges of $G$ by $V(G)$ and $E(G)$, respectively. A clique with
$r$ vertices is denoted by $K_{r}$. For a given graph $F$, the Turán number
${\rm ex}(n,F)$ is the maximum number of edges possible in an $n$-vertex graph
which does not contain $F$ as a subgraph.

Turán’s theorem asserts that for all $r$ we have ${\rm
ex}(n,K_{r+1})\leq\frac{(r-1)n^{2}}{2r}$, and equality holds when $r$ divides
$n$ and we take a complete $r$-partite graph with classes of equal size. Now
we attempt to generalize this result by considering an arbitrary $n$-vertex
graph $G$ and looking at the behavior of the edges. Since for any $r$ we wish
to recover the bound of $\frac{(r-1)n^{2}}{2r}$ in the case when no edge is in
a copy of $K_{r+1}$, we define a weight on the edges based on the size of the
cliques in which that edge occurs. To this end, let

$c(e)=\max\\{r:\mbox{$e$ occurs in a subgraph of $G$ isomorphic to
$K_{r}$}\\}.$

It is then natural to assign each edge a weight
$\left.1\middle/\frac{(c(e)-1)n^{2}}{2c(e)}\right.$ with denominator matching
the corresponding extremal bound. We wish to prove that the sum of these
weights is at most $1$. Moving the $n^{2}/2$ factor to the other side of the
inequality we arrive at the following natural assertion.

######  Theorem 1.

Let $G$ be any $n$-vertex graph, then

$\sum_{e\in E(G)}\frac{c(e)}{c(e)-1}\leq\frac{n^{2}}{2},$

and equality holds if and only if $G$ is a multipartite graph with classes of
equal size.

We prove Theorem 1 in Section 2 using an inductive argument. Theorem 1 was
very recently proved independently by Domagoj Bradac̆ [4] using the method of
Motzkin and Straus [15]. Bradac̆ [4] communicates that the statement of
Theorem 1 was proposed by Balogh and Lidický and discussed at a conference in
Oberwolfach in 2022. Moreover he mentions that stability results in the case
of $K_{5}$-free graphs have been obtained by Balogh and Lidický. We will refer
to Theorem 1 as a localized version of Turán’s theorem since the weight
assigned to each edge depends only on the structures which it participates in.
The bound from Turán’s theorem for any $r$ is easily recovered by noting that
in a $K_{r+1}$-free graph each edge has weight at most $\frac{r}{r-1}$.

Next we turn our attention to the case of paths. Erdős and Gallai [5] proved
that an $n$-vertex graph without a copy of a path of length $k$ contains at
most $\frac{(k-1)n}{2}$ edges. Let $P_{k}$ denote the path of length $k$ (that
is, with $k$ edges). Again we introduce a function on the edges

$p(e)=\max\\{k:\mbox{$e$ occurs in a subgraph of $G$ isomorphic to
$P_{k}$}\\}.$

Then we have the following localized version of the theorem of Erdős and
Gallai.

######  Theorem 2.

Let $G$ be any $n$-vertex graph, then

$\sum_{e\in E(G)}\frac{1}{p(e)}\leq\frac{n}{2},$

and equality holds if an only if every connected component of $G$ is a clique.

Again, the original theorem of Erdős and Gallai is easily recovered by taking
a $P_{k}$-free graph $G$ and using that $p(e)\leq k-1$. Also one can rather
simply give a similar result for stars. For any graph $G$, let $s(e)$ be the
maximum number of edges in a star containing $e$.

######  Proposition 1.

Let $G$ be any $n$-vertex graph, then

$\sum_{e\in E(G)}\frac{1}{s(e)}\leq\frac{n}{2},$

and equality holds if and only if each connected component of $G$ is regular.

Abstractly we are looking for theorems of the following form. Suppose we have
an infinite sequence of graphs $F_{1},F_{2},\dots$ with the property that for
all $i$, $F_{i}$ is a subgraph of $F_{i+1}$. Let $G$ be an arbitrary
$n$-vertex graph, and for each edge $e\in E(G)$ set

$f(e)=\max\\{i:\mbox{$e$ is an edge of a subgraph of $G$ isomorphic to
$F_{i}$}\\}.$

Then we would like to know when it holds that

$\sum_{e\in E(G)}\frac{1}{{\rm ex}(n,F_{f(e)+1})}\leq 1.$ (1)

A bound of this form simultaneously generalizes each of the corresponding
results for extremal numbers ${\rm ex}(n,F_{i})$. Indeed, if $G$ does does not
contain a particular $F=F_{i}$ as a subgraph, then by the monotonicity of the
extremal function ${\rm ex}(n,F)$ with respect to taking subgraphs, we have

$\frac{\left\lvert{E(G)}\right\rvert}{{\rm ex}(n,F)}\leq\sum_{e\in
E(G)}\frac{1}{{\rm ex}(n,F_{f(e)+1})}\leq 1,$

and consequently $\left\lvert{E(G)}\right\rvert\leq{\rm ex}(n,F)$. A stronger
corollary of a bound of the form (1) is the following. Suppose for an infinite
sequence of graphs $F_{1}\subset F_{2}\subset\cdots$ we have a bound of the
form (1). Fix $F=F_{i}$ for some $i$, and partition the edge set $E(G)$ into
two parts $S$ and $T$ where $S=\\{e\in E(G):\mbox{$e$ is an edge of a subgraph
of $G$ isomorphic to $F$}\\}$ and $T=E(G)\setminus S$, then

$\frac{\left\lvert{S}\right\rvert}{{\rm
ex}(n,F)}+\frac{\left\lvert{T}\right\rvert}{\binom{n}{2}}\leq 1.$ (2)

The bound (2) follows by replacing ${\rm ex}(n,F_{j})$ with ${\rm
ex}(n,F_{i})$ for all $j<i$ and replacing ${\rm ex}(n,F_{j})$ with
$\binom{n}{2}$ for all $j>i$. Note that Theorems 1 and 2 are not precisely of
the form (1) since the corresponding extremal bounds which we generalize are
only tight in certain divisibility cases. It would be interesting to extend
these results so that the inequality is sharp in all divisibility cases. Note
that inequalities of the form (1) do not hold for any possible graph sequence.
Indeed, if $F_{1}$ is a triangle, $F_{2}$ is a bow tie and $G$ is a balanced
complete bipartite graph plus an edge, then (1) is violated.

In extremal set theory bounds of the form (2) sometimes have had applications
for ‘cross’-versions [8] (also termed ‘multicolor’-versions [2, 11]) of
various problems. We now turn our attention to finding localized versions of
some theorems in extremal set theory.

First we recall the classical LYM-inequality [1, 12, 13, 17] which generalizes
Sperner’s theorem [16] about antichains in the Boolean lattice. Let
$\mathcal{A}\subset 2^{[n]}$ be a family of sets forming an antichain with
respect to the subset relation, then we have

$\sum_{A\in\mathcal{A}}\frac{1}{\binom{n}{\left\lvert{A}\right\rvert}}\leq 1.$
(3)

Daykin and Frankl proved the following natural extension of the LYM-
inequality. Suppose that $\mathcal{A}$ is any family of subsets of $[n]$ and
let $\mathcal{S}\subset\mathcal{A}$ be the collection of those sets in
$\mathcal{A}$ incomparable to every set in $\mathcal{A}$. Write
$\mathcal{T}=\mathcal{A}\setminus\mathcal{S}$, then

$\sum_{A\in\mathcal{S}}\frac{1}{\binom{n}{\left\lvert{A}\right\rvert}}+\frac{\left\lvert{\mathcal{T}}\right\rvert}{2^{n}}\leq
1.$ (4)

The inequality (4) can be used to directly bound the sum of the sizes of a
family of cross-Sperner families.

A $(k+1)$-chain in $2^{[n]}$ is a collection of sets
$A_{1},A_{2},\dots,A_{k+1}$ such that for all $i$ we have $A_{i}\subset
A_{i+1}$. Another natural extension of the LYM-inequality is the following.
Suppose $\mathcal{A}\subset 2^{[n]}$ contains no $(k+1)$-chain, then

$\sum_{A\in\mathcal{A}}\frac{1}{\binom{n}{\left\lvert{A}\right\rvert}}\leq k.$
(5)

The inequality (5) can be proved by applying a Mirsky-type [14] decomposition
to the set family or directly by imitating Lubell’s proof of the LYM-
inequality [9]. Our main result in this topic is a generalization of (5). For
an arbitrary $\mathcal{A}\subset 2^{[n]}$, let

$c(A)=\max\\{k:\mbox{$A$ participates in a $k$-chain consisting of sets from
$\mathcal{A}$}\\}.$

######  Theorem 3.

Let $\mathcal{A}\subset 2^{[n]}$ be an arbitrary family of sets, then

$\sum_{A\in\mathcal{A}}\frac{1}{\binom{n}{\left\lvert{A}\right\rvert}c(A)}\leq
1.$

Moreover equality holds if and only if $\mathcal{A}$ consists of a union of
complete levels.

A further extension of Theorem 3 to the setting of posets is given in Section
4, Corollary 1. Observe that if $\mathcal{A}$ is a $(k+1)$-chain free family,
then $c(A)\leq k$ and we recover (5). The inequality in Theorem 3 and (4) seem
to be independent of each other.

Next we consider intersecting set families. Recall that the Erdős-Ko-Rado [6]
theorem asserts than if $r<n/2$, then a pairwise intersecting family
consisting of sets of size $r$ has size at most $\binom{n-1}{r-1}$. In order
to find a shorter proof for a theorem of Hilton [8], Borg [3] proved the
following generalization of the Erdős-Ko-Rado theorem. Let $r<n/2$ and let
$\mathcal{A}$ be an arbitrary family of $r$-element subsets of $[n]$. Let
$\mathcal{S}=\\{A\in\mathcal{A}:\mbox{for all $B\in\mathcal{A}$, $A$ and $B$
intersect}\\}$ and $\mathcal{T}=\mathcal{A}\setminus\mathcal{S}$, then

$\left\lvert{\mathcal{S}}\right\rvert+\frac{r}{n}\left\lvert{\mathcal{T}}\right\rvert\leq\binom{n-1}{r-1}.$
(6)

We now give a localized version generalizing Borg’s result.

######  Theorem 4.

Let $\mathcal{A}$ be a collection of $r$-element subsets of $[n]$. Let $m$ be
the function on $\mathcal{A}$ defined by setting $m(A)=n/r$, if $A$ is
contained in some matching of $\left\lfloor{n/r}\right\rfloor$ sets from
$\mathcal{A}$, and setting $m(A)$ equal to the size of the largest matching in
$\mathcal{A}$ containing $A$, if that matching has fewer than
$\left\lfloor{n/r}\right\rfloor$ sets, then

$\sum_{A\in\mathcal{A}}\frac{1}{m(A)}\leq\binom{n-1}{r-1}.$

Note that there are at least three distinct constructions attaining equality
in Theorem 4. In addition to a star or a full level we may take the
construction consisting of all sets of size $r$ containing at least one of two
fixed elements.

Finally, we turn out attention to perfect graphs, posets and sequences. Recall
that a perfect graph is one in which the chromatic number and clique number of
all induced subgraphs are equal. In particular for a perfect graph $G$ we have
$\omega(G)=\chi(G)$ and so $\alpha(G)\omega(G)=\alpha(G)\chi(G)\geq n$. In
Section 4 we prove the analogous localized version of this bound as a
corollary of a more technical statement about functions on perfect graphs that
may be of independent interest.

Let $G$ be a perfect graph, and for each $v\in V(G)$ let $c(v)$ be the largest
size of a clique containing $v$, and let $i(v)$ be the largest size of an
independent set containing $v$.

######  Theorem 5.

For any $n$-vertex perfect graph $G$, we have

$\sum_{v\in V(G)}\frac{1}{c(v)i(v)}\leq 1.$

As a consequence of Theorem 5 we deduce a localized version of the classical
theorem of Erdős and Szekeres [7] about sequences.

##  2 Proofs of localized versions of extremal graph theorems

###### Proof of Theorem 1.

We prove the claim by induction on $n$. The result holds trivially for $n=1$,
so assume $n>1$ and let $G$ be an $n$-vertex graph with edge set $E$. If the
graph contains no edges, then the bound follows trivially so assume $G$ has at
least one edge. Let $k$ be the size of the largest clique in $G$, and let $C$
be a clique of size $k$. We split the edges $E$ into three parts: $E_{C}$, the
edges within $C$; $E_{G\setminus C}$, the edges within $G\setminus C$; and
$E_{S}$, the edges that connect $C$ and $G\setminus C$. We bound the
contribution to the sum from each of these separately.

  1. 1.

Since $C$ is a clique of maximum size in $G$, we know that $E_{C}$ contains
$k(k-1)/2$ edges, all with $c(e)=k$. So we can see that

$\sum_{e\in
E_{C}}\frac{c(e)}{c(e)-1}=\frac{k(k-1)}{2}\frac{k}{k-1}=\frac{k^{2}}{2}.$

  2. 2.

For all $v\in V(G\setminus C$), let $C_{v}=\\{w\in C\mid\\{v,w\\}\in E\\}$.
Note that $C_{v}\cup\\{v\\}$ is itself a clique, and so we may conclude that
$\left\lvert{C_{v}}\right\rvert+1\leq k$, and
$c(e)\geq\left\lvert{C_{v}}\right\rvert+1$ for all edges $e$ that connect $v$
to $C$. Thus, we obtain that

$\sum_{e\in E_{S}}\frac{c(e)}{c(e)-1}\leq\sum_{v\in V(G\setminus
C)}\left\lvert{C_{v}}\right\rvert\frac{\left\lvert{C_{v}}\right\rvert+1}{\left\lvert{C_{v}}\right\rvert}\leq\sum_{v\in
V(G\setminus C)}k=(n-k)k.$

  3. 3.

Lastly, our induction hypothesis implies that

$\sum_{e\in E_{G\setminus C}}\frac{c(e)}{c(e)-1}\leq\frac{(n-k)^{2}}{2}.$

Combining all three of the estimates above we obtain that

$\sum_{e\in
E}\frac{c(e)}{c(e)-1}\leq\frac{k^{2}}{2}+k(n-k)+\frac{(n-k)^{2}}{2}=\frac{n^{2}}{2},$
(7)

as required.

Now suppose we have equality in (7), then all three of the estimates above
must be tight. From the third estimate we obtain that $G\setminus C$ is a
complete multipartite graph with $m$ equal size classes where $m\leq k$.
Moreover, for each edge $e$ in $E_{G\setminus C}$ we have that
$m=c_{G\setminus C}(e)=c_{G}(e)$. By the second estimate each vertex from
$G\setminus C$ must have exactly $k-1$ neighbors in $C$. Consequently if we
take a vertex from each class in $G\setminus C$, we obtain that these vertices
have a common neighborhood in $C$ of size at least $k-m$. Thus every edge in
$E_{G\setminus C}$ is part of a $k$-clique in $G$ and so $m=c_{G}(e)=k$.
Finally, any selection of $k$ vertices from distinct classes of $G\setminus C$
must have an empty common neighborhood in $C$ for otherwise we would have a
larger clique. It follows that for every class in $G\setminus C$ there is
exactly one vertex in $C$ to which all vertices in that class are nonadjacent,
and this vertex is distinct for each class in $G\setminus C$. Adding each such
vertex from $C$ to its respective class in $G\setminus C$, we see that $G$ is
a balanced multipartite graph as required. ∎

Now we give the proof of the localized version of the Erdős-Gallai theorem.

###### Proof of Theorem 2.

We prove the claim by induction on $n$. The claim follows trivially for $n=1$,
so assume $n>1$. Furthermore, assume that $G$ is connected; if $G$ is not
connected, we may simply apply the induction hypothesis to each connected
component in turn, and sum the results to arrive at our claim.

Assume the longest path in $G$ has length $k$, and let $P$ be a path achieving
this length, with endpoints $v$ and $w$. We use $R(v)$ to denote the edges
that have $v$ as an endpoint; note that $R(v)$ cannot contain any edges to
vertices outside of $P$, since otherwise $P$ is not maximal. We define $R(w)$
similarly, and note it has the same property.

If there exists a circuit $C$ that includes all the vertices on $P$, then we
can see that $P$ must include all the vertices in $G$. Otherwise, since $G$ is
connected, we can find a path from $C$ to any vertex $u$ not lying on it; but
the path that starts at $u$, goes to $C$, and then goes around $C$ is strictly
longer that $P$, a contradiction. So in this case, we have that $k=n-1$.
Furthermore, every edge in the graph either lies on the circuit $C$ or forms a
chord in $C$. In either case, we can easily construct a path of length $n-1$
containing it. So we can see that

$\sum_{e\in
E(G)}\frac{1}{p(e)}=\left\lvert{E(G)}\right\rvert\frac{1}{n-1}\leq\binom{n}{2}\frac{1}{n-1}=\frac{n}{2},$
(8)

and we are done. Equality in the theorem implies (8) is tight and so $G$ is a
clique.

Now we assume that there is no circuit $C$ that includes all of the vertices
of $P$. Note that this means that $\\{v,w\\}\notin E(G)$. Furthermore, let
$\\{v^{\prime},w^{\prime}\\}$ be any internal edge of $P$, where $v^{\prime}$
is closer to $v$ along $P$ (and so $w^{\prime}$ is closer to $w$ along $P$).
Note that
$P\setminus\\{\\{v^{\prime},w^{\prime}\\}\\}\cup\\{\\{v,w^{\prime}\\},\\{v^{\prime},w\\}\\}$
would be a circuit, so either $\\{v,w^{\prime}\\}\notin E(G)$ or
$\\{v^{\prime},w\\}\notin E(G)$. Recalling that $R(v)$ and $R(w)$ contain no
edges to vertices outside $P$, we may thus conclude that

$\left\lvert{R(v)}\right\rvert+\left\lvert{R(w)}\right\rvert\leq 2+(k-2)=k.$

So without loss of generality, we assume that
$\left\lvert{R(v)}\right\rvert\leq k/2$. Note that any $e\in R(v)$ has
$p(e)=k$, since there is always some $e^{\prime}\in P$ that can be replaced
with $e$ to form a new path $P^{\prime}$. Thus, if we apply our induction
hypothesis to $G\setminus v$, we get that

$\sum_{e\in E(G)}\frac{1}{p(e)}=\sum_{e\in
R(v)}\frac{1}{p(e)}+\sum_{E(G)\setminus R(v)}\frac{1}{p(e)}\leq\sum_{e\in
R(v)}\frac{1}{p(e)}+\sum_{E(G)\setminus R(v)}\frac{1}{p_{G\setminus
v}(e)}\leq\frac{k}{2}\frac{1}{k}+\frac{n-1}{2}=\frac{n}{2}.$ (9)

Equality in the theorem statement implies that both inequalities in (9) hold
with equality for all $e\in E(G)$. This means that for the edges $e$ in
$E(G\setminus v)$ we have $p(e)=p_{G\setminus v}(e)$. Moreover by induction
$G\setminus v$ must be a disjoint union of cliques. If $k=1$ the graph
consists of just an edge and we are done, so assume $k>1$. Consider the edge
$e$ incident to $v$ in $P$ and the next edge $f$ in the path. Since $f$
belongs to a connected component which is a clique in $G\setminus v$ and $f$
is adjacent to $e$, we can easily find a longer path in $G$ containing $f$ and
so $p(e)>p_{G\setminus v}(e)$. Thus in the present case, equality cannot hold
in (9). ∎

We conclude this section with the proof of the analogous statement about
stars.

###### Proof of Proposition 1.

For a vertex $v$ of $G$ set $w(v)$ equal to the sum of $\frac{1}{s(e)}$ across
edges $e$ which are incident to $v$. Then for all $v$,

$w(v)\leq\sum_{e:v\in e}\frac{1}{d(v)}=1.$ (10)

Then we have

$2\sum_{e\in E(G)}\frac{1}{s(e)}=\sum_{v}w(v)\leq n,$

and the result follows.

Suppose we have equality in (10), then for every $v$ every edge $e$ incident
to $v$ must satisfy $s(e)=d(v)$. It is then immediate that each component is
regular, as claimed. ∎

Given that we have localized versions of the extremal results of paths and
stars it would be natural to investigate what happens in the case of an
arbitrary sequence of trees: $T_{1}\subset T_{2}\subset\cdots$. However, such
an investigation may be difficult since we only know the validity of the
Erdős-Sós conjecture in certain cases. Nonetheless one could hope to prove
localized versions conditional on the Erdős-Sós conjecture.

##  3 Proofs of localized versions of extremal hypergraph theorems

We begin by proving the localized version of the LYM-inequality.

###### Proof of Theorem 3.

Let $\mathcal{A}\subset 2^{[n]}$ be any family of sets. Call a chain of sets
$\mathcal{C}$ maximal if it contains a set of every possible cardinality. We
will double count pairs $(A,\mathcal{C})$ where $A\in\mathcal{A}$ and
$\mathcal{C}$ is a maximal chain in $2^{[n]}$ using a weight function $w$. We
define $w$ by

$w(A,\mathcal{C})=\begin{cases}\frac{1}{c(A)}&\mbox{if }A\in\mathcal{A}\mbox{
and }A\in\mathcal{C},\\\ 0&\mbox{otherwise.}\end{cases}$

First fix a set $A\in\mathcal{A}$. There are
$\left\lvert{A}\right\rvert!(n-\left\lvert{A}\right\rvert)!$ maximal chains
containing $A$ and so

$\sum_{A\in\mathcal{A}}\sum_{\mathcal{C}}w(A,\mathcal{C})=\sum_{A\in\mathcal{A}}\frac{\left\lvert{A}\right\rvert!(n-\left\lvert{A}\right\rvert)!}{c(A)}.$
(11)

Now, fix a maximal chain $\mathcal{C}$. Suppose $\mathcal{C}$ contains $m$
sets from $\mathcal{A}$; then we have $c(A)\geq m$ for all such sets, since
these $m$ sets themself form a chain of length $m$. Thus, we have

$\sum_{\mathcal{C}}\sum_{A\in\mathcal{A}}w(A,\mathcal{C})\leq\sum_{\mathcal{C}}\frac{m}{m}=n!.$
(12)

Comparing $\eqref{eq1}$ and $\eqref{eq2}$ yields

$\sum_{A\in\mathcal{A}}\frac{1}{c(A)\binom{n}{\left\lvert{A}\right\rvert}}\leq
1,$ (13)

as desired. Suppose we have equality in $\eqref{eq3}$. Then the total weight
on every chain must be $1$. Note that this trivially holds in the case where
$\mathcal{A}$ equals a union of levels. We claim that this is the only case
where equality holds. Suppose $\mathcal{A}$ is not a union of levels. Then
there is at least one level of $2^{[n]}$ containing both a set from
$\mathcal{A}$ and one not from $\mathcal{A}$. Moreover, there must be such a
pair with symmetric difference $2$. Call these sets $A$ and $B$ where
$A\in\mathcal{A}$ with $c(A)=m$ and $B\notin\mathcal{A}$. Since
$\left\lvert{A}\right\rvert=\left\lvert{B}\right\rvert=t$ and $A$ and $B$ have
symmetric difference $2$, it follows that the intersection, $A\cap B$, is of
size $t-1$ and the union, $A\cup B$, is of size $t+1$.

Consider any chain of the form
$\mathcal{C}_{1}=\\{\varnothing,A_{1},A_{2},\dots,A_{t-2},A\cap B,A,A\cup
B,A_{t+2},\dots,[n]\\}$, then the total weight along $\mathcal{C}_{1}$ must be
$1$ in the equality case and so $\mathcal{C}_{1}$ contains $m$ sets from
$\mathcal{A}$ each with weight $1/m$. Now, consider the chain
$\mathcal{C}_{2}=\\{\varnothing,A_{1},A_{2},\dots,A_{t-2},A\cap B,B,A\cup
B,A_{t+2},\dots,[n]\\}$. Since this chain contains the same sets as
$\mathcal{C}_{1}$ except with $B\notin\mathcal{A}$ instead of
$A\in\mathcal{A}$, the total weight of $\mathcal{C}_{2}$ is $1-1/m$, a
contradiction. ∎

###### Proof.

We will use Katona’s method of cyclic permutations [10]. By a cyclic
permutation, $\sigma$, we mean a cyclic ordering
$a_{1}<a_{2}<\dots<a_{n}<a_{1}$ of $[n]$. A set $A\in\mathcal{A}$ is an
interval in $\sigma$ if its elements are consecutive in $\sigma$. An interval
starts at $a_{i}$ if $a_{i}$ is the smallest element in the order on $A$
induced by $\sigma$. We will double count pairs $(A,\sigma)$ where
$A\in\mathcal{A}$ and $\sigma$ is a cyclic permutation of $[n]$ with the
following weight function:

$w(A,\sigma)=\begin{cases}\frac{1}{m(A)},&\text{if }A\in\mathcal{A}\text{ and
}A\text{ is an interval in }\sigma,\\\ 0,&\text{otherwise.}\end{cases}$

Every set $A\in\mathcal{A}$ is an interval in exactly $r!(n-r)!$ cyclic
permutations. Thus, we have

$\sum_{A\in\mathcal{A}}\sum_{\sigma}w(A,\sigma)=\sum_{A\in\mathcal{A}}\frac{r!(n-r)!}{m(A)}.$

Now we switch the order of summation and fix a cyclic permutation $\sigma$. In
Lemma 1, whose proof is given below, we will show that the the total weight
contributed by intervals along any cyclic permutation is at most $r$. It
follows that

$\sum_{\sigma}\sum_{A\in\mathcal{A}}w(A,\sigma)\leq\sum_{\sigma}r=(n-1)!r.$

Dividing through by $(n-r)!r!$ gives the desired result. ∎

######  Lemma 1.

Let $\sigma$ be a cyclic permutation and denote by $\mathcal{A}^{\sigma}$ the
collection of those sets in $\mathcal{A}$ which are intervals in $\sigma$. Let
$m(A)$ be defined as in the theorem, then

$\sum_{A\in\mathcal{A}^{\sigma}}\frac{1}{m(A)}\leq r.$

###### Proof.

Let $n=tr+s$ where $t$ and $s$ are integers and $0\leq s<r$. Similarly, let
$\left\lvert{A^{\sigma}}\right\rvert=lr+k$ where $l$ and $k$ are integers and
$0\leq k<r$.

First, we show that every set in $\mathcal{A}^{\sigma}$ is contained in an
$l$-matching. Notice that if an interval $A$ does not begin less than $r$
positions before or after an interval $B$, then $A$ and $B$ are disjoint.
Consider the cyclic order attained by removing all of those elements from
$\sigma$ at which no $A\in\mathcal{A}^{\sigma}$ begins. If two elements $a$
and $b$ are more than $r$ positions apart in this contracted order, then they
must have been at least $r$ positions apart in the original order, and so the
interval beginning at $a$ in $\sigma$ must be disjoint from the interval
beginning at $b$. Now take an arbitrary element of the contracted order and
move along the order $r$ elements at a time. After $l-1$ repetitions we are
still a distance of at least $r$ from the starting element. The starting
element, along with the elements encountered at each of the $l-1$ steps
constitute an $l$-matching. Since our choice of starting element in the
contracted order was arbitrary, it follows that every
$A\in\mathcal{A}^{\sigma}$ is contained in an $l$-matching.

Now, we distinguish two cases based on whether $l=t$ or $l<t$. If $l=t$, then
since every $A\in\mathcal{A}^{\sigma}$ is contained in an $l$-matching we
have,

$\sum_{A\in\mathcal{A}^{\sigma}}\frac{1}{m(A)}=\frac{\left\lvert{\mathcal{A}^{\sigma}}\right\rvert}{n/r}\leq\frac{n}{n/r}=r.$

It remains to show the bound for the case $l<t$. Since $l<t$ there are at
least $r-k$ elements of $\sigma$ at which no set in $\mathcal{A}^{\sigma}$
begins. Choose any $r-k$ such elements.

We will refer to these elements as “fake” starting positions as we will
imagine additional intervals beginning at them. The size of
$\mathcal{A}^{\sigma}$ plus the number of fake starting positions is then
$(l+1)r$. As before, we consider the contracted order containing only elements
beginning sets in $\mathcal{A}^{\sigma}$ and the fake starting positions.
Since $(l+1)r$ is a multiple of $r$, we may partition the elements of the
resulting order into $r$ classes each containing $l+1$ elements such that in
any class the distance between two elements is a multiple of $r$. There are
only $r-k$ fake starting positions, so it follows that some $k$ of these
classes consist of only elements corresponding to sets in
$\mathcal{A}^{\sigma}$. For each set $A$ contained in one of the $k$ classes
consisting only of sets in $\mathcal{A}^{\sigma}$, we know that $m(A)\geq l+1$
since $A$ is in a $l+1$-matching with the other sets in the class. It follows
that the net weight contributed by such sets is at most

$\frac{k(l+1)}{l+1}=k.$ (14)

Subtracting off the sets in $\mathcal{A}^{\sigma}$ which fill one of the
classes and the fake starting positions leaves

$r(l+1)-k(l+1)-(r-k)=l(r-k)$

sets. Since every set in $\mathcal{A}^{\sigma}$ is contained in matching of
size at least $l$, we have that the weight contribution of the remaining sets
is at most

$\frac{l(r-k)}{l}=r-k.$ (15)

Thus, adding (14) and (15) we have that

$\sum_{A\in\mathcal{A}^{\sigma}}\frac{1}{m(A)}\leq k+(r-k)=r,$

as desired. ∎

##  4 Results on perfect graphs, posets and sequences

######  Theorem 6.

Let $G$ be a perfect graph, and $f$ be a function on the set of pairs $(H,v)$
where $H$ is an induced subgraph of $G$ and $v\in V(H)$. Assume that $f$
satisfies $f(H,v)\leq f(G[V(H)\cup\\{w\\}],v)$ for inducerd subgraphs $H$ of
$G$ and $w\in V(G)\setminus V(H)$. Also assume that if $H$ is an independent
set in $G$, then we have

$\sum_{v\in V(H)}\frac{1}{f(H,v)}\leq 1.$

For an induced subgraph $H$ of $G$, let $c(H,v)$ be the size of the largest
clique in $H$ that contains $v$. Then, we have

$\sum_{v\in V(H)}\frac{1}{f(H,v)c(H,v)}\leq 1.$

###### Proof.

We use induction on the size of the largest clique in $H$. If $H$ is an
independent set, then we have $c(H,v)=1$ for all $v\in V(H)$ and the desired
bound follows by assumption. Otherwise, let $k$ be the size of the largest
clique in $H$, and assume we have the desired bound whenever the maximum
clique has size strictly less than $k$. Define $B$ as the set of all vertices
contained in a $k$-clique, that is $B=\\{v\in V(H):c(H,v)=k\\}$. Since $G$ is
perfect, we may conclude that the chromatic number of $H$ is also $k$. Let $R$
be any $k$-coloring of $H$. We form the natural partition of $B$ based on $R$
as

$B_{r}=\\{v\in B:v\text{ has color $r$ under }R\\}.$

Now, for any color $r\in R$, we know that every $k$-clique in $H$ must contain
exactly one vertex with color $r$, and so the largest clique in $H\setminus
B_{r}$ must have size exactly $k-1$. We apply induction to get that

$\sum_{v\in V(H\setminus B_{r})}\frac{1}{f(H\setminus B_{r},v)c(H\setminus
B_{r},v)}\leq 1$ (16)

for every $r\in R$.

Now, for all $v\in H$ and all $r\in R$, we have by assumption that $f(H,v)\geq
f(H\setminus B_{r},v)$ and trivially that $c(H,v)\geq c(H\setminus B_{r},v)$.
Recall that $B_{r}$ contains exactly one vertex from each $k$-clique with
vertices in $B$ (which is every $k$-clique in $H$). Thus, for any $v\in
B\setminus B_{r}$ it is clear that $c(H\setminus B_{r},v)=k-1$, and so for all
$v\in B$ we have $c(H\setminus B_{r},v)=\frac{k-1}{k}c(H,v)$. Summing Equation
(16) over all $r$ gives us

$\displaystyle k$ $\displaystyle\geq\sum_{r\in R}\sum_{v\in V(H\setminus
B_{r})}\frac{1}{f(H\setminus B_{r},v)c(H\setminus B_{r},v)}$
$\displaystyle=\sum_{r\in R}\sum_{v\in V(H\setminus B)}\frac{1}{f(H\setminus
B_{r},v)c(H\setminus B_{r},v)}+\sum_{r\in R}\sum_{v\in V(G[B\setminus
B_{r}])}\frac{1}{f(H\setminus B_{r},v)c(H\setminus B_{r},v)}$
$\displaystyle\geq k\sum_{v\in V(H\setminus
B)}\frac{1}{f(H,v)c(H,v)}+(k-1)\sum_{v\in
V(G[B])}\frac{1}{f(H,v)\frac{k-1}{k}c(H,v)}$ $\displaystyle=k\sum_{v\in
V(H)}\frac{1}{f(H,v)c(H,v)}.$

Dividing both sides by $k$ yields the desired inequality. ∎

The following corollary is a natural generalization of Theorem 3 to any poset
satisfying the LYM-inequality.

######  Corollary 1.

Let $P$ be a ranked poset with $N_{i}$ elements of rank $i$. For $x\in P$, let
$\left\lvert{x}\right\rvert$ denote the rank of $x$. Suppose that any
antichain $S\subset P$ satisfies the LYM-type inequality:

$\sum_{x\in S}\frac{1}{N_{\left\lvert{x}\right\rvert}}\leq 1.$

Then, given any set $T\subset P$ we have

$\sum_{x\in T}\frac{1}{N_{\left\lvert{x}\right\rvert}c(T,x)}\leq 1.$

###### Proof.

Let $G$ be the comparability graph of $P$. A set $S\subset P$ corresponds to
an induced subgraph $G_{S}$ of $G$. Observe that $S$ is an antichain if and
only if $G_{S}$ is an independent set. Moreover the chains in the poset $P$
are in one-to-one correspondence with the cliques in $G$. The assumption that
an antichain $S$ in $P$ satisfies the LYM-inequality shows that the conditions
of Theorem 6 are satisfied when $f(G_{S},x)$ is taken to be
$N_{\left\lvert{x}\right\rvert}$ for all $S$ and $x$. Then the conclusion of
Corollary 1 is immediate from the conclusion of Theorem 6. ∎

Now we deduce Theorem 5 from Theorem 6.

###### Proof of Theorem 5.

Let $G$ be a perfect graph and for an induced subgraph $H$ and $x\in V(H)$ let
$f(H,v)$ be the maximum size of an independent set in $H$ which contains $v$.
It is easy to see $f$ satisfies the condition increasing condition. If $H$ is
an independent set then $f(H,v)=\left\lvert{V(H)}\right\rvert$ and the other
condition of Theorem 6 is satisfied. Then taking $G=H$, the conclusion of
Theorem 6 gives the required bound:

$\sum_{v\in V(G)}\frac{1}{i(v)c(v)}=\sum_{v\in V(G)}\frac{1}{f(G,v)c(G,v)}\leq
1.\qed$

Again by considering the comparability graph the following corollary is
immediate from Theorem 5. For any poset $P$ and $x\in P$ let $C(x)$ denote the
size of the largest chain $x$ belongs to and $A(x)$ the size of the largest
antichain $x$ belongs to.

######  Corollary 2.

Let $P$ be any poset we have,

$\sum_{x\in P}\frac{1}{A(x)C(x)}\leq 1.$

By considering the natural poset defined on sequences of numbers
$x_{1},x_{2},\dots,x_{N}$ where $x_{i}\prec x_{j}$ if $i<j$ and $x_{i}<x_{j}$
we obtain a localized version of the classical result of Erdős and Szekeres
[7]. For a finite sequence of real numbers let $i(x)$ and $d(x)$ denote the
longest increasing and decreasing subsequence containing $x$, respectively.
Then we have the following.

######  Corollary 3.

For any finite sequence $S$ of real numbers

$\sum_{x\in S}\frac{1}{i(x)d(x)}\leq 1.$

##  5 Acknowledgements

The second author would like to thank Rutger Campbell and Tuan Tran for
insightful discussions about this topic and Nika Salia for providing the
example with the triangle and bow tie in the introduction. The research of the
second author was supported by NKFIH grant K135800.

## References

  * [1] Béla Bollobás.  On generalized graphs.  Acta Mathematica Hungarica, 16(3-4):447–452, 1965.
  * [2] Béla Bollobás, Peter Keevash, and Benny Sudakov.  Multicoloured extremal problems.  Journal of Combinatorial Theory, Series A, 107(2):295–312, 2004\.
  * [3] Peter Borg.  A short proof of a cross-intersection theorem of Hilton.  Discrete mathematics, 309(14):4750–4753, 2009.
  * [4] Domagoj Bradač.  A generalization of Turán’s theorem.  arXiv preprint arXiv:2205.08923, 2022.
  * [5] Paul Erdős and Tibor Gallai.  On maximal paths and circuits of graphs.  Acta Math. Acad. Sci. Hungar. v10, pages 337–356, 1959.
  * [6] Paul Erdős, Chao Ko, and Richard Rado.  Intersection theorems for systems op finite sets.  Quart. J. Math. Oxford Ser.(2), 12:313–320, 1961.
  * [7] Paul Erdős and George Szekeres.  A combinatorial problem in geometry.  Compositio mathematica, 2:463–470, 1935.
  * [8] A.J.W. Hilton.  An intersection theorem for a collection of families of subsets of a finite set.  Journal of the London Mathematical Society, 2(3):369–376, 1977\.
  * [9] Gyula O.H. Katona.  Sperner type theorems, Ph. D. Thesis, Eötvös Loránd University.  1968\.
  * [10] Gyula O.H. Katona.  A simple proof of the Erdős-Chao Ko-Rado theorem.  Journal of Combinatorial Theory, Series B, 13(2):183–184, 1972\.
  * [11] Peter Keevash, Mike Saks, Benny Sudakov, and Jacques Verstraëte.  Multicolour Turán problems.  Advances in Applied Mathematics, 33(2):238–262, 2004.
  * [12] David Lubell.  A short proof of Sperner’s lemma.  Journal of Combinatorial Theory, 1(2):299, 1966.
  * [13] Lev D. Meshalkin.  Generalization of Sperner’s theorem on the number of subsets of a finite set.  Theory of Probability & Its Applications, 8(2):203–204, 1963.
  * [14] Leon Mirsky.  A dual of Dilworth’s decomposition theorem.  The American Mathematical Monthly, 78(8):876–877, 1971.
  * [15] Theodore S. Motzkin and Ernst G. Straus.  Maxima for graphs and a new proof of a theorem of turán.  Canadian Journal of Mathematics, 17:533–540, 1965.
  * [16] Emanuel Sperner.  Ein satz über untermengen einer endlichen menge.  Mathematische Zeitschrift, 27(1):544–548, 1928.
  * [17] Koichi Yamamoto.  Logarithmic order of free distributive lattice.  Journal of the Mathematical Society of Japan, 6(3-4):343–353, 1954\.