text:
\begin{document}
\title{A note on log-concave random graphs}
\author{Alan Frieze\thanks{Research supported in part by NSF Grant DMS1661063} and Tomasz Tkocz\\
Department of Mathematical Sciences,\\
Carnegie Mellon University,\\
Pittsburgh PA15213,\\
U.S.A.}
\maketitle
\begin{abstract}
We establish a threshold for the connectivity of certain random graphs whose (dependent) edges are determined by the uniform distributions on generalized Orlicz balls, crucially using their negative correlation properties. We also show the existence of a unique giant component for such random graphs.
\end{abstract}
\section{Introduction}
Probabilistic combinatorics is today a thriving field bridging the classical area of probability with modern developments in combinatorics. The theory of random graphs, pioneered by Erd\H{o}s-R\'enyi \cite{ErdosRenyi59}, \cite{ErdosRenyi60} has given us numerous insights, surprises and techniques and has been used to count, to establish structural properties and to analyze algorithms. There are by now several texts \cite{B}, \cite{JLR}, \cite{FK} that deal exclusively with the subject. The most heavily studied models being $G_{n,m}$ and $G_{n,p}$. Both have vertex set $[n]$ and in the first we choose $m$ random edges and in the second we include each possible edge independently with probability $p$.

Let $X$ be a random vector in $[0,\infty)^{\binom{n}{2}}$ with a log-concave down-monotone density $f$, that is (i) $\log f$ is concave and (ii) $f(x) \geq f(y)$ if $x \leq y$ (coordinate-wise). For $0 < p < 1$, let $G_{X,p}$ be a random graph with vertices $1,\ldots, n$ and edges determined by $X$: for $1 \leq i < j \leq n$, $\{i,j\}$ is an edge if and only if $X_{\{i,j\}} \leq p$. Such \emph{log-concave random graphs} were introduced by Frieze, Vempala and Vera in \cite{FVV}. For instance, when $X$ is uniform on $[0,1]^{\binom{n}{2}}$, $G_{X,p}$ is the  random graph $G_{n,p}$.
The paper \cite{FVV} introduced a surprising connection between random graphs and convex geometry.

It studied, among other things, the connectivity of $G_{X,p}$ and found a logarithmic gap for the threshold. There is no gap when $G_{X,p}$ is defined by uniform sampling from a ``well-behaved'' regular simplex\footnote{A regular simplex $\set{x\in \R^d:a\cdot x\leq 1}$ for some $a\geq 0$ if $a_i/a_j\leq K$ for some not too large $K$.} and we extend this case to {\em Generalized Orlicz Balls} GOBs: that is sets of the form $\{x \in \R^d: \sum_{i=1}^d f_i(|x_i|) \leq 1\}$ for some nondecreasing lower semicontinuous convex functions $f_1,\ldots,f_d: [0,\infty)\to [0,\infty]$ with $f_i(0) = 0$, which are not identically $0$ or $+\infty$ on $(0,\infty)$.

The key property of Orlicz balls is {\em negative correlation}. We say that a random vector $X$ in $\R^d$ has negatively correlated coordinates if for any disjoint subsets $I$, $J$ of $\{1,\ldots,d\}$ and nonnegative numbers $s_i$, $t_j$, we have
\[
\Pr{\forall i \in I \ |X_i| > s_i, \forall j \in J \ |X_j| > t_j} \leq \Pr{\forall i \in I \ |X_i| > s_i}\Pr{\forall j \in J \ |X_j| > t_j}.
\]
It was shown in \cite{PW2} that this property holds for random vectors uniformly distributed on GOBs (see also \cite{PW1} for a first such result treating two coordinates and \cite{Woj} for a simpler proof of the general result).

{\bf Notation:} Throughout the paper we will let $\s_{\min}$ and $\s_{\max}$ be defined by
$$\sigma_{\min}^2 = \min_{1 \leq i < j \leq n}\E X_{i,j}^2 \qquad \text{and} \qquad \sigma_{\max}^2 = \max_{1 \leq i < j \leq n}\E X_{i,j}^2.$$
Our result concerning connectivity is the following theorem.
\begin{theorem}\label{th1}
Let $X = (X_{i,j})_{1\leq i < j \leq n}$ be a log-concave random vector in $[0,\infty)^{\binom{n}{2}}$ with a down-monotone density and negatively correlated coordinates.
\begin{enumerate}[(a)]
\item For every $\delta \in (0,1)$, there are constants $c_1$ and $c_2$ dependent only on $\delta$ such that for $p < c_1\sigma_{\min}\frac{\log n}{n}$, we have
\[
\Pr{G_{X,p} \textrm{ has isolated vertices}} > 1 - c_2n^{-\delta}.
\]
\item For every $\delta \in (0,1)$, there are constants $C_1$ and $C_2$ dependent only on $\delta$ such that for $p > C_1\sigma_{\max}\frac{\log n}{n}$, we have
\[
\Pr{G_{X,p} \textrm{ is connected }} > 1 - C_2n^{-\delta}.
\]
\end{enumerate}
\end{theorem}
We will also discuss the existence of a giant component for smaller values of $p$.

{\bf Notation:} Let
\begin{equation}\label{eq:def-M}
M = \max_{T}\sup_{y \in [0,\infty)^{|T|}}\max_{(i,j) \notin T} \E(X_{i,j}^2|X_T = y),
\end{equation}
where the first maximum is over all nonempty subsets $T$ of the index set $\{(i,j), \ 1 \leq i < j \leq n\}$ and we denote $X_T = (X_{i,j})_{(i,j) \in T}$.

For our theorem on the existence of a giant component we need to have $M=O(1)$. For a GOB, $\set{x \in \R^{\binom{n}{2}}: \sum_{1\leq i<j\leq n} f_{i,j}(|x_{i,j}|) \leq 1}$, this is justified by the following assumption: we let
$$a_{i,j}=\sup\set{t>0:f_{i,j}(t)\leq 1}.$$
Now our assumptions on the $f_{i,j}$ imply that the $a_{i,j}$'s are finite. Furthermore, $M\leq \max_{i,j}a_{i,j}^2$ and so our assumption here is that $\max_{i,j}a_{i,j}$ is bounded by an absolute constant.
\begin{theorem}\label{th2}
Let $X = (X_{i,j})_{1\leq i < j \leq n}$ be a log-concave random vector in $[0,\infty)^{\binom{n}{2}}$ with a down-monotone density. Assume that

