TITLE: Equation of the graph by points
QUESTION [0 upvotes]: I have a non-static set of points
How do I get the equation of a graph passing through all these points?
The graph should consist of straight lines, as in the picture
As in the picture below, except that it's not a table, but one equation

REPLY [2 votes]: You can define piecewise linear function. If you have nodes $$x_1<x_2<\ldots<x_n$$ and the desired function has to satisfy the set of conditions $f(x_i)=y_i$ for $1\leq i\leq n$ then one can define $f$ by the formula
$$f(x) = \frac{y_{k+1}-y_k}{x_{k+1}-x_k}\cdot(x-x_k)+y_k,\quad x_k\leq x\leq x_{k+1}.$$ This defines $f$ on $[x_1,x_k]$.
You can also be interested in splines, which are  piecewise polynomial functions and can be not only continuous but also differentiable.
Here is a solution with degree-$1$ splines for the following data :
$$\begin{array}{|c|c|c|c|c|c|}
\hline
x_i&0&1&3&5&6&9\\
\hline
y_i&0&4&1.5&3&-0.5&0\\
\hline\end{array}$$
with solution given by a linear combination
$$f(x)=\sum y_i t_{x_{i},x_{i+1},x_{i+2}}(x)$$
of the piecewise linear continuous "tent functions" (or "triangular functions") defined in the following way:
$$t_{a,b,c}(x)=\begin{cases}&1 \ \ \text{for} \ x=b\\
&0 \ \ \text{for x outside} \ (a,c)
\end{cases}$$
Remark: please note that the coefficients of the linear combination of these tent functions are precisely values $y_i$. If we take all coefficients equal to $1$, we will get a trapezoidal function with  a plateau sum of these "tent functions"  is a "trapezoidal function" with a "plateau at "1".

Fig. 1: All the basis "tent functions" colored in blue, green, purple, black resp. have their maximum equal to $1$.


TITLE: Relation of integration of parabola over multiple volumes
QUESTION [0 upvotes]: I have a multivariate function $f(x) = \sum_i^d x_i^2 c_i$ where all $c_i$ are non-negative and $x$ is a $d$-dimensional vector.
I will integrate it over volume $A$ and volume $D$.
Volume $A$ is determined by: $A = \{ ||x||_2 \leq C \}$.
Volume $B$ is determined by: $B = \{ \max_i |x_i| \leq C\}$.
Volume $D = B \setminus A$.
Note that $B$ is the rectangle enclosing volume $A$.
For me it seems obvious that the mean of $f$ on $D$ must be larger than the mean of $f$ on $A$:
$$\frac{\int_D f(x) dx}{\int_D dx} \geq \frac{\int_A f(x) dx}{\int_A dx}$$
This can be made clear using a drawing, since $D$ surrounds $A$.
However, showing this statement formally seems difficult. Perhaps it is possible to do a coordinate transformation to some coordinate $u_i^2 = x_i^2 c_i$ and then to polar-coordinates, and compare the integrals there?

REPLY [0 votes]: It is better to avoid polar coordinates. Both the hypercube $B$ and the hypersphere $A$ are left invariant by mapping $(x_1,\ldots,x_d)$ into $(x_{\sigma(1)},\ldots,x_{\sigma(d)})$ for any $\sigma\in S_d$ or just for any cyclic permutation of the coordinates. For instance, assuming $d=3$,
$$ \int_{B}\left(c_1 x_1^2+c_2 x_2^2+c_3 x_3^2\right)\,d\mu =\frac{c_1+c_2+c_3}{3}\int_{B}(x_1^2+x_2^2+x_3^2)\,d\mu$$
and the same applies to $A$. The whole problem boils down to the computation of two simple integrals, $\int_{A}\|x\|^2\,d\mu$ and $\int_{B}\|x\|^2\,d\mu$. Just pick your favourite technique to find a closed form for them.
Your second inequality is just stating that the mean value of $f$ over $D$ is greater than the mean value of $f$ over $A$ - this requires no computation at all, it is a trivial consequence of the convexity of $f$. You may also notice that the Laplacian of $f$ is non-negative, hence $f$ is a subharmonic function.


TITLE: How to solve $(2x^2-1)^2=2y^2 - 1$ in positive integers?
QUESTION [5 upvotes]: I encountered this question (posed by Fermat) in a letter from Fermat to Carcavi and was wondering what would be the best elementary way to solve it.

Solve in positive integers$$(2x^2-1)^2=2y^2 - 1$$

Any help will be appreciated.
Thanks in advance.

REPLY [2 votes]: For $y$ a prime, the simplest solution I've ever seen is this answer in another thread. I have no doubt that (very elementary) method could be adapted to solve the fully-general theorem. Another solution, given by Mahoney, I replicated here.


TITLE: If 300 contestants line up to play this game, what is the > approximate probability that at least 150 of them win?
QUESTION [3 upvotes]: Problem: On a game show contestants play a game by putting mini-golf balls from
  a five yard distance. Every contestant gets three chances to make a
  put. Assume that every contestant has an equal chance of 0.2 of
  sinking a ball. The game is won, if at least one of the three balls
  can be sunk.

(a) What is the probability that a contestant wins this game? Which distribution
are you using and what are the parameters?
(b) How many contestants do you expect to see on average until the third one wins?
Which distribution are you using and what are the parameters?
I have a X-Bin(3,0.2)
then, P(win the game)=3C1 *0.2 (1-0.2)^2 + 3c2 * 0.2 * (1-0.2)^1 +3c2 * 0.2 ($$)^0=0.488
Point b): NB(3, 0.488) then E(y)=3/0.488=6.25
I need help with this this point:

(c) If 300 contestants line up to play this game, what is the
  approximate probability that at least 150 of them win?

I need to use normal? How? the book said the answer is 0.360