$M=O(1)$.  There are constants $c_1$ and $c_2$ such that for every $\beta > 1$, we have
\begin{enumerate}[(i)]
\item\label{lm:giant-smallp}
If $p < \frac{c_1\sigma_{\min}}{n}$, then
\[
\Pr{G_{X,p} \textrm{ has a component of order } \geq \beta\log n } < \frac{12}{n^{\beta-1}}.\]
\item\label{lm:giant-largep}
If $p > \frac{c_2M\log\left(\frac{M}{\sigma_{\min}}\right)}{n}$, then
\[
\Pr{G_{X,p} \textrm{ has a component of order } \in [\beta\log n,n/2] } < \frac{1}{n^{\beta-1}}
\]
and
\[
\Pr{G_{X,p} \textrm{ has a unique giant component of order } > n/2} > 1 - \frac{5\beta}{\log n}-\frac{1}{n^{\beta-1}}.
\]
\end{enumerate}
\end{theorem}
Note that we have dropped the assumption of negative correlation.
\section{Connectivity: Proof of Theorem \ref{th1}}
\begin{proof}
Part (b) is part of Theorem 2.1 of \cite{FVV}. For (a), we adapt the standard second moment argument used for the Erd\"os-R\'enyi model. For $1 \leq i \leq n$, let $Y_i$ be equal to $1$ if the vertex $i$ is isolated and $0$ otherwise. Let $Y = Y_1 + \ldots + Y_n$ be the number of isolated vertices. We have,
\[
\Pr{G_{X,p} \textrm{ has isolated vertices}}=  \Pr{Y  > 0} \geq \frac{(\E Y)^2}{\E Y^2}.
\]
Thus, if we show that $\E Y^2 \leq (1+\varepsilon)(\E Y)^2$, then $\Pr{Y > 0} \geq 1 - \varepsilon$. Clearly,
\[
\E Y^2 = \sum_{k} \E Y_k^2 + \sum_{k \neq l} \E Y_k Y_l = \sum_k \E Y_k + \sum_{k \neq l} \Pr{Y_k = 1 = Y_l} = \E Y + \sum_{k \neq l} \Pr{Y_k = 1 = Y_l}
\]
and our goal is to show that
\[
\E Y \leq \frac{\varepsilon}{2}(\E Y)^2 \qquad \text{and} \qquad \sum_{k \neq l} \Pr{Y_k = 1 = Y_l} \leq \left(1+\frac{\varepsilon}{2}\right)(\E Y)^2.
\]
From the negative correlation of coordinates of $X$ as well as an elementary inequality $\Pr{A} \leq \Pr{A\cap B} + 1 - \Pr{B}$, we get
\begin{align*}
\Pr{Y_k=1=Y_l} &= \Pr{\forall i \neq k \ X_{ik} > p, X_{il} > p, X_{kl} > p} \\
&\leq \Pr{\forall i \neq k \ X_{ik} > p}\Pr{\forall i\neq k,l \ X_{il} > p} \\
&\leq \Pr{\forall i \neq k \ X_{ik} > p}\big[ \Pr{\forall i\neq l \ X_{il} > p} + 1 - \Pr{X_{kl} > p} \big] \\
&= \Pr{Y_k = 1}\big[ \Pr{Y_l = 1} + \Pr{X_{kl} \leq p} \big].
\end{align*}
By Lemma 3.5 from \cite{FVV}, $\Pr{X_{kl} \leq p} \leq \frac{p}{\sigma_{\min}}$ (recall that by the Pr\'ekopa-Leindler inequality, marginals of log-concave vectors are log-concave; clearly, marginals of down-monotone densities are down-monotone). Therefore,
\begin{align*}
\sum_{k \neq l} \Pr{Y_k = 1 = Y_l} &\leq \sum_{k \neq l} \Pr{Y_k = 1}\Pr{Y_l =1} + \sum_{k\neq l} \Pr{Y_k = 1}\frac{p}{\sigma_{\min}} \\
&\leq \left(\sum_{k} \Pr{Y_k=1}\right)^2 + \frac{np}{\sigma_{\min}}\sum_{k} \Pr{Y_k = 1} \\
&\leq \left(1 + \frac{np}{\sigma_{\min}\E Y}\right)(\E Y)^2  < \left(1 + \frac{c_1\log n}{\E Y}\right)(\E Y)^2,
\end{align*}
so it suffices to take $\varepsilon$ such that
\[
\varepsilon \geq \frac{2}{\E Y} \qquad \text{and} \qquad \varepsilon \geq \frac{2c_1\log n}{\E Y}.
\]
By Lemma 3.1 from \cite{FVV}, $\Pr{Y_k = 1} \geq e^{-a p n /\sigma_{\min} }$, for some universal constant $a$ (the assumption $p < \frac{1}{4}\sigma_{\min}$ of that lemma is clearly satisfied if $p < c_1\sigma_{\min}\frac{\log n}{n}$), so
\[
\E Y = \sum_k \Pr{Y_k = 1} \geq ne^{-a p n /\sigma_{\min} } > n^{1-ac_1}.
\]
Thus, $\varepsilon = c_2n^{ac_1-1}\log n$ will suffice.
\end{proof}

\section{Giant Component: Proof of Theorem \ref{th2}}
\begin{lemma}\label{lm:inout-edge-uppbd}
Let $X = (X_{i,j})_{1\leq i < j \leq n}$ be a log-concave random vector in $[0,\infty)^{\binom{n}{2}}$ with a down-monotone density. There are universal constants $a$ and $b$ such that for $S, T \subset \{(i,j), \ 1 \leq i < j \leq n\}$ and $p > 0$, we have
\[
\Pr{\forall s \in S \ X_s > p, \forall t \in T \ X_t \leq p} \leq e^{-ap|S|/M}\left(\frac{bp}{\sigma_{\min}}\right)^{|T|}.
\]
\end{lemma}
\begin{proof}
Fix disjoint sets $S, T \subset \{(i,j), \ 1 \leq i < j \leq n\}$ (if they are not disjoint, the probability in question is $0$) and $y \in [0,\infty)^{|T|}$. Let $f$ be the density of $(X_S,X_T)$. The conditional density of the vector $X_S$ given $X_T = y$,
\[
f_{X_S|X_T}(x|y) = \frac{f(x,y)}{\int f(x',y)\dd x'}
\]
is down-monotone and log-concave. Therefore, by Lemma 3.1 from \cite{FVV},
\[
\Pr{\forall s \in S \ X_s > p| X_T=y} \leq e^{-ap|S|/M}.
\]
We denote the density of $X_T$ by $f_{X_T}$ and get
\begin{align*}
\Pr{\forall s \in S \ X_s > p, \forall t \in T \ X_t \leq p} &= \int_{[0,p]^{|T|}} \Pr{\forall s \in S \ X_s > p | X_T = y} f_{X_T}(y) \dd y \\
&\leq \int_{[0,p]^{|T|}}e^{-ap|S|/M} f_{X_T}(y) \dd y \\
&= e^{-ap|S|/M}\Pr{\forall t \in T \ X_t \leq p}\\
&\leq e^{-ap|S|/M}\left(\frac{bp}{\sigma_{\min}}\right)^{|T|},
\end{align*}
where the final inequality follows directly from Lemma 3.2 of \cite{FVV}.
\end{proof}

With this lemma in hand, we can prove Theorem \ref{th2}.
\begin{proof}
Let $Z_k$ be the number of components of order $k$ (that is, on $k$ vertices) in $G_{X,p}$. As for the Erd\"os-R\'enyi model, looking at a spanning tree for each component and bounding the corresponding in-out edge probabilities using Lemma \ref{lm:inout-edge-uppbd} yields
\begin{align*}
\E Z_k &\leq \binom{n}{k}k^{k-2}e^{-apk(n-k)/M}\left(\frac{bp}{\sigma_{\min}}\right)^{k-1} \\
&\leq \left(\frac{en}{k}\right)^kk^{k-2}e^{-apk(n-k)/M}\left(\frac{bp}{\sigma_{\min}}\right)^{k-1} \\
&=\frac{\sigma_{\min}}{bp}\frac{1}{k^2}\left[\frac{eb}{\sigma_{\min}}pne^{-\frac{ap}{M}(n-k)}\right]^k.
\end{align*}
If $p = \frac{M}{a}\frac{c}{n}$, with $c$ being a constant (chosen soon), this becomes
\[
\E Z_k \leq \frac{e}{A}\frac{1}{c}\frac{n}{k^2}\left[Ace^{-c}e^{ck/n}\right]^k,
\]
where we put $A = \frac{eb}{a}\frac{M}{\sigma_{\min}}$.

\bigskip
\emph{Case 1.}
If $c$ is a small constant, say $c \leq \frac{1}{eA}$ (equivalently, $p \leq \frac{\sigma_{\min}}{e^2b}\frac{1}{n}$), then we bound $e^{-c}e^{ck/n}$ crudely by $1$ and get that
\[
\E Z_k \leq \frac{e}{A}\frac{1}{c}\frac{n}{k^2}(Ac)^{k} \leq en(Ac)^{k-1} \leq e^2ne^{-k}.
\]
Thus,
\[
\E \left(\sum_{k \geq \beta \log n} Z_k \right) \leq e^2n\cdot \sum_{k \geq \beta \log n}e^{-k} \leq e^2ne^{-\beta\log n}\frac{1}{1 - e^{-1}} = \frac{e^3}{e-1}\frac{1}{n^{\beta-1}} < \frac{12}{n^{\beta-1}}.
\]
By the first moment method, this gives \eqref{lm:giant-smallp}.

\bigskip\noindent
\emph{Case 2.}
Let $c$ be a large constant, say such that $Ace^{-c/2} \leq \frac{1}{e}$ and $Ac \geq e^2$, which holds when, say $c \geq 4\log A$, provided that $A$ is large enough, which leads to the assumption on $p$ in \eqref{lm:giant-largep}. Then for $k \leq n/2$, we have
\[
\E Z_k \leq \frac{en}{Ac} (Ace^{-c/2})^k \leq ne^{-k-1}.
\]
Thus,
\[
\E \left(\sum_{\beta \log n \leq k \leq n/2 } Z_k \right) \leq ne^{-1}\sum_{k \geq \beta \log n} e^{-k} \leq \frac{1}{e-1}\frac{1}{n^{\beta-1}} < \frac{1}{n^{\beta-1}}.
\]
By the first moment method, this gives the first part of \eqref{lm:giant-largep}.

To go about the second part and show that there is a giant component, we shall simply count the number of vertices on the small components and show that with high probability, there are strictly less $n$ such vertices. The uniqueness of a giant component plainly follows from the fact that it has more than $n/2$ vertices, so there cannot be more than one such components. Fix $1 \leq k \leq \beta\log n$ and set $t = ne^{-k-1}$. For any positive integer $l \leq et+1$, we have
\begin{align*}
\Pr{Z_k \geq et} &\leq \Pr{Z_k(Z_k-1)\ldots(Z_k-l+1) \geq et(et-1)\ldots(et-l+1) } \\
&\leq \frac{\E Z_k(Z_k-1)\ldots(Z_k-l+1)}{et(et-1)\ldots(et-l+1)} \\
&\leq
\frac{\E Z_k(Z_k-1)\ldots(Z_k-l+1)}{(et-l+1)^l}.
\end{align*}
As for the upper bound for $\E Z_k$, looking at spanning trees for each $l$-tuple of distinct components of order $k$ and bounding the corresponding in-out edge probabilities using Lemma \ref{lm:inout-edge-uppbd} yields
\begin{align*}
\E Z_k&(Z_k-1)\ldots(Z_k-l+1) \\
&\leq \binom{n}{k}\binom{n-k}{k}\ldots\binom{n-(m-1)k}{k}(k^{k-2})^le^{-\frac{ap}{M}kl(n-kl)}\left(\frac{bp}{\sigma_{\min}}\right)^{(k-1)l} \\
&\leq \left(\frac{en}{k}\right)^{kl}(k^{k-2})^le^{-\frac{ap}{M}kl(n-kl)}\left(\frac{bp}{\sigma_{\min}}\right)^{(k-1)l} \\
&= \left(\frac{e}{A}\frac{1}{c}\frac{n}{k^2}\left[Ace^{-c}e^{ckl/n}\right]^k\right)^l.
\end{align*}
Provided that $kl \leq n/2$, under our assumption $c\geq 4\log A$, this is further upper bounded by $(t/k^2)^l$, which gives
\[
\Pr{Z_k \geq ne^{-k}} = \Pr{Z_k \geq et} \leq \frac{1}{k^{2l}}\left(\frac{t}{et-l+1}\right)^l.
\]
For $k \geq \frac{1}{2}\log n$, we choose $l = 1$ and get
\[
\Pr{Z_k \geq ne^{-k}} \leq \frac{1}{e}\frac{1}{(\frac{1}{2}\log n)^2}, \qquad k \geq \frac{1}{2}\log n.
\]
For $k < \frac{1}{2}\log n$, we have $t = ne^{-k-1} > e^{-1}\sqrt{n}$, so choosing, say $l - 1 = \lfloor e^{-1}\sqrt{n} \rfloor$ yields
\begin{align*}
\Pr{Z_k \geq ne^{-k}} \leq \left(\frac{t}{et-\lfloor e^{-1}\sqrt{n} \rfloor}\right)^l = \left(\frac{1}{e-\frac{\lfloor e^{-1}\sqrt{n} \rfloor}{t}}\right)^l &\leq \left(\frac{1}{e-1}\right)^{l} \\
&\leq \left(\frac{1}{e-1}\right)^{e^{-1}\sqrt{n}}, \qquad k < \frac{1}{2}\log n.
\end{align*}
Combining the last two estimates, the union bound gives that the probability of the event $E = \{\exists k \leq \beta\log n, \ Z_k \geq ne^{-k}\}$ is at most
\[
\frac{4}{e}\frac{(\beta-1/2)\log n+1}{(\log n)^2} + \frac{\frac{1}{2}\log n}{(e-1)^{e^{-1}\sqrt{n}}} < \frac{5\beta}{\log n}
\]
(we check that $ \frac{\frac{1}{2}\log n}{(e-1)^{e^{-1}\sqrt{n}}} < \frac{2}{\log n}$ and simply bound $\frac{4}{e}\frac{(\beta-1/2)\log n+1}{(\log n)^2} \leq \frac{\frac{4}{e}\beta+\frac{2}{e}}{\log n}$). To finish, it remains to check that on $E^c$, there are few vertices on the small components. On $E^c$, we have
\[
\sum_{k \leq \beta \log n} kZ_k \leq n\sum_{k \leq \beta \log n} ke^{-k} < n \sum_{k=1}^\infty ke^{-k} =n\frac{e}{(e-1)^2} < 0.93n.
\]
\end{proof}

\begin{remark}\label{rem:moregen}
It was shown in \cite{Woj} that the negative correlation property holds in fact for random vectors with densities of the form $h(\sum f_i(x_i))$, where $h:[0,\infty)\to[0,\infty)$ is a nonincreasing log-concave function ($h = \1_{[0,1]}$ giving uniform densities on GOBs). For such densities, $M$ is finite and can be bounded as for GOBs in terms of certain parameters depending on the functions $f_i$ and $h$.
\end{remark}

\section{Conclusion and Open Questions}
We have successfully generalised the results on the regular simplex in \cite{FVV} to GOBs. The following questions seem most apposite.
\begin{enumerate}[{\bf Q1}]
\item What we prove in Theorem \ref{th2} does not rule out the possibility that in some range of $p$ there is more than one giant component. Can the proof be tightened to rule this out?
\item What is the connectivity or giant component threshold for the intersection of two well-behaved regular simplices?
\item What is the connectivity or giant component threshold for the intersection of a {\em few} regular simplices with independent randomly chosen coefficients?
\end{enumerate}

config: arxiv


TITLE: Integral of $\frac1{\cos x}$ using t substitution
QUESTION [5 upvotes]: Okay, so I'm trying to find $ \int \frac1{\cos x}\mathrm{d}x$ using the substitution $t = \tan\left(\frac{x}{2}\right)$.
I sub in the trig identity for $\sec$ as $\frac{1+t^2}{1-t^2}$ and then rearrange and substitute $\frac{\mathrm{d}t}{\mathrm{d}x} = \frac12 \left(1+ \tan^2\left(\frac{x}{2}\right)\right)$ so I am left with
$\frac2{1-t^2}$
I then used partial fractions to find
$\frac2{1-t^2} = \frac1{1+t} + \frac1{1-t}$
and therefore integrating I get
$\int \frac1{\cos x}dx = \ln(t+1) - \ln(t-1)$
But subbing in $t = \tan\left(\frac{x}{2}\right)$ doesn't seem to get me anywhere close to the solution that I want to find, which is:
$ \int \frac1{\cos x}\mathrm{d}x = \ln(\sec x + \tan x) + C$
Any help on this would be greatly appreciated.
Thanks!

REPLY [0 votes]: We know that $$\cos x=\frac{1-\tan^{2}\frac{x}{2}}{1+\tan^{2}\frac{x}{2} }=\frac{1-\tan^{2}\frac{x}{2}}{\sec^2 \frac{x}{2} }$$ Given that $$\int \frac{1}{\cos x}dx$$$$=\int \frac{1}{\frac{1-\tan^{2}\frac{x}{2}}{\sec^2 \frac{x}{2}  }}dx$$ $$=\int \frac{\sec^2 \frac{x}{2}}{1- \tan^{2}\frac{x}{2}}dx$$ Let $$\tan \frac{x}{2}=t \implies \frac{1}{2}\sec^2\frac{x}{2}dx=dt \implies \sec^2\frac{x}{2}dx=2dt $$ Now , we have $$\int \frac{\sec^2 \frac{x}{2}}{1- \tan^{2}\frac{x}{2}}dx=\int \frac{2dt}{1- t^2}$$$$=\frac{2}{2}\ln\left|\frac{1+t}{1-t}\right|$$
$$=\ln\left|\frac{1+\tan \frac{x}{2}}{1-\tan \frac{x}{2}}\right|$$
$$=\ln\left|\frac{\cos \frac{x}{2}+\sin \frac{x}{2}}{\cos \frac{x}{2}-\sin \frac{x}{2}}\right|$$
$$=\ln\left|\frac{\left(\cos \frac{x}{2}+\sin \frac{x}{2}\right)\left(\cos \frac{x}{2}+\sin \frac{x}{2}\right)}{\left(\cos \frac{x}{2}-\sin \frac{x}{2}\right)\left(\cos \frac{x}{2}+\sin \frac{x}{2}\right)}\right|$$
$$=\ln\left|\frac{\cos^2\frac{x}{2}+\sin^2\frac{x}{2}+2\sin\frac{x}{2}\cos\frac{x}{2}}{\cos^2 \frac{x}{2}-\sin^2 \frac{x}{2}}\right|$$
$$=\ln\left|\frac{1+\sin x}{\cos x}\right|$$
$$\color{blue}{=\ln\left|\sec x+\tan x\right|+C}$$


TITLE: Why is this the answer?
QUESTION [4 upvotes]: A fair coin is tossed $n$ times by Adam and $n$ times by Andrew. What is the probability that they get the same number of heads?
Now since there are a total of $2n$ flips, $n$ from each person, we would need to choose $k$ flips that they both have heads correct? So since this is a binomial$\sim (2n,\frac12)$ I came to find that we have $${2n \choose k }\left(\frac12\right)^{2n}$$ However my textbook says it differently. I'm wondering why the book says it is:  $${2n \choose n }\left(\frac12\right)^{2n}$$ Is it the same thing? I'm just confused as to why it would say choose $n$. Should I be assuming assume that half of the total flips are are going to be the same?

REPLY [10 votes]: The following solution has a minimal amount of computation, but may require some concentration.
Call our two players Alicia and Beti. They get the same number of heads iff for some $k$, they each get $k$ heads.
The probability that Beti gets $k$ heads is the same as the probability Beti gets $k$ tails, so it is the same as the probability  that Beti gets $n-k$ heads.
So the probability they get the same number of heads is the same as the probability that between them they get a total of $n$ heads.
The probability that when we toss a coin $2n$ times we get $n$ heads is
$$\binom{2n}{n}\frac{1}{2^{2n}}.$$


TITLE: Proving an implicit equation has no orbits
QUESTION [0 upvotes]: Suppose we have the function $F(x,y)=x+y-a\log(x)$ where a is a constant and define the orbit by the implicit equation $F(x,y)=c$ where c is a constant. How can I formally prove that no orbit reaches the $y$-axis?
I can sketch the some level curves of this, but still I want to know if this is something that can be proven formally?
Thanks in advance!

REPLY [1 votes]: $F(x,y)$ is not defined when $x=0$.  So if an "orbit" is defined as the set of solutions of $F(x,y)=c$, it can't contain any point of the $y$ axis.
EDIT: Ah, so what's really going on here is that  $F(x,y) = c$ is an implicit
form for the trajectories of a system of differential equations: those are the "orbits".  You should have mentioned that in the first place.
Well, not only does the solution set of $F(x,y) = c$ not contain any point of the $y$ axis, it also has no limit points on the $y$ axis if $a\ne 0$, because $\lim_{x \to 0+} \log(x) = -\infty$.


TITLE: Homology group of $(X,X)$
QUESTION [0 upvotes]: Let $H$ be a homology theory.
I want to show that $H(X,X) = 0 \; \forall p\in\Bbb Z$. Maybe someone can tell me whether my reasoning is correct.
From the exactness axiom I get a long exact sequence:
$$... \xrightarrow{\text{$\partial_*$}} H_p(X) \xrightarrow{\text{$i_*$}} H_p(X) \xrightarrow{\text{$j_*$}} H_p(X,X)  \xrightarrow{\text{$\partial_*$}}...$$
where $i_*$ is the map induced by the inclusion (identity in this case) $i:X\rightarrow X$. Therefore $i_* = id_*:H_p(X) \rightarrow H_p(X)$.
$j_*$ is induced by $id:X\rightarrow (X,X)$. Therefore $j_* = id_*$. Since this is a LES we have that $im(i_*)=ker(j_*)$, but $im(i_*)=H_p(X)$ and therefore $j_*$ sends everything to $0$. But $j_*$ is also the identity.
$\Rightarrow H_p(X,X) = 0$

REPLY [2 votes]: Too much work!
By definition the chain complex $C_*(X,A)$ is, degreewise, the quotient $C_q(X)/C_q(A)$.
So $C_q(X,X) = C_q(X)/C_q(X) = 0$. Therefore the chain complex $C_*(X,X)$ is zero in every degree. Therefore its homology is zero.


TITLE: Prove: $\sum \limits_{n=1}^{\infty}((n+\frac{x}{n})\ln(1+\frac{x}{n})-x)$ for $x \in [0,a]$ uniformly converges
QUESTION [3 upvotes]: I'd like your help with proving that following sum uniformly converges:
$$\sum_{n=1}^{\infty}\left(\left(n+\frac{x}{n}\right)\ln\left(1+\frac{x}{n}\right)-x\right)$$ for $x \in [0,a]$.
I tried to use the theorem saying that if there's one point (in our case $x=0$), which the series pointwise converges, and the  sum  of $U'_n$ converges also, the original sum uniformly converges, but it didn't work for me here.
Any hints?
Thanks a lot!

REPLY [4 votes]: The series does not converge if $x\ne0$. Using the Taylor expansion
$$
\ln(1+t)=t-\frac{t^2}{2}+\cdots
$$
we see that
$$
\Bigl(n+\frac{x}{n}\Bigr)\ln\Bigl(1+\frac{x}{n}\Bigr)-x=-\frac{x^2}{2\,n}+O\Bigl(\frac{1}{n^2}\Bigr)
$$
where the $O$ term is uniform in $x\in[\,0,a\,]$.


TITLE: Prove that Every element in $F(c)$ can be written as $r(c)$ for some $r(x)$ of degree $< n$ in $F[x]$.
QUESTION [2 upvotes]: Let $p(x)$ be an irreducible polynomial of degree $n$ over $F$. Let c denote a root of $p(x)$ in some extension of F. Prove that Every element in $F(c)$ can be written as $r(c)$ for some $r(x)$ of degree $< n$ in $F[x]$.
Note: $F(c)$ is the range of $\sigma _c$ = the substitution function
Here's what I have so far:
For some element $t(c) \in F(c)$, divide it by $p(x)$. So, by the division algorithm, $t(x) = p(x)q(x) + r(x)$, with $\mbox{degree } r(x) < \mbox{degree } p(x) = n$. But I am stuck on how to continue.. Since $c$ is a root of $p(x) \mbox{ then } p(c) = 0$ and thus $t(c) = r(c)$

REPLY [3 votes]: Since $p(x)$ is irreducible $(p(x))\subseteq F[x]$ is maximal, so $F[x]/(p(x))$ is a field containing a root of $p$. But $F(c)$ is a minimal such field, so there is an injection $F(c)\to F[x]/(p(x))\cong F[c]$ (see note below). But then clearly $F[c]\subseteq F(c)$ so equality holds.

The isomorphism is given by the first isomorphism theorem and the surjection

$$\begin{cases} F[x]\to F[c] \\ p(x)\mapsto p(c)\end{cases}.$$

REPLY [1 votes]: $p(c)=0$ helps because then $t(x) = p(x)q(x) + r(x)$ implies $t(c)=r(c)$, as needed.
But you need to argue that $F(c)=F[c]$ first.


TITLE: Tropical version of exchange relations in cluster algebras
QUESTION [0 upvotes]: The exchange relation in a cluster algebra is
\begin{align}
x_k' = \frac{1}{x_k} (\prod_{j \to k}x_j + \prod_{k \to j} x_j).
\end{align}
Do we have some tropical version of this relation? Are there some references? Thank you very much.

REPLY [1 votes]: In the paper, the formula (2.4) gives a tropical version of mutation relations:
\begin{align}
a_k' = \max( \sum_i a_i[b_{ki}]_+, \sum_i a_i [-b_{ki}]_+ )-a_k.
\end{align}


TITLE: Prove that there are no integer solutions x,y to the following system of equations using mod 4 arithmetic:
QUESTION [0 upvotes]: So i was given a question stated in the title and I have to show this for
A)$2x+7y=3$
B)$3x+ 8y = 3$
C)$4x + 9y = 5$
I understand how to use the linear diophantine equation to solve these questions but what confuses me is the "using the mod 4 arithmetic" in the question. What exactly does that mean and how would you do it?

REPLY [0 votes]: If you have a system of equations it implies more than one equation and that you are supposed to find a solution that satisfies all of them simultaneously. I presume the system consists of those three equations, not that you are supposed to "show this for" each of them individually.
What they mean is to reduce both sides modulo $4$ and see what it gives.
$2x + 3y \equiv 3 \pmod{4}$.
$3x \equiv 3 \pmod{4}$.
$y \equiv 1 \pmod{4}$.
You can easily check that $x \equiv 1 \pmod{4}$ based on the second equation but that and the third equation contradict the first.


text:
\section{Editing Algorithms}
\label{section:positive_results}

\ifdefined\islocalratio
    \subsection{Degeneracy: Density-Based Bicriteria Approximation}
    \label{section:positive_degeneracy_localratio}
    \input{./positive_results/degeneracy_localratio.tex}
\fi

\ifdefined\islp
    \subsection{Degeneracy: LP-based Bicriteria Approximation}
    \label{section:positive_degeneracy_lp}
    \input{./positive_results/degeneracy_lp.tex}
\fi

\ifdefined\isgreedy
    \subsection{Degeneracy: $O(\log n)$ Greedy Approximation}
    \label{section:positive_degeneracy_one}
    \input{./positive_results/degen-by-one.tex}
\fi

\ifdefined\istwappx
    \subsection{Treewidth/Pathwidth: Bicriteria Approximation for Vertex Editing}\label{section:positive_treewidth}
    \input{./positive_results/treewidth.tex}