REPLY [1 votes]: Let $X \sim Bin(300,0.488)$. Then using the converse probability $P(X\geq 150)=1-P(X\leq 149)$
Using the De Moivre–Laplace theorem
$P(X\leq 149)\approx\Phi\left( \frac{149+0.5-n\cdot p}{\sqrt{n\cdot p\cdot (1-p)}} \right)$
+0.5 is the continuity correction factor.
$=\Phi\left( \frac{149+0.5-300\cdot 0.488}{\sqrt{300\cdot 0.488\cdot 0.512}} \right)=\Phi(0.358)$
$\Phi(0.358)$ is the value of the cdf of the standard normal distribution if $z=0.358$. If you look at this table you can see that $\Phi(0.358)$ is about $ 0.64=64\%$


TITLE: Are Riemann curvature tensors defined up to a total derivative?
QUESTION [1 upvotes]: Consider a case where the Riemann Tensor is given by
$$R^{\mu}_{~~~\nu\rho\sigma} = P^{\mu}_{~~~\nu\rho\sigma} +\nabla_{\rho}A^{\mu}_{~~~\nu\sigma}-\nabla_{\sigma}A^{\mu}_{~~~\nu\rho}$$
It seems to me that the extra total covariant derivative may be absorbed by making a first order change of the connection
$$\Gamma^{\mu}_{\nu\rho} \to \Gamma^{\mu}_{\nu\rho} + A^{\mu}_{\nu\rho}$$
Is this a correct way to go about it?  Also, such a term will not play any role in the action $\int \sqrt{g}R$ so can I simply ignore these total derivatives ? Are two Riemann tensors defined by such a total derivative can be considered equivalent or belonging to some equivalence class?

REPLY [2 votes]: No, it is not. The Riemann curvature tensor is a construction from Differential Geometry, although it is employed in General Relativity. As mentioned in the comments, it is defined (up to a sign convention) as $R(X,Y) = [\nabla_X, \nabla_Y] - \nabla_{[X,Y]}$ in coordinate-free notation. Wikipedia also shows the expression in components, if you prefer to have a look.
While adding a total derivative won't change the Einstein–Hilbert action, it will change the interpretation of the tensor. Let us take a look at the expression for $R$ obtained from your expression. We have
$$R_{\mu\nu} \equiv R^{\rho}{}_{\mu\rho\nu} = P_{\mu\nu} + \nabla_\rho A^{\rho}{}_{\mu\nu} - \nabla_\nu A^{\rho}{}_{\mu\rho}$$
and hence
$$R \equiv R_{\mu}{}^\mu = P + \nabla_\rho A^{\rho\mu}{}_{\mu} - \nabla_\mu A^{\rho\mu}{}_{\rho},$$
so in general $R \neq P$. This means that for a flat spacetime, your definition will not give $R = 0$. While the equations of motions are, of course, still the same, the interpretation of the curvature tensor as the curvature tensor no longer holds. Notice this is just an example, and imposing $\nabla_\rho A^{\rho\mu}{}_{\mu} = \nabla_\mu A^{\rho\mu}{}_{\rho}$ by hand might still not correct other issues concerning other scalars and other tensors. The problem in general is that redefining the Riemann tensor will change its geometric meaning.


TITLE: Let $p$ be a prime, and $k \in \mathbb N$. What is the order of $U(p^{k})$?
QUESTION [0 upvotes]: Q: Let $p$ be a prime, and $k \in \mathbb N$. What is the order of $U(p^{k}) = |U(p^{k})|$?
I understand that $|U(p)| = (p-1)$.
With some experimenting I suspect that $|U(p^{k})| = (p-1)*p^{k-1} $.
How can I (dis)prove this?

REPLY [0 votes]: $|U(n)|=\phi(n)$ where $\phi$ is called as the Euler phi function.
$\phi(n)=|\{a\in \mathbb N|  1\leq a<n  \ and\  (a,n)=1 \}|$  and it is easy to see that $\phi(p)=p-1$
Now, let's try to find $\phi(p^k)$. Notice that if $(a,p^k)>1$ then $p$ must divides $a$. Thus, $a$ must be of the form $a=kp$ where $k\in \{ 1,2,...,p^{k-1}-1\}$ so,there are $p^{k-1}-1$ elements which is not desired and in total we have $p^k-1$ elements.
Hence, $\phi(p^k)=(p^k-1)-(p^{k-1}-1)=p^k-p^{k-1}=(p-1)p^{k-1}$


text:
\section{Introduction}

\subsection*{Sparsity and density.}
The theory of structural sparsity in graphs revolves around two notions introduced by Ne\v{s}et\v{r}il and Ossona de Mendez in~\cite{NesetrilM08a,NesetrilM08b,NesetrilM11}: {\em{bounded expansion}} and {\em{nowhere denseness}}.
We say that a class of graphs $\Cc$ is {\em{nowhere dense}} if for every $d\in \N$, there is an upper bound $t(d)\in \N$ on the sizes of cliques that can be found as depth-$d$ minors of graphs from $\Cc$. Here,
$H$ is a {\em{depth-$d$ minor}} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting mutually disjoint connected subgraphs of radius at most $d$.
More restrictively, $\Cc$ has {\em{bounded expansion}} if for every $d\in \N$ there is an upper bound $c(d)\in \N$ on the average degree of depth-$d$ minors of graphs from $\Cc$.
The concept of bounded expansion encompasses a vast majority of well-studied classes of sparse graphs.
Examples include proper minor-closed classes, classes with bounded maximum degree,

graphs that can be drawn in the plane with a bounded number of crossings per edge~\cite{NOdMW12}, and
intersection graphs of bounded-ply families of fat objects in Euclidean spaces~\cite{Har-PeledQ17}.