\fi

\ifdefined\isbde
	\subsection{Bounded Degree: Polynomial Time Algorithm for Edge Editing}
	\label{section:bounded_degree_edge_edit}
 	\input{./positive_results/BDEalg.tex}
\fi

\ifdefined\isstarforest
    \subsection{Treedepth 2: $O(1)$-approximation for Editing}
    \label{section:positive_starforest}
    \input{./positive_results/starforest.tex}
\fi


TITLE: Find integral given volume
QUESTION [1 upvotes]: I need to find the integral of the function $F(x,y,z) = z$ in the region $E$ that is top half of a sphere of $r=2$. So $z \geq{0}$ and $x^2+y^2+z^2\leq{4}$. I found the volume to be $\int_{0}^{2\pi}\int_{0}^{2}\int_{0}^{\sqrt{4-r^{2}}}rdzdrd\theta = \frac{16\pi}{3}$, but I do not know what to do next.
$\overline{z}=\frac{1}{V}\int\int\int_{E}zdV$ is what I'm looking for. Any help is appreciated!

REPLY [1 votes]: Take a point $P(x,y,z)$ on sphere. Suppose $\phi$ is the angle which line $OP$ makes with $z-$ axis and $\theta$ is the angle on $xy-$ plane.
Then with polar coordinates  $P(rsin\phi cos\theta, rsin\phi sin\theta, rcos\phi)$; where $0<r<2, 0<\theta <2π, 0<\phi<π/2$ and $\lvert\frac{\partial(x,y,z)}{\partial(r,\theta,\phi)}\rvert=r^2 sin\phi$
$V=\int_0^{π/2}\int_0^{2π}\int_0^2 r^2 sin\phi dr d\theta d\phi$
$\implies V=\int_0^{π/2}sin\phi d\phi\times\int_0^{2π}d\theta\times \int_0^2 r^2 dr$
$=1\times 2π\times \frac{8}{3}=16\frac{π}{3}$


TITLE: The evaluation map on twists of a vector bundle and an induced filtration
QUESTION [3 upvotes]: The following question arose while thinking about a step in the proof of Huybrechts-Lehn, Theorem 1.3.1 (the Harder-Narasimhan filtration for the projective line $\mathbb{P}^{1}$):
Setup: Let $k$ be a field, let $X$ be a projective $k$-scheme, let $\mathcal{O}_{X}(1)$ be a fixed very ample line bundle on $X$, let $E$ be a vector bundle on $X$. For an integer $b \in \mathbb{Z}$, let $\mathrm{ev}_{E(b)} : \mathrm{H}^{0}(X,E(b)) \otimes_{k} \mathcal{O}_{X} \to E(b)$ be the evaluation map and let $E_{b} \subseteq E$ be the image of the twist $\mathrm{ev}_{E(b)}(-b) : \mathrm{H}^{0}(X,E(b)) \otimes_{k} \mathcal{O}_{X}(-b) \to E$.
Question: Why is $E_{b} \subset E_{b+1}$?
(And does this inclusion depend on a choice of global section $s \in \Gamma(X,\mathcal{O}_{X}(1))$?)
Remark: Note that $\mathrm{Hom}_{\mathcal{O}_{X}}(\mathcal{O}_{X}(-b),\mathcal{O}_{X}(-b-1)) = 0$ so there is no map $\varphi : \mathrm{H}^{0}(X,E(b)) \otimes_{k} \mathcal{O}_{X}(-b) \to \mathrm{H}^{0}(X,E(b+1)) \otimes_{k} \mathcal{O}_{X}(-b-1)$ satisfying $\mathrm{ev}_{E(b+1)}(-b-1) \circ \varphi = \mathrm{ev}_{E(b)}(-b)$.