While the definitions of nowhere denseness and of bounded expansion may seem arbitrary at first glance, the last decade has witnessed a prodigious development of various structural techniques for them.
Apart from describing many interesting combinatorial properties, these techniques have strong applications in algorithm design and uncover deep links with logical aspects of sparsity.
In particular, it has been shown~\cite{DKT12,GroheKS17} that for subgraph-closed classes of graphs, nowhere denseness exactly
\footnote{
Assuming that $\FO$ model-checking cannot be solved in FPT time on all graphs
(which is implied by
the widely believed conjecture that $\mathsf{FPT} \neq \mathsf{W}[1]$,
or even $\mathsf{AW}[\star]\neq \mathsf{FPT}$).
}
delimits classes where every property expressible in the First-Order logic $\FO$
can be tested in almost linear time.
This shows that nowhere denseness corresponds to an important dividing line in descriptive complexity theory.
We refer to the monograph of Ne\v{s}et\v{r}il and Ossona de Mendez~\cite{sparsity} and to more recent lecture notes~\cite{notes} for a broader introduction to the subject.

The techniques of structural sparsity can be applied not only to describe structure in sparse graphs, but also to analyze dense graphs that can be derived from sparse ones using simple combinatorial transformations.
Take, for instance, the concept of the power of a graph: for a graph $G$ and an integer $d\in \N$, the {\em{$d$th power}} $G^d$ is the graph on the same vertex set as $G$, where two vertices $u$ and $v$ are considered adjacent
if and only if they are at distance at most $d$ in $G$. Taking a power can turn a sparse graph into a dense one: e.g.\ the second power of a star is a clique.
Thus, if $\Cc$ is a class of sparse graphs, then the class $\Cc^d$ of the $d$th powers of graphs in $\Cc$ may contain dense graphs, but the intuition is that graphs from $\Cc^d$ should admit strong structural properties due to admitting
sparse pre-images. This work fits into the broader direction of trying to describe and quantify these properties.