REPLY [6 votes]: There is a commutative diagram
$$\require{AMScd}
\begin{CD}
H^0(E(b)) \otimes H^0(\mathcal{O}(1)) \otimes \mathcal{O}(-b-1)
@>{\mathrm{ev}_{\mathcal{O}(1)}}>>
H^0(E(b)) \otimes \mathcal{O}(-b)
\\
@VVV @V{\mathrm{ev}_{E(b)}}VV
\\
H^0(E(b+1)) \otimes \mathcal{O}(-b-1)
@>{\mathrm{ev}_{E(b+1)}}>>
E
\end{CD}
$$
where the left vertical arrow is the multiplication of global sections. The top arrow is surjective (because $\mathcal{O}(1)$ is very ample), hence the composition of the top and right arrows has image $E_b$. By commutativitity of the diagram it is contained (canonically) in the image $E_{b+1}$ of the bottom arrow.


TITLE: Does the isotropic group of local galois representation have finite index?
QUESTION [2 upvotes]: Let $\rho : G\to \mathrm{GL}_n(\mathbb Z_p)$ be a crystalline representation of $G=\mathrm{Gal}(\bar{\mathbb{Q}}_p/\mathbb{Q}_p)$.  For any non zero element $a\in \mathbb{Z}_p^n$ , it spans a rank one $\mathbb{Z}_p$-submodule $L_a$. Now consider the subgroup $H$ of $G$, $H=\{g\in G| g(L_a)\subset L_a\}$.  Does  $H$   have finite index in $G$, i.e .$[G:H]< \infty$?

REPLY [4 votes]: If $\rho$ is a representation with this property, then by taking $a$ to run through a basis of $\mathbf{Z}_p^n$ and intersecting the corresponding $H$'s, there must be a finite-index subgroup of $G$ whose image under $\rho$ is diagonal. Most crystalline representations will not have this property. There are even unramified representations that are not of this form, e.g. the one mapping Frobenius to $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$.


TITLE: Unit-counit adjunction intuition
QUESTION [10 upvotes]: Do you have a particular intuition or example you keep in your head when you think about the unit-counit adjunction? At this point, writing
$$R(\epsilon_c)\circ \eta_{R(c)} = \text{Id}_{R(c)}$$
$$\epsilon_{L(d)} \circ L(\eta_{d}) = \text{Id}_{L(d)}$$
just feels like symbolic manipulation to me. (Here we have $R:C \to D$ right adjoint to $L:D \to C$, and $c \in |C|$ and $d \in |D|$.)
Obviously there are many examples of adjoint functors. Looking for an clarifying and/or easy to remember example of how the unit and counit work together as above.

REPLY [0 votes]: Think in terms of identity.
Let me reference an object by two modalities, say |#> and |b>, with operators defined as

|#|sharp
|b| flat

and unit defined by

|#b| = 1 = |b#|

Now, to identify each object, let us create a round-trip path built form each objects unique spelling: we take a sharp path and immediately a flat path in the first object and we take a flat path and a immediately a sharp path in the second :

|#> = |b#| |#> = 1 |#>
|b> = |#b| |b> = 1 |b>.

Both of these are maps from the object back to itself, and thus should represent an identity, but we see that creating paths using our adjoint operators does not create a unique identity that separates objects created exclusively in one modality as opposed to the other.
But watch what happends when be bifurcate the original unit definition to include a counit

|#b| = 1$_f$.
|b#| = 1$_s$.

Now our objects unique round-trip path truly is unique for each object and can thus truly represent a unique identity:

|#> = |b#| |#> = $1_s$ |#>
|b> = |#b| |b> = $1_ f$ |b>.