Kwon et al.~\cite{KPS20} proved a useful structural theorem for powers of classes of bounded expansion, namely they admit {{low shrubdepth colorings}}\footnote{In~\cite{KPS20}, Kwon et al. discuss
a weaker notion of {\em{low rankwidth colorings}} and only mention that the colorings they obtain for powers of classes of bounded expansion are actually low shrubdepth colorings. This has been later clarified and generalized
by Gajarsk\'y et al. in~\cite{GajarskyKNMPST18}.}.
This mirrors the existence of so-called {\em{low treedepth colorings}} in classes of bounded expansion, see~\cite{NesetrilM08a}.

Shrubdepth was introduced by Ganian et al.~\cite{GanianHNOM19} and, informally, a graph has small shrubdepth if its adjacency relation can be concisely described in a tree of bounded depth, called the {connection model}.
A \emph{connection model} for a graph \(G\) with a label set \(\Lambda\) is a tuple \((\lambda, T, \set{Z_x \colon x \in V(T) \setminus V(G)})\) consisting of:
\begin{enumerate}
\item a labelling \(\lambda\) of vertices of \(G\) with labels from \(\Lambda\),
\item a rooted tree \(T\) whose leaves are the vertices of \(G\), and
\item for every non-leaf node $x$ of $T$, a symmetric binary relation $Z_x\subseteq \Lambda^2$,
\end{enumerate}
such that the following condition holds. For every pair of vertices \(u, v\) in $G$, we have
\[uv \in E(G) \Leftrightarrow (\lambda(u), \lambda(v)) \in Z_x,\quad
\textrm{where \(x\) is the lowest common ancestor of \(u\) and \(v\) in \(T\).}\]
The \emph{shrubdepth}\footnote{The original definition proposed by Ganian et al. in~\cite{GanianHNOM19} is slightly different and applies only to classes of graphs, and not single graphs. The variant defined here leads to the same notion of having low shrubdepth colorings.} of $G$ is the lowest number $s$ such that $G$ has a connection model of depth at most~$s$ over a label set of size $s$.
A class $\Cc$ admits \emph{low shrubdepth colorings} if for every $p\in \N$ there exist numbers $f(p)$ and $s(p)$ such that every graph $H$ in $\Cc$ has a vertex coloring with at most $f(p)$ colors in which
every subset of $p$ colors induces a subgraph of shrubdepth at most $s(p)$.

The result of Kwon et al.~\cite{KPS20} was later generalized by Gajarsk\'y et al.~\cite{GajarskyKNMPST18} to arbitrary one-dimensional $\FO$ interpretations of classes of bounded expansion,
where the binary predicate ``$\dist(u,v)\leq d$'' that is used in the definition of the $d$th power can be replaced with any property of a pair of vertices that can be expressed in $\FO$.
This encompasses a broad range of graph transformations definable in logic.

The existence of low shrubdepth colorings with a constant number colors entails a number of strong structural properties.
For instance, as observed in~\cite{KPS20}, it implies that the class in question is $\chi$-bounded.
Mimicking the situation for low treedepth colorings, one should expect an analogue of these results for powers, or even $\FO$ interpretations, of nowhere dense classes.
Therefore, the following natural conjecture, posed in
\cite{KPS20}, is the goal
which sets the motivation for our work.

\begin{conjecture}\label{conj:lsc}
Let $\Cc$ be a nowhere dense class of graphs, $d$ be a positive integer, $\eps$ be a positive real.
Then there is a function $f\colon \N\to \N$ such that for every natural $p$ and
every $n$-vertex graph $G$ in $\Cc^d$, there is a coloring of $G$ using $\Oh(n^{\eps})$ colors in which every subset of $p$ colors induces a subgraph of $G$ of shrubdepth at most $f(p)$.
\end{conjecture}

Unfortunately, the arguments provided in~\cite{KPS20,GajarskyKNMPST18} do not generalize to the nowhere dense setting and Conjecture~\ref{conj:lsc} remains open.
While this statement would expose interesting and potentially quite useful structure in powers of nowhere dense classes,
one can also investigate those hypothetical corollaries and try to prove them using different means, in hope of gathering more insight.
Our work contributes to this line of research.

\subsection*{Our results.} We study properties of powers of nowhere dense classes related to the Erd\H{o}s-Hajnal conjecture.
Recall that a graph class $\Cc$ has the {\em{Erd\H{o}s-Hajnal property}} if there exists $\delta>0$ such that every graph $G$ in $\Cc$ on $n$ vertices contains either a clique or an independent set of size at least~$n^\delta$.
The {\em{Erd\H{o}s-Hajnal conjecture}}~\cite{EH89} hypothesizes that for every fixed graph $H$, the class of graphs that exclude $H$ as an induced subgraph has the Erd\H{o}s-Hajnal property.
The conjecture is open for as simple graphs as $H=C_5$ and $H=P_5$, see the survey of Chudnovsky~\cite{Chudnovsky14} for an overview.

It is known that for every nowhere dense class $\Cc$ and integer $d\in \N$, the class $\Cc^d$ excludes some half-graphs as a semi-induced subgraph~\cite{AdlerA14}, and hence has the Erd\H{o}s-Hajnal property~\cite{MalliarisSh14} (see also~\cite[Chapter 5, Theorem 2.8]{notes} for a compact explanation).
However, when $\Cc$ has bounded expansion, it is a simple consequence of the existence of low shrubdepth colorings that the class $\Cc^d$ actually enjoys the strong Erd\H{o}s-Hajnal property defined as follows.
A class of graphs admits the {\em{strong Erd\H{o}s-Hajnal property}} if there exists a constant $\delta>0$ such that in every $n$-vertex graph $G$ with $n \ge 2$ from the class there exist disjoint vertex subsets $A,B$, each of size
at least $\delta n$, such that either every vertex of $A$ is adjacent to every vertex of $B$ (i.e.\ $A$ is {\em{complete}} to $B$),
or there is no edge with one endpoint in $A$ and the other in $B$ (i.e.\ $A$ is {\em{anticomplete}} to $B$).
It is known that for hereditary classes, the strong Erd\H{o}s-Hajnal property implies the (standard) Erd\H{o}s-Hajnal property~\cite{APPRS05}, but the converse implication is not true e.g.\ for triangle-free graphs.

Let us note that while the connection between low shrubdepth colorings and the strong Erd\H{o}s-Hajnal property was observed during the work on~\cite{KPS20,GajarskyKNMPST18}, it has not been included in any published manuscript. Hence, for the sake of completeness we clarify it in Appendix~\ref{app:shrubs}.

Conjecture~\ref{conj:lsc}, if true, would imply a weaker variant of the strong Erd\H{o}s-Hajnal property for powers of nowhere dense classes, where the lower bound of $\delta n$ on the cardinalities of $A$
and $B$ would be replaced by $n^{1-\eps}$, for any $\eps>0$ fixed in advance and sufficiently large $n$. The main result of this work is a direct proof of this statement; in fact, we show its significant generalization.

\begin{theorem}\label{thm:main}
Let $\calC$ be a nowhere dense graph class, $d$ be a positive integer, $\epsi$ be a positive~real.
Then there is an integer $k_0$ such that for every graph $G$ in $\Cc$ and vertex subsets $A$, $B$ in $G$ satisfying $|A \cup B|\geq k_0$,
there exist disjoint sets $A'$ and $B'$ with $A' \subseteq A$, $B'\subseteq B$ such that
$$|A'| \ge (1-\eps)\cdot |A|,\qquad\qquad |B'| \ge \frac{|B|}{|A \cup B|^{\eps}},$$
and in $G^d$, every vertex from $A'$ is adjacent either to all vertices from $B'$, or to no vertex from $B'$.
\end{theorem}

If sets \(A'\) and \(B'\) satisfy Theorem~\ref{thm:main}, then we can find a subset
\(A''\) consisting of at least half of vertices of \(A'\) which is either complete or
anticomplete to \(B'\) in \(G^d\).
Hence, applying the theorem with \(A = B = V(G)\) implies that
in every sufficiently large \(n\)-vertex graph \(G\) from a fixed nowhere dense
class there are two disjoint sets which are either complete or anticomplete
to each other in \(G^d\) where the lower bounds on the sizes of the sets
are \((1/2 - \eps)n\) and \(n^{1-\eps}\), respectively.
Moreover, we may choose \(A'\) and \(B'\) from any prescribed vertex subsets
\(A\) and \(B\) and the lower bounds will be scaled appropriately.

The main technical step towards the proof of Theorem~\ref{thm:main} is the following lemma, which may be of independent interest.
Here, we say that a vertex subset $S$ {\em{$d$-separates}} vertex subsets $A$ and $B$ in a graph $G$ if every path of length at most $d$ with one endpoint in $A$ and second in $B$ intersects~$S$.

\begin{lemma}\label{lem:new-abs}
  Let $\calC$ be a nowhere dense graph class, $d$ be a positive integer, $\eps$ be a positive~real.
  Then there is an integer $k_0$ such that for every graph $G$ in $\Cc$ and vertex subsets $A$, $B$ in $G$ satisfying $|A \cup B|\geq k_0$,
  there exist a vertex subset $S$ and disjoint
  vertex sets $A'$ and $B'$
  with $A'\subseteq A$, $B'\subseteq B$ such that
  $$|A'|\geq (1-\eps)\cdot |A|,\qquad |B'|\geq \frac{|B|}{|A \cup B|^\eps},\qquad |S|\leq |A \cup B|^\eps,$$
  and $S$ $d$-separates $A'$ and $B'$.
\end{lemma}

Theorem~\ref{thm:main} follows from combining Lemma~\ref{lem:new-abs} with known bounds on the neighborhood complexity in nowhere dense classes~\cite{EickmeyerGKKPRS17}.
However, Lemma~\ref{lem:new-abs} can be also used together with the newer bounds on the number of $\FO$ types in sparse graphs~\cite{PilipczukST18a}
to give the following generalization of Theorem~\ref{thm:main} to $\FO$ interpretations
of nowhere dense classes (see Section~\ref{sec:interpretations} for relevant definitions).
\begin{theorem}\label{thm:interpretations}
Let $\calC$ be a nowhere dense graph class, $d$ be a positive integer, $\epsi$ be a positive~real, $\varphi(x,y)$ be an $\FO$ formula with two free variables.
Then there is an integer $k_0$ such that for every graph $G$ in $\Cc$ and vertex subsets $A$, $B$ in $G$ satisfying $|A \cup B|\geq k_0$,
there exist disjoint sets $A'$ and $B'$ with $A' \subseteq A$, $B'\subseteq B$ such that
$$|A'| \ge (1-\eps)\cdot |A|,\qquad\qquad |B'| \ge \frac{|B|}{|A \cup B|^{\eps}},$$
and for every $a \in A'$, either we have $G\models \varphi(a,b)$ for all $b\in B'$,
or $G\models \neg \varphi(a,b)$ for all $b\in B'$.
\end{theorem}

\begin{comment}
\begin{theorem*}
Let $\Cc$ be a nowhere dense class of graphs, $\varphi(x,y)$ be an $\FO$ formula with two free variables, and $\eps$ be a positive real.
There exists an integer $k_0$ such that for every graph $G$ in $\Cc$ and vertex subset $W$ in $G$ satisfying $|W|\geq k_0$, there exist disjoint subsets $A$, $B$ with $A,B\subseteq W$ such that:
\[
|A|\geq \left(1/2-\eps\right) |W|,\qquad |B|\geq |W|^{1-\eps},
\]
and either $G\models \varphi(a,b)$ for all $a\in A$ and $b\in B$,
or $G\models \neg \varphi(a,b)$ for all $a\in A$ and $b\in B$.

\end{theorem*}
\end{comment}

Finally, we show that unlike in the bounded expansion case, the nowhere dense classes of
graphs do not have the strong Erd\H{o}s-Hajnal property.
Therefore, in Theorem~\ref{thm:main} we cannot require that both of the subsets
\(A'\) and \(B'\) contain a fixed positive fraction of sets \(A\) and \(B\) respectively.

\begin{proposition}\label{prop:no-strong-EH}
 There exists a nowhere dense class of graphs that does not enjoy the strong Erd\H{o}s-Hajnal property.
\end{proposition}

This proposition was already shown in~\cite[Theorem~50]{JNOdMS20}, but we propose an
arguably simpler explanation of this fact.

\subsection*{Other related work.}
Very recently, Ne\v{s}et\v{r}il et al.~\cite{NOdMPZ19} proved that powers of sparse graph classes admit good clustering properties in the following sense:
if $\Cc$ is a nowhere dense class and $d\in \N$ is fixed, then every graph from $\Cc^d$ can be vertex-partitioned into cliques so that contracting every clique to a single vertex yields a graph from another
nowhere dense class $\Dd$, which depends only on $\Cc$ and $d$. The same holds also when the notion of nowhere denseness is replaced with having bounded expansion.
From this result it is possible to derive a weaker formulation of Theorem~\ref{thm:main}, where both sides are allowed to have slightly sublinear sizes, see Appendix~\ref{app:shrubs} for a discussion.

Malliaris and Shelah~\cite{MalliarisSh14} gave improved bounds for the Regularity Lemma in classes of graphs that exclude a {\em{semi-induced half-graph}} of a constant length, also known as {\em{combinatorially stable}} classes.
It is known that powers of nowhere dense classes, and even their images under $\FO$ interpretations, have this property~\cite{AdlerA14}, hence the results of Malliaris and Shelah apply to our setting.
From the results provided in~\cite{MalliarisSh14} it is possible to derive statements of flavor similar to the strong Erd\H{o}s-Hajnal property,
however the obtained bounds would be significantly weaker than the ones provided by Theorem~\ref{thm:main}.

The ``almost'' strong Erd\H{o}s-Hajnal property of similar flavor as the one provided by Theorem~\ref{thm:main} was proved by Fox et al.~\cite{FPT10} for the class of intersection graphs of $x$-monotone curves in the plane.
Namely, if $\Cc$ is this class, then
there is a positive constant $\delta$ such that in every $n$-vertex graph $G$ in $\Cc$ with $n \geq 2$, one can find
either find disjoint vertex subsets $A$ and $B$ such that $|A|,|B|\geq \delta n/\log n$ and $A$ is complete to $B$,
or disjoint vertex subsets $A$ and $B$ such that $|A|,|B|\geq \delta n$ and $A$ is anticomplete to $B$.
In general, the strong Erd\H{o}s-Hajnal property appears often in the setting of geometric intersection graphs, for instance
the class of intersection graphs of convex subsets of the plane enjoys it~\cite{FPT10}. See~\cite{FP08} for a survey on this line of research.

Finally, in a very recent series of papers, Scott, Seymour and Spirkl study how large {\em{pure pairs}} --- disjoint vertex subsets $A$ and $B$ such that $A$ is either complete or anticomplete to $B$ --- can be found in graphs drawn from various graph classes defined by forbidding induced subgraphs. In particular, in one of the works~\cite{ScottSS19} they prove a statement of flavor very similar to ours: they extract a pure pair $(A,B)$ such that $|A|=\Omega(n)$ and $|B|=\Omega(n^{1-\epsi})$ for any $\epsi>0$ fixed beforehand. The setting is, however, very different: they assume excluding a ``long'' subdivision of a fixed graph~$H$ as an induced subgraph, which imposes structure unlike the one found in powers of sparse~graphs.

\subsection*{Organization.}
In Section~\ref{sec:preliminaries} we list the preliminary definitions.
In particular, we define the key sparsity measure for our work, the weak coloring numbers.
In Section~\ref{sec:lemmas} we prove our main technical contribution, i.e.\ Lemma~\ref{lem:new-abs}.
In Section~\ref{sec:proofs-of-the-theorem} we wrap up the proof of Theorem~\ref{thm:main}
and in Section~\ref{sec:interpretations} we show how to lift it to FO interpretations of nowhere dense classes.
Section~\ref{sec:example} describes a nowhere dense class without the strong Erd\H{o}s-Hajnal property.
In Appendix~\ref{app:shrubs} we include a proof that a class with low shrubdepth colorings admits the strong Erd\H{o}s-Hajnal property.

\begin{comment}

\section{Introduction: old}

A class of graphs $\calC$ has the \emph{Erd\H{o}s-Hajnal} property if there is a positive constant $\delta$ such that every $n$-vertex graph $G$ in $\calC$ contains a clique or an independent set of size $n^{\delta}$.
Erd\H{o}s and Hajnal conjectured~\cite{EH89} that for every graph $H$,
the class of \emph{$H$-free} graphs, i.e.\
the class of graphs with no induced subgraph isomorphic to $H$, has the property.
A class of graphs $\calC$ has the \emph{strong Erd\H{o}s-Hajnal} property
if there is a positive constant $\delta$ such that every $n$-vertex graph $G$ in $\calC$ with $n \ge 2$
contains two disjoint subsets of vertices of size at least $\delta n$ each, such that
either there are all possible edges between them or there is no edge between them.

As first observed by Alon et al.~\cite{APPRS05}, a class closed under taking induced subgraphs
that has the strong Erd\H{o}s-Hajnal property also has the Erd\H{o}s-Hajnal property.

For convienience,
we call a pair $(A,B)$ of disjoint subsets of vertices of a graph $G$ \emph{complete}
if there are all possible edges between $A$ and $B$ in $G$, and \emph{anticomplete}
if there are no edges between $A$ and $B$ in $G$.

TODO: mention \url{https://web.math.princeton.edu/~pds/papers/foxconj/paper.pdf}.

It is known that for some graphs $H$, e.g.\ for $H = K_3$, the $H$-free graphs have the Erd\H{o}s-Hajnal property, but not its strong version.
Still, the approach to the Erd\H{o}s-Hajnal property through the strong property proved to be fruitful.
Chudnovsky, Scott, Seymour, and Spirkl~\cite{CSSS18} showed that
for every tree $T$,
the class of graphs excluding $T$ and its complement $\overline{T}$ as induced subgraphs has the strong Erd\H{o}s-Hajnal property.
There is a series of papers on Erd\H{o}s-Hajnal style properties for geometric intersection graphs.
Fox, Pach and T\'{o}th~\cite{FPT10} showed that
the class of intersection graphs of families of convex sets in the plane has
the strong Erd\H{o}s-Hajnal property.
Another result from~\cite{FPT10} gives a class that 'almost' admits the property:
For the class $\calC$ of intersection graphs of $x$-monotone curves in the plane,
there is a positive constant $\delta$ such that for every $n$-vertex graph $G$ in $\calC$ with $n \ge 2$,
either there is a complete pair $(A, B)$ with $|A|,|B|\geq \delta n/\log n$ in $G$,
or there is an anticomplete pair $(A, B)$ with $|A|,|B|\geq \delta n$ in $G$.
See~\cite{FP08} for a survey on this line of research.

For the usual classes of sparse graphs,
like planar graphs or graphs excluding a fixed graph as a minor,
the strong Erd\H{o}s-Hajnal property holds trivially
as they contain independent sets of linear size.
The question is much more interesting when we ask for powers of sparse graphs
or more generally for classes interpreted from sparse classes of graphs.
Given a graph $G$ and a positive integer $d$, the $d$-\emph{th power} of $G$, denoted by $G^d$,
is the graph on the same set of vertices as $G$ where two vertices are adjacent
if they are at distance at most $d$ in $G$.
The powers of sparse graphs can be dense, e.g.\ the second powers of stars are complete graphs.
Still, it is believed that they inherit somewhat simple structure.

Over the last decade the structural graph theory has expanded beyond the classes of graphs
excluding a fixed graph as a minor.
Ne{\v{s}}et{\v{r}}il and Ossona de Mendez introduced concepts of
classes of graphs with
\emph{bounded expansion}~\cite{NOdM08} and
classes of graphs that are \emph{nowhere dense}~\cite{NOdM11}.
Let us give some informal intuition behind these concepts,
see Section~\ref{sec:preliminaries} for the precise definitions.
The key idea in both cases is to look at minors of \emph{bounded depth}, that is,
minors that can be obtained by first contracting disjoint connected subgraphs of bounded radius, and then possibly removing some vertices or edges.
In a nowhere dense class it is required that bounded-depth minors exclude at least some graph (which can depend on the depth).
In a class with bounded expansion the requirement is stronger:
For every $r \geq 1$, depth-$r$ minors should be sparse, that is, their average degrees should be bounded by some function $f(r)$.

These properties are robust and include
graphs excluding a fixed graph as a minor, bounded degree graphs, and
graphs that allow drawings on a plane with bounded number of crossings per edge,
see~\cite{NOdMW12}.
At first sight, the properties might seem weak and vague for
a graph class.
Yet, this notion captures enough structure to allow solving a wide range
of algorithmic problems efficiently:
Dvořák, Kráľ and Thomas~\cite{DKT12} devised a linear-time algorithm for testing
first-order definable properties in classes of bounded expansion.
The following result by Kwon, Pilipczuk, and Siebertz~\cite{KPS20} was a starting point for our project.

\begin{theorem}[Kwon, Pilipczuk, and Siebertz~\cite{KPS20}]\label{thm:bd-exp-strong-eh}
Let $\calC$ be a class with bounded expansion and let $d$ be an integer with \(d \ge 1\).
There exists a constant $\delta$ with \(\delta > 0\) such that
for every $n$-vertex graph $G$ in $\calC$ with $n \ge 2$
there are two disjoint subsets $A$, $B$ of $V(G)$ such that
\begin{enumerate}
  \item $|A|, |B| \ge \delta n$ and
  \label{item:bounded-exp-bounds}
  \item $(A,B)$ is complete or anticomplete in $G^d$.
\end{enumerate}
In other words, the class of $d$-th powers of graphs in $\calC$ has
the strong Erd\H{o}s-Hajnal property.
\end{theorem}

Very often, results which hold for classes with bounded expansion have their counterparts for nowhere dense classes, with a factor-$n^{o(1)}$ quantitative difference.
For instance, it is natural to expect that for
a nowhere dense class $\calC$ and a positive constant $\epsi$ an analogue of \cref{thm:bd-exp-strong-eh} is true
with the bounds within item \ref{item:bounded-exp-bounds}
replaced with $|A|, |B| = \Omega(n^{1-\epsi})$.
However, the proof that works in bounded expansion setting seem to be difficult to lift
into nowhere dense setting.
(This is often the case; we come back to this in the last section, see~\cref{conj:low-shrub-depth}).
With a very different proof strategy,
we prove the result for nowhere dense and
obtain a complete or anticomplete pair in which one side is even of linear size.

\begin{theorem}\label{thm:main}
Let $\calC$ be a nowhere dense class of graphs,
let $d$ be an integer and \(\epsi\) be a real with \(d \ge 1\) and \(\epsi > 0\).
There exists a constant $\delta$ with \(\delta > 0\) such that for any
graph $G$ in $\calC$ and any nonempty subsets \(A_0\) and \(B_0\) of \(V(G)\)
there exist sets $A$, $B$ with \(A \subseteq A_0\) and \(B \subseteq B_0\)
such that
\begin{enumerate}
  \item $|A| \ge (\frac12-\epsi)|A_0|$, $|B| \ge \delta |B_0|/(|A_0| + |B_0|)^{\epsi}$, and
  \item $(A,B)$ is complete or anticomplete in $G^d$.
\end{enumerate}
\end{theorem}

We show that the result is tight in a sense that we cannot have both $A$ and $B$
linear in $n$ even for $d=1$, i.e.\ there exists a nowhere dense class without the strong Erd\H{o}s-Hajnal property, see Section~\ref{sec:example}.

TODO: elaborate on the ABS lemma:

\begin{lemma}\label{lem:new-abs}
  Let \(\calC\) be a nowhere dense class of graphs, let \(d\) be an integer and \(\epsi\) be a real with \(d \ge 1\) and \(\epsi > 0\).
  There exists an integer \(n_0\) such that for every \(n\)-vertex graph \(G\)
  with \(n \ge n_0\) and any nonempty subsets \(A\) and \(B\)
  of \(V(G)\), there exist sets \(A'\), \(B'\) and \(S\) with
  \(A' \subseteq A\), \(B' \subseteq B\) and \(S \subseteq V(G)\) such that
  \begin{enumerate}
    \item \(|A'| \ge (1 - \epsi) |A|\), \(|B'| \ge |B|/n^\epsi\),
    \(|S| \le n^\epsi\), and
    \item every \(A'\)--\(B'\) path of length at most \(d\) intersects \(S\).
  \end{enumerate}
\end{lemma}

TODO1: mention that we approach the business via weak coloring numbers\\
TODO2: Organization of the paper.
\end{comment}

config: arxiv


TITLE: Show $(URU^* - \lambda I)^jv = 0 \Rightarrow (R - \lambda I_n)^jU^*v = 0$
QUESTION [1 upvotes]: I don't understand a small step in a proof. Could anyone show me why this is true?
If $U$ is a unitary matrix and $R$ an upper triangle matrix show that for $j \geq 1$:
$$
(URU^* - \lambda I)^jv = 0 \Rightarrow (R - \lambda I_n)^jU^*v = 0.
$$

REPLY [2 votes]: $(URU^*-\lambda I)^jv=(URU^*-\lambda UU^*)^jv=(U(R-\lambda I)U^*)^jv=U(R-\lambda I)^jU^*v$
Added
In fact, $UABU^*=(UAU^*)(UBU^*)$, therefore $(UAU^*)^n=UA^nU^*$


TITLE: Integration of Rational function contain even power of variable $\int\frac{1}{1+x^6}dx$
QUESTION [0 upvotes]: Evaluation of $\displaystyle \int\frac{1}{1+x^6}dx$

$\bf{My\; Try::}$Let $$I = \int\frac{1}{1+x^6}dx = \int\frac{1}{(1+x^2)(x^4-x^2+1)}dx$$
Using Partial fraction , above Integral is very lengthy, Can we solve it without using
partial fraction or any other way, Help me
Thanks

REPLY [2 votes]: $$\displaystyle \int\frac{1}{1+x^6}dx  = \frac{1}{2}\int\frac{\left(1+x^4\right)+\left(1-x^4\right)}{1+x^6}dx$$
$$\displaystyle  = \frac{1}{2}\int\frac{1+x^4}{1+x^6}dx+\frac{1}{2}\int\frac{1-x^4}{1+x^6}dx$$
Now we will take $\displaystyle I = \frac{1}{2}\int\frac{1+x^4}{1+x^6}dx$ and $\displaystyle J = \frac{1}{2}\int\frac{1-x^4}{1+x^6}dx$
So first we will calculate value of $I$
So $$\displaystyle I = \frac{1}{2}\int\frac{1+x^4}{1+x^6}dx = \frac{1}{2}\int\frac{(x^2+1)^2-2x^2}{1+x^6}dx$$
So $$\displaystyle I = \frac{1}{2}\int\frac{(x^2+1)^2}{(1+x^2)\cdot (x^4-x^2+1)}dx - \int\frac{x^2}{1+(x^3)^2}dx$$
So $$\displaystyle = \frac{1}{2}\int\frac{x^2+1}{x^4-x^2+1}-\int\frac{x^2}{1+(x^3)^2}dx$$
So $$\displaystyle  = \frac{1}{2}\int \frac{\left(1+\frac{1}{x^2}\right)}{\left(x-\frac{1}{x}\right)^2+1^2}-\int \frac{x^2}{1+(x^3)^2}dx$$
Now Let $\displaystyle \left(x-\frac{1}{x}\right) = t \Leftrightarrow \left(1+\frac{1}{x^2}\right)dx = dt$ and $x^3 = u\Leftrightarrow 3x^2dx = du\displaystyle \Leftrightarrow dx = \frac{1}{3}du$
So $$\displaystyle I = \frac{1}{2}\cdot \tan^{-1}\left(x-\frac{1}{x}\right) - \frac{1}{3}\cdot \tan^{-1}\left(x^3\right)+\mathcal{C'}$$
Similarly we will calculate for $$\displaystyle J = \frac{1}{2}\int\frac{1-x^4}{1+x^6}dx$$
So $$\displaystyle J = \frac{1}{2}\int\frac{(1-x^2)\cdot (1+x^2)}{(1+x^2)\cdot (x^4-x^2+1)}dx = -\frac{1}{2}\int\frac{x^2-1}{x^4-x^2+1}dx$$
$$\displaystyle J = -\frac{1}{2}\int \frac{\left(1-\frac{1}{x^2}\right)}{\left(x+\frac{1}{x}\right)^2+\left(\sqrt{3}\right)^2}dx$$
Now Now Let $\displaystyle \left(x+\frac{1}{x}\right) = v \Leftrightarrow \left(1-\frac{1}{x^2}\right)dx = dv$
So $$\displaystyle J = -\frac{1}{2}\cdot \frac{1}{2\sqrt 3}\cdot \ln \left|\frac{\left(x+\frac{1}{x}\right)-\sqrt{3}}{\left(x+\frac{1}{x}\right)+\sqrt{3}}\right|+\mathcal{C''}$$
So $\displaystyle \int \frac{1}{1+x^6}dx = \frac{1}{2}\cdot \tan^{-1}\left(x-\frac{1}{x}\right) - \frac{1}{3}\cdot \tan^{-1}\left(x^3\right) - \frac{1}{4\sqrt{3}}\cdot \ln \left|\frac{\left(x+\frac{1}{x}\right)-\sqrt{3}}{\left(x+\frac{1}{x}\right)+\sqrt{3}}\right|+\mathcal{C}$


TITLE: General formula for a sum of quadratic sequence
QUESTION [6 upvotes]: I understand that the general formula for a sum of quadratic sequence is :$\displaystyle \sum_{i=1}^n {i^2} = \frac{n(n+1)(2n+1)}{6}$
However, my question is that does $i$ here has to be single term always? Can I still use the formula if I am calculating $\displaystyle \sum_{i=1}^n {(1+i)^2} $ ?
For example, I was trying to calculate $\displaystyle \sum_{i=1}^3 {(2+i)^2} $, and this is what I did

$\displaystyle \frac{(2+n)((2+n)+1)(2(2+n)+1)}{6}$
$\displaystyle \frac{(2+n)(3+n)(2n+5)}{6}$
$\displaystyle \frac{(5)(6)(11)}{6} = 55$

However, the right answer is 50.
I would like to know what is happening here? And why I can't use this formula directly?

REPLY [1 votes]: No, you can't use the original formula directly. If you change what is to be squared, then here is how the formula transforms:
$SUM((a + i)^2) = i(i+1)(2i+1)/6 + a(i^2 + i) + a^2(i)$
In other words:
$f_n = f_o + a(i^2 + i) + a^2(i)$
where $f_n$ is the new formula and $f_o$ is the old formula. The old formula being:
$f_o = i(i+1)(2i+1)/6$


TITLE: Help in finding a function in $L^p$ such that $f*g=||g||_1 f$ with $g\in L^1(\mathbb{R})$ non negative and fixed
QUESTION [3 upvotes]: I consider a non negative function $g\in L^1(\mathbb{R})$.
I want to find a function $f\in L^p(\mathbb{R})$ such that
$$ f*g=||g||_1 \:f ,$$ where $*$ is the convolution.
I would be very thankful if someone could help me finding this function $f$.

REPLY [2 votes]: Albeit not too interesting, $f \equiv 0$ works.
If the space is a probability space, $p \geq 1\,^\dagger$ and $ \|g\|_1 \neq 0$, then $h:= \frac{g}{\|g\|_1}$ is a probability density (let's say of a rnd. var. $X$) and your equation becomes:
$$f * h = f$$
Now if $f$ is a probabilty density of $Y$, then $f*h$ is the PDF of  $X+Y$.
And the above equation says that $X+Y = Y$ with a probability of $1$.
This means that $X = 0$ with a probablity of $1$. So indeed $f=0$ a.e.
$^\dagger$ see stochasticboy321's comment below.


TITLE: Given an interval around each rational number: How to find a real number which is in none of these intervals?
QUESTION [2 upvotes]: There are countable infinite many rational numbers, so it is possible to "count" them: There are many ways to do this; just pick one.
If an order is chosen, there is an $n$th rational number. Each of these numbers is now embedded into an interval $I_n$ which has the width $2^{-n}$. The rational number is exactly in the middle of this interval. Such an interval is created for each rational number.
Is it possible to name a real number which is in none of these intervals (given a ordering for the rational numbers)?
Thank you

REPLY [1 votes]: As mentioned in the comments by @lulu, the total length of the intervals is $$\sum_{n=0}^{\infty} {2^{-n}} = 2$$
So even if those intervals did not overlap at all, there is no way they can cover the whole real line, and there will be uncountable many real numbers to choose from that are not covered by those intervals.
It might seem counter-intuitive that you can have these intervals around the rationals and still not cover all the reals even though the rationals are dense in the reals, so let me write a bit more about that so that it becomes less weird.
The ordering you choose will for most rationals $p/q$ give an index that is at least $q$. So the interval around $p/q$ will generally be smaller than $2^{-q}$ in length.
(Note that this is not rigorous, and that you can construct orderings where this is not true for infinitely many rationals in the ordering, but let's go with it for now just to get a better feel for what is happening.)
Would you always expect to be able to approximate a real that closely by a rational? For example, $355/113$ is a very good approximation to $\pi$, as it is correct to about 6 decimals. That falls far short however of the $2^{-113}$ accuracy that would be required for it to fall within that intervals in this question. That would require 34 decimals of accuracy.
It would be asking a lot for all reals to have an approximation $p/q$ that is accurate to $2^{-q}$. There are in fact numbers that are hard to approximate. These are numbers where there is no approximation $p/q$ that is more than $c/q^2$ away for some constant $c$. So even putting intervals of length $c/q^2$ around rationals $p/q$ is not sufficient to cover all the reals.