(BTW, if I'm not mistaken, the first definition of our unit as self-dual corresponds to a monoidal interpretation for our space of study while our unit/counit definition corresponds to a group interpretation for our space)


TITLE: Hexagon Complex Number Geometry
QUESTION [1 upvotes]: The diagonals $AC$ and $CE$ of the regular hexagon ABCDEF are divided by the inner points M and
N, respectively, so that $AM/AC =CN/CE = r$. Determine $r$ if $B, M,$ and $N$ are collinear.
The process to do this by coordinates is very tedious. Does anyone know how to do this with the use of complex number geometry specifically?

REPLY [0 votes]: Consider the complex plane, let $\omega = e^{\pi/3}$ be an elementary sixth root of unity. We find that $\omega^2 = \omega - 1$.
Let $A = 1+\omega, B = \omega, C = 0, D = 1-\omega, E = 2-\omega, F = 2$. These six points form a regular hexagon.
Then $M = (1-r)A, N = rE$.
Let $X = M\bar N + N\bar B + B\bar M$, simplify to obtain $X = a(r) + b(r)\omega$ for some real values $a(r)$ and $b(r)$ depending on $r$.
From this question we find that $M, N, B$ are collinear iff $X$ is real, which is the case iff $b(r) = 0$. By solving that you should be done quickly.


TITLE: Sheaf cohomology: meaning of $H^1(X,2\pi i\Bbb{Z})$
QUESTION [2 upvotes]: Let $X$ be a complex algebraic surface.
We have the exponential sequence $0\to 2\pi i\Bbb{Z}\to\mathcal{O}_X\to\mathcal{O}_X^*\to 0$.
This this article says that $H^1(X,2\pi i\Bbb{Z})$ is the singular cohomology group and that  $H^1(X,\mathcal{O}_X^*)$ may be identified with $\text{Pic}(X)$.
I don't understand this. How did we get from sheaf cohomology to singular cohomology and the group of divisors modulo linear equivalence?

REPLY [5 votes]: This is two different questions.
For the first, you need a comparison theorem between Cech and singular cohomology; you can find this in a variety of places. (EDIT: full references here https://mathoverflow.net/questions/310306/outline-of-the-proof-that-cech-cohomology-and-singular-cohomology-coincide-on-an).
For the second, you need that $H^1(X, \mathcal{O}_X^*)$ parametrizes line bundles; this is straightforward from Cech cohomology -- the transition functions for a line bundle give a class in $H^1$, check that two line bundles are isomorphic iff they differ (multiplicatively) by the trivial class. (EDIT: it looks like you've seen Pic defined in terms of divisors mod linear equivalence, so you also need that these are the same as line bundles!)


TITLE: What is the number of non-negative integers with at most four digits at least one of which is equal to 7?
QUESTION [0 upvotes]: What is the number of non-negative integers with at most four digits at least one of which is equal to 7?

REPLY [1 votes]: We have four sets $A$, $B$, $C$, and $D$, consisting of the nonnegative integers less than $10,000$ that respectively have the first, second, third, and fourth digits equal to $7$.
First, add up the cardinalities of all four sets. This gives $|A|+|B|+|C|+|D|=1000+1000+1000+1000=4000$.
Then, subtract the cardinalities of all the binary intersections. This gives $4000-|A \cap B|-|A \cap C|-|A \cap D|-|B \cap C|-|B \cap D|-|C \cap D|=4000-100-100-100-100-100-100=3400$.
Next, add the cardinalities of all the ternary intersections. This gives $3400+|A \cap B \cap C|+|A \cap B \cap D|+|A \cap C \cap D|+|B \cap C \cap D|=3400+10+10+10+10=3440$.
Finally, subtract the cardinality of the intersection of all four sets. This gives $3440-|A \cap B \cap C \cap D|=3440-1=3439$.
The answer is therefore $3439$, using the Inclusion-Exclusion Principle.


TITLE: $p$ is polynomial, set bounded open set with at most $n$ components
QUESTION [2 upvotes]: Assume $p$ is a non constant polynomial of degree $n$. Prove that the set $\{z:|(p(z))| \lt 1\}$ is a bounded open set with at-most $n$ connected components. Give example to show number of components can be less than $n$.
thanks.
EDIT:Thanks,I meant connected components.

REPLY [1 votes]: Fact 1 : If $f : G \to \mathbb{C} $ is analytic, $G$ open and connected and $f(G)$ is a subset of a circle (or a line) then $f$ is constant.
Fact 2 : $f:\overline{G} \to \mathbb{C}$ analytic on a bounded region $G$ and $|f|(\partial G) = \{c\}$, then either $f$ has a root in $G$ or $f$ is a constant.
To prove fact 2, say $c = 0$, then $ |f| \leq 0 $ by the maximum principle, but then $f = 0$ a constant.
Say $c \neq 0$ and $f \neq 0$ in $G$, then $\frac{1}{f} : \overline{G} \to \mathbb{C}$ is analytic in the interior and then assumes maximum on $\partial G$. We need then $|f| \leq c$ and $1/|f| \leq 1/|c|$ in $G$, then $ |f| = |c|$ in $G$.
From this, we have that $f$ maps connected $G$ on the circle $\{z \, : \, |z| = |c|\}$, then $f$ is constant by Fact 1.
$\square$
Suppose now we have $f$ a polynomial. Say $G \subset |f|^{-1}([0,c)) \doteq A$ a connected component of the bounded(Liouville) open $A$.
Note that $|f| = c$ at $\partial G$, by Fact 2 $f$ is either a constant polynomial or have a zero in the interior of $G$.
Say we have $\gamma(t) = (1-t)a + tb$ where $a$ and $b$ are zeros, $\{\gamma\}$ is compact, say then $|f| \leq c$ on this curve, then the entire curve $\{\gamma\}\subset |f|^{-1}([0,c+1)) = A_{c+1}$.
Note thar $a$ and $b$ will be two roots of $f$ lying on the same connected component of $A_{c+1}$.
[Pretty much Conway's Chapter VI]