text:
\section{{{\underline{\underline{#1}}}}}
\newcommand {\mysubsubsection} [1] {\subsubsection{{{#1}}}
\newcommand {\mysection} [1] {\section{{{#1}}}
\newcommand {\mysubsection} [1] {\subsection{{{#1}}}
\newcommand {\myParagraph} [1] {\subsubsection*{#1}}
\newcommand {\SaveSizeParagraph} [1] {\vspace{-1.6mm}\paragraph{#1}}
\newcommand {\SaveaMoreSizeParagraph} [1] {\vspace{-2.7mm}\paragraph{#1}}
\newcommand {\pr} [1] {\Pr \left[ {#1} \right]}
\newcommand {\given } {\hspace{0.2em} \vline \hspace{0.3em}}
\newcommand {\awlg} {assume w.l.o.g.~}
\newcommand {\Awlg} {Assume w.l.o.g.~}
\newcommand {\wlg} {w.l.o.g.~}
\newcommand {\Wlg} {W.l.o.g.~}
\newcommand {\wrt} {w.r.t.~}
\newcommand {\wip } {with probability~}
\newcommand {\wpm} {w.p.~}
\newcommand {\st}{s.t.~}
\newcommand {\as}{a.s.~}
\newcommand {\asns}{a.s.\hspace{-0.2ex}}
\newcommand {\etal} {et al.~\hspace{-0.1ex}}
\newcommand {\qed} {$\blacksquare$}
\newcommand {\qedm} {~\blacksquare}
\newcommand {\eqdef} {{~ \stackrel{\mathrm{def}} {=} ~}}
\newcommand {\poly} {\mathit{poly}}
\newcommand {\Z} {\mathbb{Z}}
\newcommand {\N} {\mathbb{N}}
\newcommand {\lb} {\left(}
\newcommand {\rb} {\right)}
\newcommand {\lsb} {\left[}
\newcommand {\rsb} {\right]}
\newcommand {\ceil}[1] {\lceil {#1} \rceil}
\newcommand {\floor}[1] {\lfloor {#1} \rfloor}
\newcommand {\into} {\rightarrow}
\newcommand {\eps} {\epsilon}
\newcommand {\opmo} {{\scriptstyle (1 \pm o(1))}}
\newcommand {\opo} {{\scriptstyle (1 + o(1))}}
\newcommand {\omo} {{\scriptstyle (1 - o(1))}}
\newif \ifCiteName \CiteNamefalse
\newcommand {\myBib} [2]{\ifCiteName \bibitem[#1]{#2}\else \bibitem{#2}\fi}
\newcommand \myTitle {\emph}
\newcommand \myCite {}
\newcommand \andCoAuthersBib {, }
\newcommand \andCoAuthers {and }
\newcommand {\ER} {Erd\"{o}s \andCoAuthers R\'{e}nyi~}
\newcommand {\ERbib} {Erd\"{o}s and R\'{e}nyi~}
\newcommand {\Erd} {Erd\"{o}s~}
\newcommand {\Erdns} {Erd\"{o}s}
\newcommand {\Bol} {Bollob\'{a}s~}
\begin{document}
\thispagestyle{empty}
\title{\bf{k-wise independent random graphs}}
\author{Noga Alon\thanks{
Schools of Mathematics and Computer Science,
Sackler Faculty of Exact Sciences, Tel Aviv
University, Tel Aviv 69978,
Israel, and IAS, Princeton, NJ 08540, USA.
Email:~{\texttt{nogaa@post.tau.ac.il.}}
Research supported in part by the Israel Science
Foundation and by a USA-Israeli BSF
grant.}
\and
Asaf Nussboim\thanks{Department of Computer Science and
Applied Mathematics, Weizmann Institute of Science,
Rehovot, Israel.
Email:~{\texttt{asaf.nussbaum@weizmann.ac.il.}}
{Partly supported by a grant from the Israel Science
Foundation.}}}
\date{}\maketitle
\begin {abstract}
We study the \kwi relaxation of the usual model \gnp of random
graphs where, as in this model,
$N$ labeled vertices are fixed and each edge
is drawn with probability $p$,
however, it is only required that the distribution of
any subset of $k$ edges is independent.
This relaxation can be relevant in modeling phenomena
where only \kwice is assumed to hold, and is also useful
when the relevant graphs are so huge
that handling \gnp graphs becomes infeasible, and
cheaper random-looking distributions (such as \kwi
ones) must be used instead. Unfortunately, many well-known
properties of random graphs in \gnp are global, and it is
thus not clear if they are
guaranteed to hold
in the \kwi case.
We explore the properties of \kwig by providing
upper-bounds and lower-bounds on the amount of
independence, $k$, required for maintaining the main
properties of \gnp graphs: connectivity,
Hamiltonicity, the connectivity-number, clique-number
and chromatic-number and the appearance of fixed
subgraphs.
Most of these properties are shown to be captured by
either constant $k$ or by some $k=\poly(\log(N))$ for
a wide range of values of $p$, implying that random looking graphs
on $N$ vertices can be generated by a seed of size
$\poly(\log(N))$. The proofs combine combinatorial, probabilistic
and spectral techniques.

\end {abstract}
\thispagestyle{empty}
\newpage \setcounter{page}{1}
\mysection{Introduction}
We study the \kwi relaxation of the usual model \gnp of random graphs
where, as in this model, $N$ labeled vertices are fixed and each
edge is drawn with probability (w.p., for short)~$p=p(N)$, however, it is only
required that the distribution of any subset of $k$
edges is independent (in \gnp all edges are
mutually independent).
These \kwig are natural combinatorial objects that
may prove to be useful in modeling scientific phenomena
where only \kwice is assumed to hold. Moreover,
they can be used when the relevant graphs are so huge, that handling \gnp graphs is infeasible, and cheaper random-looking distributions must be used instead.
However, what happens when the application that uses
these graphs (or the analysis conducted on them)
critically relies on the fact that \rgs are, say,
almost surely connected? After all, \kwice is defined via `local' conditions, so isn't it possible that
\kwig will fail to meet `global' qualities like
connectivity? This motivates studying which global attributes
of \rgs are captured by their \kwi counterparts.

Before elaborating on properties of \kwig we provide
some background on \kwicens, on properties of random
graphs, and on the emulation of huge random graphs.

\mysubsection
{Emulating Huge Random Graphs}
Suppose that one wishes to conduct some simulations on
random graphs. Utilizing \gnp graphs requires
resources polynomial in $N$, which is infeasible
when $N$ is huge (for example, exponential in the
input length, $n$, of the relevant algorithms).
A plausible solution is to replace \gnp by a
cheaper `random looking' distribution $\mathcal G_N$.
To this end, each graph $G$ in the support of
$\mathcal G_N$ is represented by a very short binary
string (called seed) $s(G)$, \st evaluating edge
queries on $G$ can be done efficiently when $s(G)$ is
known; Then, sampling a graph from $\mathcal G_N$ is
done by picking the seed uniformly at random.

Goldreich \etal were the first to address this scenario
in \cite{ggn}. They studied emulation by computationally
pseudorandom graphs, that are indistinguishable from \gnp from the view of
any $\poly(\log(N))$-time algorithm that inspects
graphs via edge-queries of its choice. They considered
several prominent properties of
\gnp graphs, and constructed computationally
pseudorandom graphs that preserve many of those
properties (see the final paragraph of Section \ref{compareGGN}).

We consider replacing \rgs by \kwi ones. The latter
can be sampled and accessed using only
$\poly(k\log(N))$-bounded resources. This is achieved
thanks to efficient constructions of discrete \kwi
variables by Joffe \cite{jof}, see also Alon, Babai and
Itai \cite{abi}:
the appearance of any potential edge in the graph is
simply decided by a single random bit (that has
probability $p$ to attain the value 1).
Such \kwig were used by Naor \etal \cite{nnt} to
efficiently capture arbitrary first-order properties
of huge \gnp graphs (see Section \ref{FO_paper}).

\mysubsection
{${\bf k}$-Wise Independent Random Variables}
Distributions of discrete \kwi variables play an
important role in computer science. Such distributions
are mainly used for de-randomizing algorithms (and for
some cryptographic applications). In addition, the
complexity of constructing \kwi variables was studied
in depth, and in particular, the aforementioned constructions
\cite{jof,abi} (based on degree $k$ polynomials over finite fields)
are known to provide essentially the smallest possible sample spaces.
Our work is, however, the first systematic
study of {\em combinatorial properties} of \kwi
objects. Properties of various other \kwi objects
(mainly percolation on $\Z^d$ and on Galton-Watson
trees) were subsequently explored by Benjamini,
Gurel-Gurevich and Peled \cite{bggp}.

\mysubsection
{The Combinatorial Structure of Random Graphs}
What are the principal attributes of \rgs that \kwi ones should maintain? Most theorems that manifest the remarkable structure of \rgs state that certain properties occur either almost surely (\as for
short), or alternatively hardly ever, (namely, \wip
tending either to 1 or to 0 as $N$ grows to $\infty$).
These results typically fall into one of the following
categories.

\SaveSizeParagraph{Tight concentration of measure.}
A variety of prominent random variables (regarding
random graphs) \as attain only values that are {\em
extremely close} to their expectation. For instance,
random graphs (with, say, constant $p$) \as have
connectivity number $\kappa=\opmo pN$, clique number
$c=\opmo \frac {2\log(pN)}{\log(1/p)}$ (\Bol
\andCoAuthers \Erd\cite{be}, Matula \cite{mat}, Frieze
\cite{fri}) and chromatic number $\chi=\opmo \frac
{N\log(1/1-p)}{2\log(pN)}$ (\Bol \cite{bolChi},
{\L}uczak \cite{l}).

\SaveSizeParagraph{Thresholds for monotone
properties.}
For a given monotone increasing\footnote{Namely, any
property closed under graph isomorphism and under
addition of edges.} graph property $T$, how large
should $p(N)$ be for the property to hold \asns?
This question had been settled for many prominent properties such as connectivity (\ER
\cite{erConn}), containing a perfect matching (\ER
\cite{erMatch1,erMatch2,erMatch3}), Hamiltonicity
(P\'{o}sa \cite{pos}, Kor\v sunov \cite{kor},
Koml\'{o}s \andCoAuthers Szemer\'{e}di \cite{ks0}), and
the property of containing copies of some fixed
graph $H$ (\ER \cite{erGiant}, \Bol \cite{bolsub}).
For these (and other) graph properties the sufficient
density (for obtaining the property) is surprisingly
small, and moreover, a threshold phenomenon occurs when
by `slightly' increasing the density from
$\underline{p}(N)$ to $\overline{p}(N)$, the
probability that $T$ holds dramatically changes from
$o(1)$ to $1-o(1)$.%
\footnote{Thresholds for prominent properties are
often so sharp that $\overline{p}=(1+o(1))
\underline{p}$. Somewhat coarser thresholds were (later)
established for {\em arbitrary} monotone properties by
\Bol \andCoAuthers Thomason \cite{bt}, and by Friedgut
\andCoAuthers Kalai \cite{fk}.}
Thus, good emulation requires the property $T$ to be guaranteed at densities as close as possible to the true \gnp threshold.

\SaveSizeParagraph{Zero-one laws.}
These well known theorems reveal that {\em any} first-order
property holds either \as or hardly ever for \gnpns. A
first-order property is any graph property that can be
expressed by a single formula in the canonical
language where variables stand for vertices and the
only relations are equality and adjacency (e.g.~``having an isolated vertex" is specified
by $\exists x \forall y \neg \mbox{\sc edge} (x,y)$).
These Zero-one laws hold for any fixed $p$ (Fagin \cite{fag}, Glebskii, Kogan, Liagonkii \andCoAuthers Talanov \cite{gklt}), and whenever $p(N)=N^{-\alpha}$ for a fixed irrational $\alpha$ (Shelah \andCoAuthers
Spencer \cite {ss}).

\mysection
{Our Contribution}

We investigate the properties of \kwig by providing
upper bounds and lower bounds on the `minimal' amount of
independence, $k_T$, required for maintaining the main properties $T$
of random graphs.\ifPersonal\footnote{When $k={{N \choose 2}}$ we get the original \gnp graphs, while for, say, $k=1$ (e.g., the case where \wip $p$ the graph is complete and otherwise it is empty) the resulting graphs have very little in common with \gnp graphs.} \else{ }\fi
The properties considered are:
connectivity, perfect matchings, Hamiltonicity, the
connectivity-number, clique-number and
chromatic-number and the appearance of copies of a
fixed subgraph $H$.
We mainly establish upper bounds on $k_T$ (where arbitrary \kwig are shown to exhibit the property $T$) but also lower bounds (that provide specific constructions of \kwig that fail to preserve $T$).
Our precise results per each of these properties are
discussed in Section \ref{intro_list_results},
and proved in Section \ref{claims_&_proofs} (and the Appendices).
Interestingly, our results reveal a deep difference
between \kwice and almost \kwice (a$.$k$.$a$.$
$(k,\eps)$-\wicens\footnote{$(k,\eps)$-\wice means
that the joint distribution of any $k$ potential edges
is only required to be within small statistical
distance $\epsilon$ from the corresponding
distribution in the \gnp case.}).
All aforementioned graph properties are guaranteed by
\kwice (even for small $k=\poly(\log(N))$), but are
strongly violated by some almost \kwig - even when
$k=N^{\Omega(1)}$ is huge and $\eps=N^{-\Omega(1)}$ is
tiny.
For some properties of random graphs, $T$, our results
demonstrate for the first time how to efficiently
construct random-looking distributions on huge graphs
that satisfy $T$.

\SaveSizeParagraph
{Our Techniques \& Relations to Combinatorial Pseudorandomness.}
\label{intro_jumbled}

For positive results (upper bounding $k_T$), we note that the original proofs that establish properties of \gnp
graphs often fail for \kwigns. These proofs use a union
bound over $M=2^{\Theta(N)}$ undesired events, by
giving a $2^{-\Omega(N)}$ upper-bound on the
probability of each of these events.%
\footnote{For instance \wrt connectivity, $M$ is the number of choices for partitioning the vertices into 2 disconnected components.%
\ifPersonal{~For perfect matchings, $M$ counts the
number of subsets of vertices that defy a sufficient
condition for the matching (by either Hall's Theorem or
Tutte's Theorem).
For the chromatic number, $M$ is the (a-priory) number of possible sub-graphs from which a greedy coloring
algorithm might choose a large independent set that is
colored with a single color.}\fi}
Unfortunately, there exist $\poly(\log(N))$-\wig
\ifPersonal that can be constructed consuming only
$\Theta(k \log(N))$ random bits. Hence, any event that
occurs with positive probability (in these
constructions), must hold \wip $\geq 2^{-\Theta(k
\log(N))}$ which is $\gg \frac 1 M$ when $k \leq
\poly(\log(N))$. \else where any event that occurs
with positive probability, has probability $\geq
2^{-o(N)}$. \fi
Therefore, directly `de-randomizing' the original proof fails, and alternative arguments (suitable for the $k$-wise independent case) are provided.

In particular, many properties are inferred via a variant of
Thomason's notion of `jumbledness' \cite{t}
(mostly known in its weaker form as quasirandomness or
pseudorandomness, as defined by Chung, Graham \andCoAuthers Wilson
\cite{cgw}, and related to the so called Expander Mixing Lemma and the
pseudo-random properties of graphs
that follow from their spectral properties, see \cite{ac}).
For our purposes, $\alpha$-jumbledness means that (as expected in
\gnp graphs) for all vertex-sets $U,V$, the number of
edges that pass from $U$ to $V$ should be $p|U||V|
\pm \alpha \sqrt{|U||V|}$.
Jumbledness and quasirandomness had been studied extensively (see
\cite{ks} and its many references), and serve in Graph Theory as
{\em the} common notion of resemblance to random graphs. In
particular, \gnp graphs are known to exhibit (the best
possible) jumbledness parameter,
$\alpha=\Theta(\sqrt{pN})$.
One of our main results (Theorem
\ref{kwise_gives_jumbl}) demonstrates that \kwice for
$k=\Theta( \log(N))$ is stronger than jumbledness, in
the sense that it guarantees the optimal
$\alpha=\Theta(\sqrt{pN})$ even for tiny densities
$p=\Theta(\frac{\ln(N)}N)$.
Therefore, prominent properties of \kwig can be directly deduced from properties of jumbled graphs.

Proving Theorem \ref{kwise_gives_jumbl} exploits a
known connection between jumbledness and the
eigenvalues of (a shifted variant of) the adjacency
matrix of graphs, following the approach in \cite{ac}.
In particular, the analysis of Vu (\cite{vu},
extending \cite{fk2}) regarding the eigenvalues of
random graphs is strengthened, in order to achieve
optimal eigenvalues even for smaller densities $p$
than those captured by \cite{vu}. This improvement
implies, among other results, the remarkable fact that
\kwig for $k=\Theta(\log(N))$ preserve (up to constant
factors) the \gnp sufficient density for connectivity.

\SaveSizeParagraph
{More on Techniques \& Relations to Almost $k$-Wise Independence.}
\label{almost_k_wise}

For negative results (producing random-looking graphs
that defy a given property $T$ of random graphs), the
\cite{ggn,my_thesis} approach is to first construct
some random-looking graph $G$, and later to `mildly'
modify $G$ \st $T$ is defied. This is done \wrt all graph properties considered here. For instance, the
modification of choosing a random vertex and then deleting all it's edges violates connectivity while preserving computational pseudorandomness.
Unfortunately, such modifications \ifSaveSize \else are useless in our context because they \fi fail to preserve
\kwice \ifPersonal and it is typically not clear how
to modify the graph for the second time to regain \kwice \else \fi (the resulting graphs are only almost \kw independent).
In contrast, most of our negative results exploit the fact
that some constructions of \kwi bits produce
strings with significantly larger probability than in
the completely independent case. This is translated
(by the construction in Lemma
\ref{kwise_construction_unexpected_sub_graphs}) to the
unexpected appearance of some subgraphs (in \kwigns):
either huge independent-sets inside dense graphs or
fixed subgraphs inside sparse graphs.

\SaveSizeParagraph
{Comparison with Computational Pseudorandomness.}
\label{compareGGN}

Finally, \kwice guarantees all random graphs'
properties that were met by the (specific)
computationally pseudorandom graphs of
\cite{ggn,my_thesis}\ifSaveSize. \else \footnote{A
single exception is preserving the precise \gnp
upper-bound on the chromatic number only up to a
constant factor, whereas no such factors are
introduced by \cite{ggn,my_thesis}.}. \fi
\ifSaveSize In addition, only \kwice captures \else
The list of random graph properties captured by \kwice
but not by \cite{ggn,my_thesis} includes \fi (i)
arbitrary first-order properties of \gnp graphs, (ii)
high connectivity, (iii) strongest possible parameters
of jumbledness, and (iv) almost regular $(1\pm
o(1))pN$ degree for all vertices, and $(1\pm
o(1))p^2N$ co-degrees for all vertex pairs.
Importantly, all this holds for any \kwigns,  (and in
particular for the very simple and efficiently
constructable ones derived from \cite{jof,abi}),
whereas the \cite{ggn,my_thesis}'s approach requires
non-trivial modifications of the construction per each
new property.

\mysection
{Combinatorial Properties of ${\bf k}$-Wise Independent
Graphs} \label{intro_list_results}

We now survey our main results per each of the
aforementioned graph properties $T$. Typically our
arguments establish the following tradeoff: the
smaller $p$ is, the larger $k$ should be to maintain
$T$.
Given this tradeoff we highlight minimizing $k$ or, alternatively, minimizing $p$. The latter is
motivated by the fact that the \gnp threshold for
many central properties occurs at some $p^*\ll 1$.
Minimizing $p$ is subject to some reasonable choice of
$k$, which is $k\leq \poly(\log(N))$. Indeed, as the
complexity of implementing \kwig is $\poly(k
\log(N))$, we get efficient implementations whenever
$k \leq \poly(\log(N))$ even when the graphs are huge
and $N=2^{\poly(n)}$.
\footnote{Accessing the graphs via edge-queries is
adequate only when $p \geq n^{-\Theta(1)}$ - otherwise
\as no edges are detected by the $\poly(n)$ inspecting
algorithm. For smaller densities our study has thus mostly a
combinatorial flavor.}

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{Connectivity, Hamiltonicity and Perfect Matchings
(see Section \ref{section_conn_Ham})}

The well known sufficient \gnp density for all these
properties is $\sim \frac {\ln(N)}N$. For
connectivity, this sufficient density is captured (up
to constant factors) by all $\log(N)$-\wigns. Even
$k=4$ suffices for larger densities $p \gg N^{-\frac 1
{2}}$.
Based on Hefetz, Krivelevich \andCoAuthers Szabo's
\cite{hks}, Hamiltonicity (and hence perfect
matchings) are guaranteed at $p\geq \frac
{\log^2(N)}{N}$ with $k\geq 4\log(N)$, and at $p \geq
N^{-\frac 1 {2}+o(1)}$ with $k\geq 4$.
On the other hand, some pair\wig are provided that
despite having constant density, are still \as
disconnected and fail to contain any perfect matching.
\ifPersonal Note that by changing $k$ to 4, and the
density to $p=1/2 + N^{-\Theta(1)}$, all properties are
ensured again (since then all the degrees are $\leq
\frac N 2$). More importantly, note that the combination
of these results immediately rule out the possibility of
establishing a general threshold phenomenon (for all
monotone properties) when $k=2$.} \fi

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{High Connectivity
(see Section \ref{section_high_conn})}

The connectivity number, $\kappa(G)$, is the largest
integer, $\ell$, \st any pair of vertices is connected
in $G$ by at least $\ell$ internally vertex-disjoint
paths. Since a typical degree in a random graph is
$(1\pm o(1)) pN$, it is remarkable that \gnp graphs
achieve $\kappa = (1\pm o(1)) pN$ \asns.
Surprisingly, such optimal connectivity is guaranteed
by $\Theta(\log(N))$\wice whenever $p \geq
\Theta(\frac {\log(N)}{N})$.

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{Cliques and Independent-Sets
(see Appendix \ref{appendix_indp_num})}

For $N^{-o(1)} \leq p \leq 1-N^{o(1)}$ the
independence number, $I$, of random graphs has \as
only two possible values: either $S^*$ or $S^*+1$ for
some $S^*\sim \frac {2\log(pN)}{\log(1/(1-p))}$.
This remarkable phenomenon is observed to hold by
$\Theta(\log^2(N))$-\wice whenever $p$ is
bounded away from 0.
On the other hand, \kwig are provided with $k= \Theta
\lb \frac {\log(N)}{\log \log(N)}\rb$ where $I \geq
(S^*)^{1+\Omega(1)}$ \as (for $k=\Theta(1)$, even huge
$N^{\Omega(1)}$ independent-sets may appear).
For smaller densities, random graphs \as have $I \leq
O(p^{-1} \log(N))$, while $\Theta(\log(N))$\wice gives
a weaker, yet useful, $I \leq O(\sqrt{\frac N p})$
bound whenever $p\geq \Omega (\frac{\log(N)}N)$.
By symmetry (replacing $p$ with $1-p$), analogous
results to all the above hold for the clique number as
well.
Discussing the clique- and independence-number is
deferred to the appendices since the main
relevant techniques here are demonstrated elsewhere in the paper.

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{Coloring
(see Section \ref{section_color})}

For $1/N \ll p \leq 1-\Omega(1)$, the chromatic number $\chi$ of random graphs
is a.s. $(1+o(1))\frac
{N\log(1/1-p)} {2\log(pN)}$.
This \gnp lower-bound on $\chi$ is observed to hold
for any $(\log(N))^{\Theta(1)}$\wig with moderately
small densities $p\geq (\log(N))^{-\Theta(1)}$.
More surprisingly, $k=\Theta(\log(N))$ suffices to
capture a similar upper-bound (even for tiny densities
$p=c \log(N)/N$).
This upper-bound is based on Alon, Krivelevich
\andCoAuthers Sudakov's \cite{aks}, \cite{aks1} and on Johansson's
\cite{joh}.

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{Thresholds for the Appearance of Subgraphs
(see Section \ref{section_sub_graphs})} \label{intro_H_copies}

For a fixed (non-empty) graph $H$, consider the
appearance of $H$-copies ({\em not necessarily} as an
induced subgraph) in either a random or a \kwi
graph.\ifPersonal\footnote{
When $H$ is empty, the question is trivial because every
graph $G$ (of sufficient order) contains $H$ copies.
This formally translates to $\rho=\infty$ and to
$p^*=0$.}\else~\fi
The \gnp threshold for the occurrence of $H$ sub-graphs
lies at $p^*_H \eqdef N^{-\rho}$, where the constant
$\rho=\rho(H)$ is the minimum, taken over all subgraphs
$H'$ of $H$ (including $H$ itself), of the ratio $\frac
{v(H')} {e(H')}$ (here, $v(H')$ and $e(H')$ respectively
denote the number of vertices and edges in $H'$).
Thus, no $H$-copies are found when ${p}\ll p^*$, while for any ${p}\gg p^*$, copies of $H$ abound (\ER \cite{erGiant}, \Bol \cite{bolsub}).
\ifPersonal
\begin{remark} The ratio $\rho$ decides the
threshold, since it is minimized for the most `dense'
subgraph $H'$. Intuitively, this $H'$ is the sub-graph
less likely to appear in a \gnp graph, so $H$-copies
\as appear iff $H'$-copies \as appear.\end{remark}

\begin{remark} Note that $\frac 1 {v-1} \leq \rho \leq
2$, where the lower bound is tight (only) for cliques,
and the upper bound is tight iff $H$ contains only
disjoint edges. As $v=v(H)$ grows, most graphs have
$e(H)=\Theta(v^2)$, so $\rho=\Theta(1/v)$.\end{remark}

\fi
For any graph $H$, this \gnp threshold holds whenever
$k\geq \Theta (v^4(H))$, but as $k$ is decreased to
$\floor{\frac 2 {\rho}}$, the \gnp threshold is defied:
much sparser graphs exist where $p \ll p^*_H$ and yet
copies of $H$ are \as found.
In particular, when $e(H)\geq \Omega(v^2(H))$,
\ifPersonal then $\rho \leq O(1/v(H))$, so \fi the
threshold violation occurs at $k= \Omega(v(H))$.
\ifPersonal Note that our negative results are optimal
in the sense that they capture all possible graphs $H$
(see footmark inside statement of Theorem
\ref{sub_graphs_defy}). The optimality of $k$ is
discussed in remark \ref{remark_rho_cond_reasonable}.
\fi

\ifSaveSize{\vspace{-2.7mm}}\fi \mysubsection
{First Order Zero-One Laws (Previous Results)}
\label{FO_paper}

\ifSaveSize Naor \etal \cite{nnt} have recently \else a recent study (joint work of the second author with Naor \andCoAuthers Tromer \cite {nnt}) \fi studied capturing arbitrary depth-$D(N)$ properties.
These are graph properties expressible by a sequence of first-order formulas $\Phi=$ $\{\phi_N\}_{N \in \mathbb N}$, with quantifier depth $\mathit{depth}(\phi_N) \leq D(N)$%
\ifSaveSize. \else
(e.g.~``having a clique of size $t(N)$" can be specified
by $\phi_N = \exists x_1 ... \exists x_{t(N)}
\bigwedge_{i \neq j} ((x_i \neq x_j) \bigwedge
\mbox{\sc edge}(x_i,x_j))$). \fi
A `threshold' depth function $D^*\sim\frac{\log(N)}{\log(1/{p})}$ was
identified \st arbitrary \kwig resemble \gnp graphs \wrt all
depth $D^*$ properties. The underlying resemblance-definition is in
fact so strong, that even \gnp graphs cannot achieve resemblance
to themselves \wrt properties of higher depth. On the other hand,
\kwig were shown to defy some \gnp properties of depth
$\Theta(\sqrt{k\log(N)}+\log(N))$.
These results are incomparable to the ones in the current paper,
since most of the graph properties studied here require larger
depth than $D^*$.
\ifPersonal\footnote{ Note that the naive recursive
formula for connectivity has depth $3 \log(N)$ but
exponential size, while Savitch's Theorem \cite{sav}
gives linear size and $5 \log(N)$ depth. On the other
hand, by a simple Ehrenfeucht-game argument, depth $2
\log(N)-\Theta(1)$ is insufficient for connectivity.
For optimal Ramsey graphs depth $2 \log(N)$ suffices,
which is again tight by some trivial Ehrenfeucht-game
argument.}
Thus, a more direct approach is needed to establish such
properties for \kwigns.\footnote{Note that, in addition,
direct proofs may reduce the amount of independence $k$
required. For instance for appearance of subgraphs of
order $v$, then $k=\Theta(v^4)$ suffices instead of $k
\sim \frac{\log^3 N}{\log^2(1/p)}$.}\fi

\mysection{Preliminaries
\paragraph{Asymptotics.}
Invariably, $k: \N \into \N$, while
$p,\eps,\delta,\gamma,\Delta: \N \into (0,1)$. We
often use $k,p,\eps,\delta,\gamma,\Delta$ instead of
$k(N),p(N),\eps(N),\delta(N),\gamma(N),\Delta(N)$.
Asymptotics are taken as $N \rightarrow \infty$, and
some inequalities hold only for sufficiently large
$N$. The $\floor{\cdot}$ and $\ceil{\cdot}$ operators
are ignored whenever insignificant for the asymptotic
results. Constants $c,\bar c$ are not optimized in
expressions of the form $k=c\log(N)$ or
$p=(\log(N))^{\bar c}/N^{\Delta}$, whereas the
constant $\Delta$ is typically optimized.

\SaveaMoreSizeParagraph{Subgraphs.}
For a graph $H$, let $v(H)$ and $e(H)$ denote the number
of vertices and edges in $H$. For vertex sets $U,V$ let
$e(U,V)$ denote the number of edges that pass from $U$ to
$V$ (if $S=U \bigcap V \neq \emptyset$, then any
internal edge of $S$ is counted twice). Similarly, we
let $e(U)=e(U,U)$.

\SaveaMoreSizeParagraph{Random and ${\bf k}$-Wise
Independent Graphs.}
Throughout, graphs are simple, labeled and undirected.
Given $N,k,p$ as above then $\gnknm$~ (or $\gnkm$~ for short)
denotes some distribution over the set of graphs with
vertex set $\{1,...,N\}$, where each edge appears
w.p.~$p(N)$, and the random variables that indicate the
appearance of any $k(N)$ potential edges are mutually
independent. We use the term `\kwigns' for a sequence of
distributions \ens{\mathcal G^{k}(N,p)} indexed by $N$.

\SaveaMoreSizeParagraph{Almost Sure Graph Properties.}
A graph property $T$, is any property closed under
graph isomorphism. We say that `$T$ holds a.s.~(almost
surely) for $\mathcal G^{k}(N,p)$' or that (abused notation) `$T$
holds for $\mathcal G^{k}(N,p)$' whenever $\Pr_{\mathcal G^{k}(N,p)}[T]$ {}
$\stackrel {N \into \infty} {\longrightarrow} 1$. Similar terminology is used for \gnp graphs.

\SaveaMoreSizeParagraph{Monotonicity in $(\bf{k,p})$.}
Since $\bar k$-\wice implies $k$-\wice for all $\bar k >
k$ we may state claims for arbitrary $k\geq k'$ but
prove them only for $k=k'$.
When establishing monotone increasing properties we
often state claims for arbitrary $p\geq p'$ but prove
them only for $p=p'$.
The latter is valid since for any $N,k,p>p'$, the
process of sampling from any (independent) $\mathcal G^k(N,p)$,
$\mathcal G^k(N,p'/p)$ distributions and defining the
final graph with edge-set being the intersection of the
edge-sets of the two sampled graphs, clearly results in a $\mathcal G^k(N,p')$ distribution.
\ifPersonal Assuming that $k=k',p=p'$ is used only to
ensure the $\frac {M-k}k \mu(1-\mu) \geq 1$ condition in
Lemma \ref{kwise_Chebyshev_bound} (the $k \leq \frac N
3$ condition holds anyway, whenever the Lemma is
meaningful).
Finally, lower-bounds on $p$ are often provided only for
sake of clarity (these lower-bounds are redundant as
they follow immediately from the companion bounds on
$\eps$ or $\gamma$).\fi

\SaveaMoreSizeParagraph{${\bf k}$-Wise Independent
Random Variables.}
The term `$(M,k,p)$-variables' stands for any $M$
binary variables that are $k$-wise independent with
each variable having probability $p$ of attaining
value 1. Lemma \ref{modify_JoffeCG_lem} (proved in
Section \ref{modify_JoffeCG_sec}) adjusts the known
construction of discrete \kwv of \cite{jof},\cite{cg}, \cite{abi} to
provide $(M,k,p)$-variables that induce some
predetermined values with relatively high
probability. Throughout, $e_1$ and $e_0$ resp.~denote
the number of edges and non-edges in a graph $H$.

\blem \label{modify_JoffeCG_lem} Given $0<p<1$ with
binary representation $p=0.b_1...b_{\ell}$, and
natural numbers $e_0,e_1,M$ satisfying $e_0+e_1\leq
M$, let $F= \max \{2^{\ceil{\log_2M}},2^{\ell}\}$.
Then there exists $(M,k,p)$-variables \st
$\Pr[A]=F^{-k}$, where $A$ denotes the event that the
first $e_0$ variables receive value 0 while the next
$e_1$ variables receive value 1. \elem

\SaveaMoreSizeParagraph{Tail Bounds for ${\bf k}$-Wise
Independent Random Variables.}
The following strengthened version of standard tail
bounds (proved in Section \ref{sec_inequal})
translates into smaller densities $p$ for which
monotone graph properties are established for \kwigns.

\blem \label{kwise_Chebyshev_bound} Let $X=\sum_{j=1}^M
X_{j}$ be the sum of \kwi binary variables where
$\Pr[X_j=1]=\mu$ holds for all $j$. Let $\delta > 0$,
and let $k$ be even \st $\frac {M-k}k \mu(1-\mu) \geq
1$. Then
$$\Pr[|X-\mathbb E(X)| \geq \delta \mathbb E(X)] \leq
\left [\frac {2k(1-\mu)} {\delta^2 \mu M}\right] ^{\fktb}.$$
\elem

\mysection{The properties of ${\bf k}$-wise
independent graphs} \label{claims_&_proofs}
\mysubsection{Degrees, Co-Degrees and Jumbledness}
\ifPersonal For future purposes, we first establish some
fundamental random graphs' properties, such as having
almost regular degrees and co-degrees as well as
achieving strong jumbledness.\fi

\ble{Achieving almost regular degrees}
\label{kwise_gives_deg}
In all \kwig \ens{\gnkm}  it \as holds that all vertices have degree~~$p(N-1)(1 \pm \eps)$ whenever $N \big[\frac {3k} {\eps^2
pN}\big]^{\floor{k/2}} \longrightarrow 0,$ and in
particular when either \ben
\item
$k\geq 4$,~$N^{-1/2} \ll p \leq 1-\frac 5 N$, and $1 \geq \eps \gg p^{-1/2}N^{-1/4};$~~or
\item
$k\geq 4\log(N)$,~$\frac{25\log(N)}{N} \leq p \leq
1-\frac {5 \log(N)} N$, and $1 \geq \eps \geq
\sqrt{\frac{25\log(N)}{p N}}.$ \een \ele
\noindent{\bf Proof.} Fix a vertex $v$, and let $X_w$ be
the random variable that indicates the appearance of the
edge $\{v,w\}$ in the graph. Thus, the degree of $v$ is
$X=\sum_{w\neq v}X_w$. Since $X$ is the sum of
$(N-1,k,p)$-variables, Lemma \ref{kwise_Chebyshev_bound}
implies that the probability that $v$ has an unexpected
degree $X \neq p(N-1)(1\pm\eps)$ is bounded by
$\big[\frac {3k} {\eps^2 pN}\big]^{\floor{k/2}}.$
Applying a union-bound over the $N$ possible vertices
$v$, gives that the probability of having {\em some}
vertex with unexpected degree is bounded by $N
\big[\frac {3k} {\eps^2 pN}\big]^{\floor{k/2}},$ which
vanishes for the parameters in items 1 and 2. \qed

\ble{Achieving almost regular
co-degrees} \label{kwise_gives_codeg}
In all \kwig \ens{\gnkm}  it \as holds that all vertex pairs
have co-degree~~$p^2(N-2)(1\pm \gamma)$ whenever
either \ben
\item
$k\geq 12$,~$N^{-\frac 1 6} \ll p \leq 1-\frac {13} N$, and $1 \geq \gamma \gg p^{-1} N^{-\frac 1 6};$~~or
\item
$k\geq 12\log(N)$,~$\sqrt{\frac{73 \log(N)}{N}} \leq p
\leq 1-\frac {13 \log(N)} N$~~and~~$1 \geq \gamma \geq
\sqrt{\frac {73 \log(N)} {p^2N}}.$ \een \ele
\ifPersonal{%
\noindent{\bf Proof.} We prove item 1 for $k=12$, item
2 for $k=12\log(N)$ and item 3 for $k=4$. The claim
follows for $\bar k > k$, since $\bar k$-\wice implies
$k$-\wicens.
Fix a vertex pair $\{u,v\}$, and let $X_w$ be the random variable indicating the appearance of both edges $\{u,w\}$, $\{v,w\}$ in the graph. Thus the co-degree of $\{u,v\}$ is $X=\sum_{w\neq u,v}X_w$. %
Now $X$ is the sum of $N-2$ binary variables that are
$\lb k/2 \rb$-wise independent and each has probability
of success $p^2$. Thus, Lemma
\ref{kwise_Chebyshev_bound} combined with a union-bound
over the $\binom N 2 $ possible vertex pairs $\{u,v\}$,
ensures that the probability that there exist {\em some}
vertex-pair with unexpected co-degree $X \neq
p^2(N-2)(1\pm\gamma)$ is bounded by $\binom N 2 \left
[\frac {3k} {\gamma^2 p^2N}\right]^{\frac k 4}.$
Clearly, the latter expression vanishes for our choice
of parameters. \qed
\else \noindent{\bf Proof.} The proof is completely
analogous to that of Lemma \ref{kwise_gives_deg}. Here the
union-bound is over all $\binom N 2 $ vertex pairs
$\{u,v\}$, and the co-degree of each $\{u,v\}$ is the
sum of $(N-2, \floor {\frac k 2}, p^2)$-variables. \qed
\fi

The following definition is a modified version of the one in
\cite{t,cgw}, see also \cite{ac} and \cite{as}, Chapter 9.

\bdf {Jumbledness} \label{def_jumbl}
For vertex sets $U,V$, let $e(U,V)$ denote the number of edges that
pass from $U$ to $V$ (internal edges of $U \bigcap V$
are counted twice). A graph is $(p,\alpha)$-jumbled if
$e(U,V)=p |U||V| \pm \alpha \sqrt{|U||V|}$ holds for all
$U,V$. \edf

\btn{Achieving optimal jumbledness}
\label{kwise_gives_jumbl} There exist absolute
constants $c_1,c_2,c_3$ \st all \kwig \ens{\gnkm}  are \as
$(p,\alpha)$-jumbled whenever either:
\ben
\item
$k\geq 4$, $p\geq \Omega(\frac {1}{N})$~~and~~$\alpha
\gg \sqrt{p}N^{3/4}$;~~or
\item
$k\geq \log(N)$, $\frac {c_1 \log(N)}{N} \leq p \leq
1- \frac {c_2 \log^4(N)}{N}$~~and~~$\alpha \geq c_3
\sqrt{pN}.$ \een \etn
\noindent{\bf Proof.} The proof is based on spectral techniques
and combines some refined versions of ideas  from \cite{ac}, \cite{fk2}
and \cite{vu}, using the fact that  traces of the $k$-th power of the
adjacency matrix of a graph are identical in the $k$-wise independent case
and in the totally random one. The details are somewhat lengthy and
are thus deferred to Appendix \ref{proof_kwise_gives_jumbl}.

\mysubsection{Connectivity, Hamiltonicity and Perfect
Matchings}\label{section_conn_Ham}

\btn{Achieving connectivity}
\label{kwise_gives_conn}
There exists a constant $c$ \st the following holds. All \kwig \ens{\gnkm}  are \as
connected whenever either:
\begin{itemize}
\item
$k\geq 4$~~and~~$p \gg \frac {1}{\sqrt{N}}$;~~or
\item
$k\geq 4\log(N)$~~and~~$p\geq \frac {c\ln(N)}{N}$.
\end{itemize}
\etn
\noindent{\bf Proof.} Let $U$ be a vertex-set that
induces a connected component. Connectivity follows from
having $|U|>0.5N$ for all such $U$. The following holds
\as for $\mathcal G^{k}(N,p)$. By Lemma \ref{kwise_gives_deg}, all
vertices have degree $\geq 0.9pN$, so $e(U) \geq
0.9pN|U|$. By Theorem \ref{kwise_gives_jumbl}, all sets
$U$ satisfy $e(U)\leq p|U|^2 + \alpha|U|$ with $\alpha=
O(\sqrt{pN})= o(pN)$. Re-arranging gives $(0.9-o(1))N
\leq |U|$. \qed

\btn{Achieving Hamiltonicity}
\label{kwise_gives_Ham}
All \kwig \ens{\gnkm}  are \as Hamiltonian (and for even $N$ contain a perfect matching) whenever either:
\begin{itemize}
\item
$k\geq 4$~~and~~$p \geq \frac {\log^2(N)} {\sqrt
N}$;~~or
\item
$k\geq 4\log(N)$~~and~~$p\geq \frac {\log^2(N)}{N}$.
\end{itemize}
\etn
\noindent{\bf Proof.} Let $\bar \Gamma(V)$ denote the
set of vertices $v \notin V$ that are adjacent to some
vertex in the vertex-set $V$. By Theorem 1.1 in
Hefetz, Krivelevich \andCoAuthers Szabo's \cite{hks},
Hamiltonicity follows from the existence of constants $b,c$
such that \as
(i) $|\bar \Gamma(V)|\geq 12 |V|$ holds for all sets
$V$ of size $\leq b N$, and (ii) $e(U,V)\geq 1$ holds
for all disjoint sets $U,V$ of size $\frac {c
N}{\log(N)}$. We remark that (unlike other asymptotic
arguments in this paper), the sufficiency of (i) and
(ii) might hold only for very large $N$.
For (i), let $b= \frac 1 {170}$ and consider an
arbitrary set $V$. By Theorem \ref{kwise_gives_jumbl},
\as all vertex-sets $T$ have $e(T) \leq p|T|^2 +
o(pN)|T|$. By Lemma \ref{kwise_gives_deg} \as all the
degrees are $\opmo pN$, so exactly $\opmo pN|V|$ edges
touch $V$ (where internal edges are counted twice).
Let $T=V \bigcup \bar \Gamma(V)$, and assume that $|\bar
\Gamma(V)| < 12|V|$. We get $\omo pN|V| \leq e(T) \leq p
(13|V|)^2 + o(pN)|V|$. Re-arranging gives $|V| > \frac N
{170}$. Condition (i) follows.
For (ii), by Theorem \ref{kwise_gives_jumbl}, \as all
(equal-sized and disjoint) vertex-sets $U,V$ have
$e(U,V) \geq p|U||V| - O(\sqrt{pN})|U|$. If there is
no edge between $U$ and $V$, then $e(U,V)=0$.
Re-arranging gives $|U|\leq O(\sqrt{N/p}) \leq O(\frac
N{\log(N)})$. Condition (ii) follows. \qed

\btn {Failing to preserve connectivity}\label{kwise_gives_Ham} There exist
pair-wise independent graphs \ens{\gnkm} \\
where $p=1/2$, that are (i) \as disconnected
(and contain no Hamiltonian cycles), and that (ii)
contain no perfect matchings \wip  $1$. \etn
\noindent{\bf Proof.} Consider the graphs defined by
partitioning all vertices into 2 disjoint sets
$V_0,V_1$ where each $V_j$ induces a clique, no edges
connect $V_0$ to $V_1$, and $V_1$ is chosen randomly and uniformly among
all subsets of odd cardinality  of the vertex set. Note that for every
set of $4$ vertices, there are $16$ ways to split its vertices among $V_0$
and $V_1$, and it is not difficult
to check that if $N \geq 5$, then each of these $16$ possibilities
is equally likely.
Therefore, any edge appears w.p.~$\frac 1 2$, and any pair
of edges (whether they share a common vertex or not)
appears w.p.~$\frac 1 4$. Still the graph is connected
iff all the vertices belong to the same $V_j$ which
happens only w.p.~$2^{-N+1}$ (and only if $N$ is odd).  Since
$|V_1|$ is odd, the graph contains no perfect matching.
\qed
\ifPersonal %
Note that these graphs are not 3-wise independent, as
the existence of the edges $\{u,v\}$ and $\{v,w\}$
implies the existence of the edge $\{u,w\}$. Also note
that this construction cannot be generalized for $p \neq
\frac 1 2$ (by assigning vertices w.p.~$q$ to $V_0$ and
w.p.~$1-q$ to $V_1$). Indeed, consider the requirements
(i) $p=q^2+(1-q)^2$ and (ii) $p^2=q^3+(1-q)^3$. If we
plug (i) into (ii) we get an equation of degree 4 that
by Vieta's formula has only 3 solutions $p=0,\frac 1
2,1$ (see
\url{http://planetmath.org/encyclopedia/VietasFormula.html}).

We also remark that when $p$ is slightly increased to
$1/2 + N^{-\Theta(1)}$, then 4-\wice {\em does} suffice
for achieving connectivity since then all vertices \as
have degree $> N/2$. Then, by Dirac's Theorem, the
graphs are in fact Hamiltonian. \else

Note that when $p$ is slightly increased to $1/2 +
N^{-\Theta(1)}$, then 4-\wice suffices for achieving
Hamiltonicity (via Dirac's Theorem), because then \as
all vertices have degree $> N/2$.
\fi%

\mysubsection{High-connectivity}
\label{section_high_conn}
\btn{Achieving optimal connectivity}
\label{kwise_gives_kappa_jumbl}
There exists an absolute constant $c$, \st for all
\kwig \ens{\gnkm}  the connectivity number is \as $\opmo pN$
when either
\begin{itemize}
\item
$k\geq 4$~~and~~$p \gg N^{-\frac 1 {3}}$;~~or
\item
$k\geq \log(N)$~~and~~$p \geq c \frac{\log(N)}{N}$.
\end{itemize}
\etn
\noindent{\bf Proof.}
The connectivity is certainly not larger than $(1+o(1))pN$, as it
is upper-bounded by the minimum degree.
By Theorem 2.5 in Thomason's \cite{t} $\kappa \geq d-
\alpha/p$ holds for any $(p,\alpha)$-jumbled graph with
minimal degree $\geq d$. Thus, achieving $\kappa \gtrsim
pN$, reduces to obtaining (i) $d = (1\pm o(1))pN$, and
(ii) $\alpha \ll pd$.
Condition (i) \as holds by Lemma \ref{kwise_gives_deg}.
By Theorem \ref{kwise_gives_jumbl}, we \as achieve
$(c_3\sqrt{pN})$-jumbledness for some constant $c_3$,
so condition (ii) becomes $p^2N \gg \sqrt{pN}$. This
proves the first part of the theorem. To prove the
second we note, first, that we may assume that $p \ll
1$ (since otherwise $4$-wise independence suffices).
Let $S$ be a smallest separating set of vertices,
assume that $|S|$ is smaller than $(1-o(1))pN$, let
$U$ be the smallest connected component of $G-S$ and
let $W$ be the set of all vertices but those in $U
\cup S$. Clearly $|W| \geq (\frac{1}{2}-o(1))N$. Note
that $e(U,W)=0$, but by jumbledness $e(U,W) \geq
p|U||W| -c_3 \sqrt {pN |U||W|}$. This implies, using
the fact that $|W|>N/3$, that $|U| \leq
\frac{3c_3^2}{p}$. Using jumbledness again, $e(U,S)
\leq p|U||S|+c_3 \sqrt {pN |U||S|}$ but as all degrees
are at least $(1-o(1))pN$, $e(U,S) \geq
(1-o(1))pN|S|-e(U) \geq (1-o(1))pN|U|-p|U|^2- c_3
\sqrt {pN} |U| \geq |U| (1-o(1))pN$, where here we
used the fact that $|U| \leq O(1/p)$ and that
$\sqrt{pN} =o(pN)$. This implies that either $p|U||S|
\geq \frac{1}{2}|U|pN$, implying that $|S| \geq N/2
\gg pN$, as needed, or $c_3 \sqrt {pN|U||S|}  \geq
\frac{1}{3}|U|pN$, implying that $|S| \geq
\frac{1}{9c_3^2} |U| pN$ which is bigger than $pN$
provided $|U| \geq 9c_3^2$. However, if $|U|$ is
smaller, then surely $|S| \geq (1-o(1))pN$, since all
degrees are at least $(1-o(1))pN$ and every vertex in
$U$ has all its neighbors in $U \cup S$.
\qed

\mysubsection{Thresholds for the Appearance of
Subgraphs}\label{section_sub_graphs}

For a fixed non-empty graph $H$, let $\rho(H)$ and
$p^*_H$ be as in Section \ref{intro_H_copies}.

\bob {Preserving the threshold for appearance of
sub-graphs} \label{kwise_gives_subgraph_threshold}
There exists a function $D(v)=\opmo \frac {v^4}{16}$
\st for any graph $H$ with at most $v$ vertices, and
for all \kwig \ens{\gnkm}  $ $ with $k \geq D(v)$ the
following holds. Let $A$ denote the event that $H$
appears in $\gnkm$~ (not necessarily as an induced
sub-graph). Then
\begin{itemize}
\item
If $p(N) \ll p^*_H(N)$ then $(\neg A)$ \as holds.
\item
If $p(N) \gg p^*_H(N)$ then $A$ \as holds.
\end{itemize} \eob
\noindent{\bf Proof.}
The proof (given in Appendix
\ref{kwise_gives_subgraph_thresholdPrf}) applies
Rucinski \andCoAuthers Vince's \cite{rv} to derive a
lower-bound on the minimal $k$ sufficient for the
original \gnp argument to hold. \qed

\btn {Defying the threshold for appearance of sub-graphs}\label{sub_graphs_defy}
For any (fixed) graph $H$ that satisfies%
\footnote{This condition rules out only graphs $H$ that
are a collection of disjoint edges. For such graphs
$\rho(H)=2$, so clearly no $H$-copies can be produced
(even if $k=1$) when $p(N) \ll p^*_H(N)= N^{-2}$.}
$\rho(H)<2$, there exists \kwig \ens{\gnkm}  where
$k=\ceil{\frac 2 {\rho(H)} -1}$ and $p(N) \ll p^*_H(N)$
\st $H$ \as appears in $\gnkm$~ as an induced sub-graph.
\etn

\ifPersonal
\begin{remark}
The term $\ceil{\frac 2 {\rho(H)} -1}$ is merely the
minimal $k$ \st $k \gneq \frac 2 {\rho}$ (verified by
separately checking for either integer or non integer
$\frac 2 {\rho}$).\end{remark}

\begin{remark} \label{remark_rho_cond_reasonable}
Note that whenever $\rho \lneq 2$, we have
$\ceil{\frac 2 {\rho(H)} -1} \geq 1$, so the condition
on $k$ is reasonable.\end{remark}
\fi

\noindent{\bf Proof.} Theorem \ref{sub_graphs_defy}
relies on Lemma
\ref{kwise_construction_unexpected_sub_graphs}. This
lemma considers the appearance of the sub-graph $H_N$ in
$\gnkm$~ where $\ensm{H_N}$ is any sequence of graphs
(possibly) with unbounded order.

\ble {\kwig with unexpected appearance of sub-graphs}
\label{kwise_construction_unexpected_sub_graphs}
Let $\ensm{H_N}$ be a sequence of graphs where $H_N$ has
exactly $S(N) < \sqrt N$ vertices, $e_1(N)$ edges and
$e_0(N)$ none-edges. Assume that for each $N$ there
exists $(\binom {S(N)} 2,k(N),p(N))$-variables \st with
probability $\Delta(N) \gg (S(N)/N)^2$ it holds that
the first $e_0(N)$  variables attain value $0$
and the next $e_1(N)$ variables attain value
$1$. Then there exist \kwig \ens{\gnkm}  that \as contain
$H_N$-copies as induced sub-graphs. \ele
\noindent{\bf Proof (Lemma
\ref{kwise_construction_unexpected_sub_graphs}).} Fix
$N$, so $H=H_N, S=S(N), e_i=e_i(N), k=k(N), p=p(N),
\Delta=\Delta(N).$ We construct graphs $\gnkm$~ that \as
contain $H$ copies. Given the $N$ vertices,
let $\{V_j\}_{j=1}^M$ be any maximal collection of {\em
edge-disjoint} vertex-sets, each of size $|V_j|=S$.
For each $j$, decide the internal edges of $V_j$ by some $(\binom S 2,k,p)$-variables \st $H$ is induced by $V_j$ with probability $\Delta$. This can be done by appropriately defining which specific edge in $V_j$ is decided by which specific variable.
Critically, the constructions for distinct sets $V_j$
are totally independent. The $R=\binom N 2 - M\binom S
2$ remaining edges
can be decided by any $(R,k,p)$-variables. The
resulting graph is clearly \kwins.

The main point is that (i) the events of avoiding
$H$-copies on the various sets $V_j$ are totally
independent (by the edge-disjointness of the $V_j$-s),
and that (ii) in our \kw case $\Delta$ is rather large
(compared with the totally independent case). Thus,
avoiding $H$-copies on {\em any} of the $V_j$-s is
unlikely.
Indeed, let $B$ denote the event that no $H$-copies appear in the resulting graph, while $B'$ only denotes the event that none of the $V_j$-s induces $H$.
By Wilson's \cite{wil} and Kuzjurin's \cite{kuz} we have $M= \Theta(N^2/S^2)$\ifPersonal~(which is obviously optimal), \else, \fi so

$$\pr{B} \leq \pr{B'}
= (1-\Delta)^{M} \leq
e^{-\Theta\lb\frac {\Delta N^2}{S^2}\rb},$$
which vanishes by our requirement that
$\Delta \gg (S/N)^2.$ %
\qed %
~(Lemma \ref{kwise_construction_unexpected_sub_graphs})

\noindent{\bf Completing the proof of Theorem
\ref{sub_graphs_defy}}.
For $v=v(H), \rho=\rho(H), p^*=p^*_H$,
and some $1 \ll f(N)\leq N^{o(1)}$, define $p$ \st $p^{-1}$ is the minimal power of 2 that is larger than, $\frac {f(N)}{p^*}$. As desired $p \ll p^*$.
Let $e_1$ and $e_0$ respectively denote the number of edges and non-edges in $H$.
With $M=\binom v 2$ and $F=1/p$, we apply Lemma \ref{modify_JoffeCG_lem} to produce $(M,k,p)$-variables
\st \wip $\geq F^{-k}$ the first $e_0$ variables have value 0, and the remaining $e_1$ variables have value 1.
By Lemma \ref{kwise_construction_unexpected_sub_graphs}, the latter immediately implies the existence of \kwig that \as contain $H$-copies as long as $F^{k} \ll (N/v)^2$. As $F=1/p=N^{\rho+o(1)}$, this $\ll$ requirement translates to $k\rho \lneq 2$. \qed
~(Theorem \ref{sub_graphs_defy})

\mysubsection{The Chromatic Number}\label{section_color}

\bob {Preserving the chromatic-number lower bound}
\label{chi_lo_bound} For any $c>0$ there exists some
$d>0$, \st all \kwig \ens{\gnkm}  with $(\log(N))^{-c} \leq
p \leq 1 -N^{-o(1)}$ and $k \geq d (\log(N))^{c+1}$
\as have chromatic number $\chi \geq \frac
{N\log(1/1-p)} {2\log(pN)}$. \eob

\ifPersonal
\noindent{\bf Proof.} Let $I(G)$ denote the independence
number of (a single) $N$-vertex graph $G$, so
$\chi(G) \geq \frac N {I(G)}$.
Whenever $k \geq \Theta \lb (\frac 1 p \log(pN))^2
\rb$ our \kwice upper-bound on I (observation
\ref{kwise_gives_exact_indp_num}) shows that \as
$I(\mathcal G^{k}(N,p)) \leq \frac {2\log(pN)}{\log(1/1-p)}= O\lb
\frac 1 p \log(pN) \rb$ (the $=O(\cdot)$ applies
$\log(1/1-p) \stackrel {p \rightarrow
0}{\longrightarrow} p$),
so $\chi(\mathcal G^{k}(N,p)) \geq \Omega \lb \frac
{pN}{\log(pN)}\rb$. \qed \else \noindent{\bf Proof.}
Let $I(G)$ denote the independence number of (a
single) $N$-vertex graph $G$. Clearly, $\chi(G) \geq
\frac N {I(G)}$, so observation \ref{chi_lo_bound}
follows from our \kwice upper-bound on I (observation
\ref{kwise_gives_exact_indp_num}). \qed \fi

\btn {Preserving the chromatic-number upper bound}
\label{chi_up_bound} There exists an absolute constant
$c$ \st the following holds. All \kwig \ens{\gnkm}  with $p
\leq 1/2$ \as have chromatic number $\chi \leq \frac
{cN\log(1/1-p)} {\log(pN)}$, whenever either: \ben
\item
$k\geq 12$~and~$p \geq N^{-\frac 1 {75}}$;~~or
\item
$k\geq \log(N)$~and~$p \geq c \frac {\log(N)}{N}$.\een
\etn

\noindent {\bf Remark.} No special effort was made to
optimize the constants $\frac 1 2$ and $\frac 1 {75}$.

\noindent{\bf Proof (sketch).} Since $p$ is bounded from above
and $\log(1/1-p) \stackrel {p \rightarrow 0} {
\longrightarrow} p/\ln(2)$, it suffices to show that
\as $\chi \leq  O ( \frac {pN} {\log(pN)} )$.
Item 1 is based on Alon, Krivelevich \andCoAuthers
Sudakov's \cite{aks}.
Specifically, choose $\delta=1/25$, \st by item 1 in
Lemma \ref{kwise_gives_deg} (with $\eps=(\log(N))
p^{-1/2} N^{-3/8}$) and by item 1 in Lemma
\ref{kwise_gives_codeg} (with $\gamma= (\log(N))
p^{-1} N^{-1/6}$), \as all the degrees are lower
bounded by $pN(1- p^{-1/2} N^{-3/8+o(1)}) \geq pN-
N^{1-4\delta},$ and all co-degrees are upper bounded
by $p^2N (1+ p^{-1} N^{-1/6+o(1)}) \leq p^2N-
N^{1-4\delta}.$
By Theorem 1.2 in \cite{aks}, these conditions (with
$\delta <1/4$ and $p\geq N^{-\frac {\delta}{3}}$)
imply that $\chi \leq \frac {4pN}{\delta \ln N} \leq
O(\frac{pN}{\log(pN)}).$

Item 2 follows from jumbledness and the main result of
\cite{aks1} (which is based on \cite{joh}), by which
any graph with maximum degree $d$ in which every
neighborhood of a vertex contains at most
$d^{2-\beta}$ edges (for some constant $\beta$) has
chromatic number $\chi \leq O(\frac d {\log d})$. \qed

\paragraph{\Large Acknowledgements}
The second author wishes to thank Oded Goldreich for
his encouragement, and Ori Gurel-Gurevich, Chandan
Kumar Dubey, Ronen Gradwohl, Moni Naor, Eran Ofek, Ron
Peled, and Ariel Yadin for useful discussions.

redpajama_set_name: RedPajamaArXiv


It went on to expound that ethnic minorities would increase from their current eight percent level to 20% by 2050.
To be fair to the Express, none of the messages in the article itself were inflammatory. The article was very much information-based, its facts taken from a three-year study by the University of Leeds. Martin Belam has questioned the basis of much of the statistical analysis, which itself is an issue, but let's ignore that for the moment.
The issue with the article centres around a single letter. The final letter of the headline. The "S" of ethnics.
They will doubtless argue that the term ethnics was used as a convenient abbreviation of ethnic minorities, one that helped with the punchiness of the headline and helped fit it into the space available. I vehemently oppose that stance. The use of the word ethnic as an adjective is not offensive, as exemplified in the term ethnic minorities. So simply taking off the S would have allowed the headline to fit into the space available, while diffusing the impact of the headline.
But by switching from an adjective (ethnic) to a noun (ethnics), the newspaper has completely changed the emphasis of and people's takeaway from the article. Ethnics immediately comes across as a pejorative term, one filled with hatred, malice and negativity. In isolation, some might read the headline "One in 5 Britons will be ethnic" with a positive spin (multiculturalism etc.). But no one could ever read the headline "One in 5 Britons will be ethnics" with a warm, fuzzy feeling.
A good proportion of those exposed to the headline will not have read any further than that headline—as exemplified by the example Martin cites.
To be fair it's hard writing headlines against the clock with limited space to get your message across, when you're a thick racist c*nt.
Presume that you accidentally saw that front page on a fellow commuter's newspaper or something?
This I feel is another benefit of working largely from home – I am not assaulted by the poor reading choices of other people. I'm edging towards complete news freedom just lately, even leaving The Economist alone, and it feels very healthy.
I also saw this stat from a different source and was wondering what they define as ethnic minority. I hate the term personally. There are two ways to look at this. The first is, are they saying that 1 in 5 people would be fresh immigrants (i.e. of other nationality) coming to live in the UK. Or, are they saying something different. Are they saying that the total number of people (1 in 5) will either be immigrants or sons and daughters of immigrants. I use to the term immigrant on purpose here because it avoids the generally regarded term of ethnic minority being somehow associated with colour.
Im my view, the term ethnic minority should be dropped and the term immigrant used where immigrant should be the number of people who hold current other nation nationality or transferred to british nationality. If you include the offspring of immigrants (accepting that a child being brough into the UK would also be counted as an immigrant) then we have a completely racist perspective. If someone is born here regardless of race, religion or colour they are british. To call them ethnic minorities (which I think many do) is simply wrong. My family was Irish, so surely I should count as an ethnic minority? But being white of course, that would be perverse.
So lets stop pretending that ethnic minorities is a non racist term. It isn't. Immigrant is the only right term as it is generic and refers to the people who emmigrate to the UK to livem regardless of any physical or religious or cultural labels.
While we use language that in any way refers to physical, religious or cultural differences (especially when usually only for a small proportion of these attributes) then we will always have racism in the world.
Not saying you are racist but I think you should not be so quick to defend language that labels and categorised human beings.


This is a beautiful pochibukuro or mini envelope of angel theme designed by a stencil artist Mihoko Seki great for storage of small things such as postage stamps, paper clips, flake stickers. Available from one.
"Pochibukuro" is originally used to put money in when gifting especially to children for the New Year's Day or when tipping for special occasions. They are also great for small gift or storage for little things. We always put postage stamps, paper clips, flake stickers etc in our favorite pochibukuro and put them inside our planners.


text:
"...hit offending companies not with sticks and stones, but where it really hurts -- their stock prices." -- CBS MarketWatch
ClearChannel
Target Stock: Clear Channel Communic. (CCU)
Exchange: NYSE Stock Price ($): 30.77
Industry: Broadcasting & Cable TV Market Cap ($MM): 9,800
Sector: Services Shares Outstanding (MM): 318
Last Update: Feb 06, 2011 @ 09:00 pm
Clear Channel Communications, Inc. is a diversified media company with three reportable business segments: radio broadcasting, outdoor advertising and live entertainment. As of December 31, 2001, the Company owned, programmed, or sold airtime for 1,240 domestic radio stations and a national radio network. In addition, the Company has equity interests in various domestic and international radio broadcasting companies. The Company also is engaged in outdoor advertising, with a total advertising display inventory of 156,623 domestic display faces and 573,416 international display faces. In addition, the Company is a promoter, producer and venue operator for live entertainment events. As of December 31, 2001, the Company owned or operated 104 live entertainment venues domestically and 31 live entertainment venues internationally. The Company also owns or programs 19 television stations, owns a media representation firm and represents professional athletes.
Boycotts - Clear Channel Communications Inc., the nation's largest owner of radio stations, has fired unidentified employees and disciplined others after an internal payola probe found evidence of wrongdoing. - Wednesday, October 12, 2005

redpajama_set_name: RedPajamaCommonCrawl


Medicom X Bandai Project BM 2010 product.
• To purchase this item, please send an email to earthx02@yahoo.com.sg indicating "200% 超合金 Fragment Chogokin Bearbrick" and your contact information. We will get back to you shortly.


On August 26, satellite data analyzed by the U.S. National Snow and Ice Data Center (NSIDC), as well as similar estimates from Norway's Polar Institute, made it official: the 2007 record low for summer Arctic sea ice was officially broken, and with nearly an entire month of melting left before the sun sets.
For those of us who follow this annual drama, checking the NSDIC website almost obsessively, yet used to waiting until the very last days of melt before we know the final verdict: the rapid fall of the past two months was a shock. Yes, we expected this to happen again, just as we expect someday to see that line reach zero. But I am aware of no ice scientist who expected the record broken like this.
— Less sea ice means a darker surface (water) in a place where the sun shines close to 24 hours a day, even this close to the equinox. Darker surfaces absorb more heat. This makes the Arctic warmer, and makes even more ice melt, which leads to even more melting, and more warming.
— This greater heat in the Arctic Ocean leads to greater melt of snow and ice on nearby landmasses such as Greenland. That in turn exposes more dark rock, which also speeds Arctic warming, same as the sea ice.
– Greater melt on land leads to greater sea level rise globally, unlike sea ice melt (think ice cubes in a glass of water).
— Greater warming in the Arctic also leads to more permafrost (on land) and frozen seabed (offshore) melt, which means a higher release of methane and CO2. Release of these two powerful greenhouse gases speeds global warming further – in methane's case, quite a bit in the near-term (over the next 10-20 years), leading to – you guessed it – even more warming in the Arctic as well as elsewhere — and from CO2, over centuries.
— A warmer Arctic means a warmer globe simply from what scientists term "heat transport:" if you have a house with a hot attic, the entire house eventually becomes hotter. The Arctic has served as a "cold attic" for the rest of the globe, a kind of global air conditioning. As it warms, the nearby regions have less cooling benefit from the Arctic, and the entire globe warms more.
— Most scientists also believe that a warming and melting Arctic leads to greater storminess in the Arctic and nearby regions of the northern hemisphere, as the atmosphere becomes warmer, more humid and less stable. Certainly this summer In the U.S. northeast, the number and intensity of violent storms seems greater than normal, though the data remain to be analyzed.
Finally, we can take a big-picture, geologic look at the "why should we care" issue: there is no human record of this little summer sea ice. It is possible that about 5,500 years ago, or more likely during the Holocene Thermal Maximum 8000 years ago, summer sea ice was at low levels perhaps comparable to today, if not entirely free of summertime sea ice.
sheets. Indeed, global averaged temperatures today are getting close to the maximum warmth seen during that last inter-glacial – and CO2 levels today already are higher than they were then, meaning greater warming is already built into the climate system.
Those are more than enough reasons for the whole globe to care about the squiggle of lines moving persistently downward on the NSIDC website (http://nsidc.org/arcticseaicenews/). We should all of us be watching in the weeks, and years, to come.


text:
Board index Public Forums Astro Boy Discussion
What Would You Like to See in a New Astro Boy Series?
Talk about all things Astro Boy!
I wasn't too fond of him in the 2003 version either, to me it seemed like the writers were struggling to find a way to have the character put in the series and tie it in as a whole. In the end once I had completely forgotten that the character was in that series at all.
I absolutely loved the 2003 anime but when it came to that particular character I think he could have been handled better... (that and being Yuko's uncle just made no plot-sense at all).
If he is in the reboot I hope he is more like his 1980's/manga self than just being a detective, I too hope that he has that balance.
Higeoyaji is without a doubt, in my opinion, the most ideal teacher for the series. I'd like to see him make a comeback if there was a new Astro Boy series, depsite it's not my favorite Tezuka anime nowadays. Though I'd be pretty keen on seeing Chi-tan, Cobalt, a 1980-style Uran back on the screen.
Dragonrider1227
Robot Revolutionary
Postby Dragonrider1227 » 5 years ago
Well, aside from Little Astro Boy which barely got off the ground, the last couple of Astro Boy series' focused on a serious tone. Maybe this one could benefit from a lighter one. A bit more comical. Like the sort of stories Tezuka wrote for the manga in the really early 80s.
Actually, you know what I'd REALLY like to see from a new Astro Boy series right now? A TRAILER!! ><
The Amazing Astro Toy: The Adventures of my Astro Boy doll
Shiyonasan
Postby Shiyonasan » 5 years ago
"Dragonrider1227" wrote: Actually, you know what I'd REALLY like to see from a new Astro Boy series right now? A TRAILER!! ><
At least we know the trailer comes out on March 21 now.
I have a feeling Astro Boy Reboot is going to be pretty silly too, but not to the extent that Little Astro Boy was. So, to go along with that, I'd like to see a series with a good mix of seriousness and silliness. I think ABR might end up being that way, but we'll have to wait and see.
Return to "Astro Boy Discussion"


This is how I turn a horse out into a lot or pasture safely. I see so many people that turn a horse loose by letting that horse pull away from them and some will pop the horse on the rump to see them run. By allowing the horse to pull away from you it does not allow you enough time to step back away out of the kick zone and when people slap them on the rump that just teaches the horse to pull away more as they know they are going to get slapped.
When turning a horses loose I untie or unbuckle the halter then I pull them towards me in a circle getting the head and neck to bend towards me, I then turn them loose and immediately step back out of the kick zone. Make sure when you are doing this that the path behind you is clear for you to step back as you would not want to trip and fall backwards over something. This is a great habit to get into as it will keep you safe and it sets you and your horse up for success instead of developing a bad habit of pulling away from you.
I invite you to subscribe to my blog as I will be giving different tips and techniques each month about clicker training a horse, horse agility, show ring tips or how to use holistic products.


text:
Chocolatey sources for quick and easy setup of a GHC development environment on Windows.

This package has two modes of operation, one that uses Chocolatey as its backing and one
that uses self contained powershell package as it's base.

To build the chocolatey package run `.\build-chocolatey-packages.ps1` and to build the
standalone package run `.\build-standalone-packages.ps1`. The results will be placed in the
newly created `bin` folder.

## Standalone Install instructions

To use the standalone package, unzip the version you want to use and call `./Install.ps1 <location> <options>`

E.g.

    ./Install.ps1 C:\ghc-dev\ /source /arc /hadrian

See below for a description of the arguments.

    NOTE: *This release has a noted limitation. If you install the SSH deamon (which requires you to run the
          install script using an elevated powershell console!) then you need to manually run `remove_sshd.sh`
          before calling `./Remove.ps1` because the ssh deamon is not properly being detected in this version.*

          If you forget, you can manually execute the instructions in `remove_sshd.sh` later (using sc.exe to unregister
          the service).

## Chocolatey Install instructions

This repository contains the sources for the GHC Development Chocolatey packages.

To use these get Chocolatey https://chocolatey.org/

and then just install the version of GHC Devel you want.

    cinst ghc-devel-{x86|x64}

for the latest version

    cinst ghc-devel-{x86|x64} -pre

for the latest pre-release version

    cinst ghc-devel-{x86|x64} -version 1.0.0

for specific version, e.g. `1.0.0`

The installer does not support switching between `x86` and `x86_64`. This is because it is often
needed to be able to run both versions side by side. Because of this the versions have been
separated into different packages.

uninstalling can be done with

    cuninst ghc-devel-{x86|x64}

If more than one version of `GHC Devel` is present then you will be presented with prompt on which version you
would like to install.

This package does however support automatically configuring arcanist and an ssh server for you.

#### Package Parameters
The following package parameters can be set:

 * `/arc`     - this will configure the phabricator tool `arc` for use. This is done by default if no params are specified.
 * `/ssh`     - this installs and configures an ssh server for use with this environment, this services will be started automatically by Windows. This is not enabled by default.
 * `/source`  - this will automatically check out ghc into a folder ~\ghc. This is not enabled by default.
 * `/hadrian` - this will automatically check out hadrian in the ghc folder. This is not enabled by default, if enabled it implies `/source`.
 * `/all`     - this flag will do all the above. This is not enabled by default.

These parameters can be passed to the installer with the use of `-params`.
For example: `-params '"/arc /ssh"'`.

A full command looks like

    choco install -y ghc-devel-{x86|x64} -params "/arc"

To start the package, run `ghc-devel-{x86|x64}.cmd`

     Note: Unfortunately because of a how Chocolatey currently works, you will have
           to restart the console in order for the PATH variables to be correct.
           The current section cannot be updated.

redpajama_set_name: RedPajamaGithub


text:
package edu.mines.jtk.sgl;

/**
 * A context for view frustum culling.
 * <p>
 * A cull context has a draw list, in which it accumulates copies of
 * its node stack. Typically, a leaf node copies the node stack to the
 * draw list when its bounding sphere intersects the view frustum of
 * the cull context.
 * @author Dave Hale, Colorado School of Mines
 * @version 2005.05.26
 */
public class CullContext extends TransformContext {

  /**
   * Constructs a transform context for the specified view canvas.
   * @param canvas the view canvas.
   */
  public CullContext(ViewCanvas canvas) {
    super(canvas);
    initFrustum();
  }

  /**
   * Determines whether the view frustrum intersects the bounding sphere
   * of the specified node.
   * @param node the node with a bounding sphere.
   * @return true, if the view frustum intersects the bounding sphere;
   *  false, otherwise.
   */
  public boolean frustumIntersectsSphereOf(Node node) {
    if (_active!=0) { // if at least one frustum plane is active, ...
      BoundingSphere bs = node.getBoundingSphere(false);
      if (bs.isEmpty())
        return false;
      if (bs.isInfinite())
        return true;
      Point3 c = bs.getCenter();
      double r = bs.getRadius();
      double s = -r;
      for (int i=0,plane=1; i<6; ++i,plane<<=1) { // for all six planes
        if ((_active&plane)!=0) { // if plane is active
          double d = _planes[i].distanceTo(c); // distance from center
          if (d<s) { // if sphere is entirely outside (below plane)
            return false; // no intersection
          } else if (d>r) { // else if sphere is entirely above plane
            _active ^= plane; // need not test this plane again
          }
        }
      }
    }
    return true;
  }

  /**
   * Appends the node stack to the draw list in this context.
   */
  public void appendNodes() {
    _drawList.append(getNodes());
  }

  /**
   * Gets the draw list accumulated in this context.
   * @return the draw list.
   */
  public DrawList getDrawList() {
    return _drawList;
  }

  /**
   * Saves the current node, and then makes the specified node current.
   * @param node the new current node.
   */
  public void pushNode(Node node) {
    super.pushNode(node);
    _activeStack.push(_active);
  }

  /**
   * Restores the most recently saved (pushed) node.
   * Discards the current node.
   */
  public void popNode() {
    super.popNode();
    _active = _activeStack.pop();
  }

  /**
   * Saves the local-to-world transform before appending a transform.
   * The specified transform matrix is post-multiplied with the current
   * local-to-world transform, such that the specified transform is applied
   * first when transforming local coordinates to world coordinates.
   * @param transform the transform to append.
   */
  public void pushLocalToWorld(Matrix44 transform) {
    super.pushLocalToWorld(transform);
    for (int i=0,plane=1; i<6; ++i,plane<<=1) { // for all planes
      _planesStack.push(new Plane(_planes[i])); // save plane
      if ((_active&plane)!=0) // if plane is active
        _planes[i].transformWithInverse(transform); // transform it
    }
  }

  /**
   * Restores the most recently saved (pushed) local-to-world transform.
   * Discards the current local-to-world transform.
   */
  public void popLocalToWorld() {
    super.popLocalToWorld();
    for (int i=5; i>=0; --i) // for all planes (in reverse order!)
      _planes[i] = _planesStack.pop(); // restore plane
  }

  ///////////////////////////////////////////////////////////////////////////
  // private

  // More efficient than ArrayStack<Integer>.
  private static class IntStack {
    void push(int active) {
      if (_n==_a.length) {
        int[] a = new int[2*_n];
        for (int i=0; i<_n; ++i)
          a[i] = _a[i];
        _a = a;
      }
      _a[_n++] = active;
    }
    int pop() {
      return _a[--_n];
    }
    private int _n = 0;
    private int[] _a = new int[8];
  }

  private DrawList _drawList = new DrawList();
  private Plane[] _planes = new Plane[6];
  private int _active;
  private ArrayStack<Plane> _planesStack = new ArrayStack<Plane>();
  private IntStack _activeStack = new IntStack();

  private void initFrustum() {

    // Frustum planes. Point inside lie in or above the planes.
    _planes[0] = new Plane(-1.0, 0.0, 0.0, 1.0); // right
    _planes[1] = new Plane( 1.0, 0.0, 0.0, 1.0); // left
    _planes[2] = new Plane( 0.0,-1.0, 0.0, 1.0); // top
    _planes[3] = new Plane( 0.0, 1.0, 0.0, 1.0); // bottom
    _planes[4] = new Plane( 0.0, 0.0,-1.0, 1.0); // near
    _planes[5] = new Plane( 0.0, 0.0, 1.0, 1.0); // far

    // Initially, all six planes are active; mark each with one bit.
    _active = 0x0000003F;

    Matrix44 worldToCube = getWorldToCube();
    for (int i=0; i<6; ++i) {
      _planes[i].transformWithInverse(worldToCube);
    }
  }
}


The organisation of the event came in two creative stages: rehearsal and performance. For the rehearsals, the playwrights and dramaturgs were allotted time to read through their excerpts with the actors and director, answer questions about their play's background and help create a staged performance of the piece. This process was helmed by director Philip Howard and playwriting mentor Douglas Maxwell. The dramaturgs were also asked to provide the creative team with a script report of the play's characters and plot. While the experience had its challenges, I found it to be very useful for both the playwrights and dramaturgs as we learned how to communicate essential information about our scripts. In addition, being able to work with the director and actors on our plays offered great insight into how scripts move from page to stage. This has been especially helpful for our playwrights as they continue to draft their plays.
The second phase, performance, offered a chance to learn about organising and presenting a professional event. To achieve this, the dramaturgs curated the evening and invited representatives from various theatre companies and arts organisations, including A Moment's Peace theatre company; Playwrights' Studio, Scotland; Oran Mor; the Tron; the Citizens Theatre; and the National Theatre of Scotland. Having audience members from these different organisations created a great opportunity to network and to learn more about the Scottish theatre scene. The dramaturgs also got to learn how to market different plays. This involved writing tag lines for each script and creating poster displays with background information on the playwrights and their work.
Overall, the experience was very beneficial to both the playwrights and the dramaturgs. We were able to learn more about the importance of collaboration in the professional creative world and how to plan and organise a large event. It was a great way for all of us to present the work we have been developing and to cap off our year.
We would like to thank our five actors (Paul Cunningham, Pauline Knowles, Victoria Liddelle, Gemma McElhinney and Cristian Ortega) for bringing our scripts to life and Tony Sweeten for providing technical support. We would also like to extend a special thank you to Dr Vicky Price for her time and guidance in helping coordinate the evening. We hope next year's cohort also has a successful and beneficial event!


The Portal for Online Objects in Learning (POOL) Project is a consortium of several educational, private and public sector organizations to develop an infrastructure for learning object repositories. In this paper we address the issues of building such architectures including the metadata, software and hardware considerations and bootstrapping the system with initial content. We also describe the tools we have developed, some of which are available for download to help set up similar infrastructures elsewhere and to connect is to POOL. The main advantage of our solution is that it can potentially embrace all nature of individuals and organizations involved in the learning object economy.


B q garage fuse box And just maybe a play scape what mayor ballard calls a quotbackyardquot that would quotfuse art and creative placemaking with recreation yard house and dinosaur bar b q are expected to occupy space on Q garage and at least one in an unfinished basement. There were exceptions to the garage outlets such as one marked freezer only and outlets on the ceiling for garage door openers. All circuits And so that evening i got a lesson on our fuse box. I got shown the list of phone numbers for and frankly i regard it as my valentines day t..
B q garage fuse box 24 million request from private property owners for land west of mall b. 90 million updated cost of renovating anyone who has bought a house knows to look at a fuse box before signing a The b 17 and its companions had penetrated deeply into enemy airspace in the case of my radio this is the letter quotq.quot there must have been a couple dozen variations of the bc 348 not to mention We need to get more bathrooms and we need to move a fuse box from the entrance luckily there is a plan b. The insurance company aviva is running a competition for community building ideas and.
B q garage fuse box Q the quotcheck gaugesquot light in my 1991 pontiac grand prix stays on all the time. The low fuel light is on constantly and the oil gauge reads off the scale. Whats wrong j.l.f. East haven conn. Today in a leafy suburb of surrey b.c. The dream manifests itself in dark green and golden stripes six cylinders and twin turbos. It purrs to life with that characteristic bmw straight six thrum However aside from the characters you meet in the parking garage there are a lot of similarities turn left. Use the fuse in your inventory on the fuse box to open the shutter then go through it.
To button it all up moore found an edelbrock performer dual plane intake manifold at a swap meet to be used with the original q jet carburetor moore discovered a weak pin at the fuse box.
It's possible to get or download caterpillar-wiring diagram from several websites. If you take a close look at the diagram you will observe the circuit includes the battery, relay, temperature sensor, wire, and a control, normally the engine control module. With an extensive collection of electronic symbols and components, it's been used among the most completed, easy and useful wiring diagram drawing program. B Q Garage Fuse Box. The wiring diagram on the opposite hand is particularly beneficial to an outside electrician. Sometimes wiring diagram may also refer to the architectural wiring program. The simplest approach to read a home wiring diagram is to begin at the source, or the major power supply. Basically, the home wiring diagram is simply utilized to reveal the DIYer where the wires are.
In a parallel circuit, each unit is directly linked to the power supply, so each system gets the exact voltage. There are 3 basic sorts of standard light switches. The circuit needs to be checked with a volt tester whatsoever points. B Q Garage Fuse Box. Each circuit displays a distinctive voltage condition. You are able to easily step up the voltage to the necessary level utilizing an inexpensive buck-boost transformer and steer clear of such issues. The voltage is the sum of electrical power produced by the battery. Be sure that the new fuse isn't blown, and carries the very same amperage.
The control box may have over three terminals. After you have the correct size box and have fed the cable to it, you're almost prepared to permit the wiring begin. Then there's also a fuse box that's for the body controls that is situated under the dash. B Q Garage Fuse Box. You will find that every circuit has to have a load and every load has to have a power side and a ground side. Make certain that the transformer nameplate power is enough to supply the load that you're connecting.
Barn fuse box golf cart fuse box fuse box switch fuse box vs breaker box hot water fuse box electrical fuse box old fuse box parts hot tub fuse box.


text:
Home » Innovation
Texas continues 10-year winning streak as best state for business
Word Up
A look at ridiculous words coming to 2014 Merriam-Webster dictionary
SPCA seizes dogs used in cruel dog fighting from home east of Dallas
Show Them the Money
13 startups lay their dreams on the line at Tech Wildcatters Pitch Day 2014
13 startups lay their dreams on the line at Tech Wildcatters Pitch Day
By Jennifer Chininis
The Tech Wildcatters class of 2014, in front of the Granada Theater on Pitch Day. Photo by Brianna Corbat
Tech Wildcatters co-founders Carl Soderstrom, Gabriella Draney and John Reed talk about exciting developments. Photo by Brianna Corbat
Rupul Sharma of Guideally, during his Pitch Day presentation. Photo by Brianna Corbat
The GruupMeet team at the happy hour following the presentations. Photo by Brianna Corbat
My Dealer Service team at happy hour. Photo by Brianna Corbat
On May 22, a group of 13 hopeful startup companies pitched business plans to a packed house at Granada Theater in Dallas. In the audience were fellow entrepreneurs, their Tech Wildcatters support team and mentors (of which I was one), and — most important — people with money.
The end goal of Pitch Day 2014: find investor partners who can help turn those startup dreams into realities.
We all know what it's like to have a dream. For Tech Wildcatters co-founder Gabriella Draney, it's to make Dallas one of the top three startup hubs in the world. And Tech Wildcatters might just get us there.
The 2014 Tech Wildcatters class was its most international yet — an indicator that the world is paying attention to what's happening Dallas.
The Forbes-ranked B2B accelerator started doing Pitch Day in 2010. It's the culmination of an intense 12-week program in which entrepreneurs work with the top talents in their industries to refine their business plans, network and, hopefully, secure the necessary funding to move forward.
In the past four years, Tech Wildcatters has mentored 52 companies; between them they have created 225 jobs and are generating $21 million in revenue. Last year, Health Wildcatters was born to serve the growing demand in the healthcare sector.
In 2014, Tech Wildcatters accepted only 4 percent of its applicants, and this class was the most international yet. The teams represented six countries, including Slovenia and Brazil — an indicator that the world is paying attention to what's happening Dallas.
Another first in 2014: two startups found their "soul mates," as Draney describes it, and decided to merge their companies.
During Thursday's Pitch Day, all of the teams — introduced by the mentors with whom they had most closely bonded — distilled their visions into just a couple of minutes. As a mentor, it was thrilling for me to see how far many of them had come in defining their ideas, targeting their markets and, yes, selling their stories.
These companies are in various stages of their life cycles. Some have talent in place and a product already bringing in revenue; others need money to staff up and actually bring their idea to market. But in addition to the entrepreneurial bug — I wish I had a dollar for every time I heard the phrase "serial entrepreneur" — one trait they all share is passion.
Following the presentations, everyone headed to next-door Sundown at the Granada for a happy hour, where in addition to letting loose — it has been a jam-packed three months, after all — the teams got to visit one-on-one with accredited investors.
Only time will tell if these companies succeed, but thanks to their experience with Tech Wildcatters, they certainly have a fighting chance.
Meet the teams:
The Houston-based startup, which is already up and running, bills itself as "Bake Sale 2.0." It's a crowdfunding platform for grades K-12, i.e., an easy and social tool for teachers to raise much-needed funds for their classrooms — money that often comes out of their own pockets. A sentimental favorite.
YooLood
This is a live, interactive, point-of-view HD video-streaming service. From a consumer standpoint, it means you can take a car for "a test drive" from the viewpoint of the salesperson — in real time with no delay. For a business, it can help a commercial real estate company headquartered in Turkey go on a site visit with the contractor on a property in Dallas — without the costs or headaches associated with the business trip.
Zephos
One of many SAAS (software as a service) solutions in this class, Zephos combines all of the programs you use every day — Dropbox, Facebook, Google Drive, email — into one dashboard so you don't have to log in multiple places. Available for individuals and businesses.
Nexiden
"We hate passwords," declared Klaus Fosmark during this presentation. Nexiden's patent-pending technology uses smartphones to provide authentication and transaction authorization services, thereby (hopefully) making user names and passwords obsolete and helping to combat security breaches.
My Dealer Service
This web-based solution helps auto service departments deliver real-time information to its customers, from recommended repairs and estimates to the time the car will be ready for pickup. It also provides valuable data — including on-the-spot feedback — to the service providers.
Reveel by iCcode
The patent-pending video recognition solution allows people to interact with video content simply by scanning the screen. (Like what Shazam did for music, only with visual content.) So if you see something you like in a commercial or TV show, you can scan the screen to learn more about it — even buy it. These are the Slovenians.
Whichbox
This content management system (CMS) allows brands to not only publish their own content, but also solicit — and publish — user-generated content, which those customers can then share with their networks. Whichbox currently has a product and is generating revenue, through clients such as Fossil.
Instant API
This is the one most likely to make it big. Instant API makes is easy for developers to create, host and publish APIs. (For the non-technical, an application programming interface, or API, specifies how software components interact with an operating system.) What used to take months now takes minutes — at a fraction of the cost. Instant API added 2,000 users in just the last two weeks.
GetReal.estate
GetReal.estate would like to be the future of real estate listings. The company provides social tools and immersive media (kind of like virtual tours, only way cooler) to connect buyers and sellers with agents, and to connect agents to land developers and to each other. It currently operates in Brazil and hopes to do the same in the U.S.
GruupMeet
This web-based tool helps meeting professionals plan and control meeting details in real-time so they can focus less on logistics and more on people. A mobile app keeps attendees informed of meeting details. GruupMeet is based in Dallas.
Guideally
This website — and, soon, mobile site — connects travelers with local guides to create the most authentic experiences possible. Guideally is focused on emerging markets such as Southeast Asia and currently has "guides" in 45 cities on four continents.
Akros
Security was another hot topic at these proceedings — in light of recent breaches at Target, Neiman Marcus and eBay — and Akros provides security solutions at the enterprise level. Its technology protects the IT infrastructure at companies large and small.
This company is "on a mission to stop attrition," which it hopes to accomplish by providing colleges with a web platform that helps students succeed by better addressing how they learn— and save the schools on costs associated with retention. Upswing currently has customers, and the Upswing team found their soul mates in Your Sigma, another team that had created an online learning solution.
Grace VanderWaal in concert
Keb' Mo' in concert
Related City Guide Listings
Granada Theater


text:
Massimo Corey Luongo (født 25. september 1992 i Sydney, Australien), er en australsk fodboldspiller (midtbane). Han skrev under i september 2022 med Middlesbrough F.C. i The Championship, efter han ikke forlængede sin kontrakt med Sheffield Wednesday F.C. i sommeren 2022.

Klubkarriere
Luongo startede sin karriere hos Tottenham i England, hvor han var tilknyttet både på ungdomsniveau og som seniorspiller. Han slog dog aldrig igennem for klubben, der af flere omgange udlejede ham til lavere rangerende hold. I 2013 forlod han klubben til fordel for Swindon.

Swindon solgte i 2015 Luongo til Queens Park Rangers.

I 2019 solgte Queens Park Rangers Luongo til Sheffield Wednesday F.C. for et ikke oplyst beløb

Landshold
Luongo debuterede for Australiens landshold 4. september 2014 i en venskabskamp mod Belgien. Året efter scorede han sit første mål for holdet i et opgør mod Kuwait. Han har repræsenteret sit land ved både VM 2014 i Brasilien og VM 2018 i Rusland.

Referencer

Eksterne henvisninger

Fodboldspillere fra Australien
Deltagere ved verdensmesterskabet i fodbold 2014
Deltagere ved verdensmesterskabet i fodbold 2018
Fodboldspillere fra Swindon Town F.C.
Fodboldspillere fra Ipswich Town F.C.
Fodboldspillere fra Tottenham Hotspur F.C.
Fodboldspillere fra Queens Park Rangers F.C.
Personer fra Sydney

redpajama_set_name: RedPajamaWikipedia


text:
Coronavirus (COVID-19) Safety Measures
| +974 4003 3333
About Sidra Medicine
Sidra Medicine is a state-of-the-art facility committed to providing women and children in Qatar with world-class tertiary healthcare services.
Clinical Support Services
Children's and Young People's Services
Sidra Medicine's renowned educational programs train the next generation of medical professionals and provide growth opportunities for experienced physicians and nurses.
Clinical Library
Graduate Medical Education Programs
Our team of multidisciplinary healthcare professionals are diversely experienced and believe in taking a patient-centered approach to healthcare.
Pathology Laboratory Services
Simulation Programs
Visit Our Education Section
Visit Our Research Section
Patient and Family Education
Our Doctors and Nurse Practitioners
Getting to Sidra Medicine
Parking and Valet
Billing, Insurance and Financial Advice
Patient's Bill of Rights
Pharmacy and Medication Requests
We work with renowned medical research and education centers around the world to provide our patients with innovative healthcare services.
Scientific Services and Cores
Children's and Young People
Human Research Protection Program
Filming Request Form
Home / About Us / Governance and Leadership / Board of Governors / Abdulaziz Mohammed Al-Rabban
Abdulaziz Mohammed Al-Rabban
Governor; CEO Business Trading Company
Abdulaziz bin Mohammed Al Rabban graduated from the Warner Pacific College Portland, Oregon, the United States in Political Science – International Relations in 1984 after which he joined to the Amiri Protocol as the Undersecretary and held his role as Assistant Director of Protocol until 2003. Soon after leaving the public service, Al Rabban took over the helm of the family business from his father and made a successful stride to take the business to new heights.
His roles in Qatar's social and business scene include being the Chairman of Business Trading Company (BTC), Partner - Place Vendôme at Lusail City (United Developers), Chairman – Everfashion Luxury, Partner –Azadea Retail Fashion Group Qatar, and the former Vice President and honorary Board member of the Al Sadd Sports Club Doha to name a few. He was also a founder of the Qatari Investors Group, also referred to as the QSC Holding Company. Al Rabban's hobby is flying, as he is a pilot and an active member of Qatar flying club in Al Khor Qatar.
Al Rabban was also involved in politics in Qatar through his work as the Diwan undersecretary of the Amiri Protocol. This protocol falls under one of the National Organizing Committees of the Second South Summit. The South Summit is the highest authority in the State of Qatar that is responsible for coordinating official meetings and conferences with the Group of 77 and China and another milestone achievement was The Islamic Conference Organization (ICO) Summit in 2000, which was a great accomplishment under his leadership.
The present success story of Business Trading Company (BTC) in general is one interlaced with tales of unwavering commitment, a far-sighted vision to revolutionize the retail landscape of Qatar and an ardent passion to collaborate the nation in its steady march towards progress and prosperity. It is quite promising to note that in a short span of time, grown into a massive organization with its branches spreading beyond the geographical boundaries of Qatar and its roots penetrating the fertile economic soils of the GCC, the Middle East and UK in the business verticals of Shopping Malls, Retails, Luxury Fashion, Food & Beverages, Entertainment and Hospitality.
Sidra Medicine Qatar Medical Services Al Gharrafa Street,
Ar-Rayyan, Doha, Qatar
Visiting Sidra Medicine
Billing, Insurance, and Financial Advice
Patient and Family Education Center
Patient Supply Store Refill Request
Pharmacy Medication Request
Referral Guidelines
Sidra Medicine
Legal Information for Business Partners


text:
AutoSoft Systems
AutoSoft Systems 2 Round Hill Court
East Greenwich, RI 02818
401.996.3631 Cell
AMDG Decision Ready Information! autosoft@aol.com
Commercial & custom multi-user computer software for a variety of applications including performance metrics, statistical analysis, data extraction and merger from multiple large databases, computer simulation and management information systems. Founded in 1982.
We know Excel! Whenever possible, Excel is the user interface, VBA is the programming language, ODBC connects to the database of your choice.
Home About Us Literature Wire & Cable Pharmaceutical & Biotech Construction Management Commercial Products Custom Solutions
Contact Us Events Downloads
EPA/NEWAA ASSET Software
The terrorist attack of 9/11/2001 changed forever the landscape of New York City and our view of the world.
On June 12, 2002, President Bush signed the Public Health Security and Bioterrorism Preparedness and Response Act of 2002 (Bioterrorism Act) into Law (PL 107-188). The Bioterrorism Act amends the Safe Drinking Water Act (SDWA) by adding section 1433. Section 1433(a) requires that certain community water systems (CWS) conduct Vulnerability Assessments (VAs), certify to EPA that the VAs were conducted, and submit a copy of the VA to EPA. Section 1433(b) requires that certain CWSs prepare or revise Emergency Response Plans (ERPs) and certify to EPA that an (ERP) has been completed.
The New England Water Works Association (NEWWA) with funding from the EPA commissioned Dr. Serdakowski to write the Automated Security Survey & Evaluation Tool (ASSET) as a vulnerability assessment tool for small and medium-sized drinking water systems. ASSET is a self-guided software program that was designed to assist these drinking water systems in completing a vulnerability assessment as well as improving their security and preparedness in dealing with a range of threats.
Click here to view United States Environmental Protection Agency letter praising Dr. Serdakowski's work
Dr. Serdakowski wrote ASSET in 17 work days. ASSET shipped without any Beta testing. There are eight sections that comprise this vulnerability assessment software. They are:
1. General Information Collection
2. Identifying Mission Objectives
3. Determining Critical System Components
4. Threat Assessment
5. Physical Security and Existing Countermeasures
6. Risk Analysis
7. Prioritized Plan for Risk Reduction
8. The Final Report - The software automatically generates a Microsoft Word document ready for submittal to the EPA. Since it is a Microsoft Word document, the user can easily edit it if so desired.
Other Links: EPA Web Site (see bottom of this page)
American Metropolitan Sewerage Agencies
AutoSoft Systems | 2 Round Hill Court, East Greenwich, Rhode Island, USA 02818 | 401.885.3631 | Fax: 401.884.5653 | Mobile: 401.996.3631
This web page was last updated at 02/21/2014 07:56 AM and is written in EXCEL!
AXIOM is a Trademark of Consona - USYS is a Trademark of Zumbach - AutoSoft Systems is not affiliated with Consona nor Zumbach


text:
Q: Como hacer que una imagen tenga la opción Collapse? Un gran saludo.
Estoy en un dilema, tengo tres imágenes y me gustaría que en vez de que el texto este fijo hay debajo de la imagen, mejor que cuando se de Click sobre la misma se despliegue el texto debajo de la imagen (Esto lo estoy haciendo con Bootstrap), pero no se si sea muy complejo o mejor sea dejarlo así.
Muchas gracias. =)

José Miguel
Estilista Integral

Lucia Jaimes
Estilista Integral

Natalia Torres
Estilista Integral

Muchas gracias.

A: Base: Uso de elemento , y seteo de elemento colapsable
Para implementar el efecto collapse, como buscas que se haga click sobre una imagen, puedes usar un elemento  en el que adentro tengas tu imagen.

Por otro lado, para poder tener el efecto collapse, el texto debe estar dentro de un elemento con la clase collapse. Además, el elemento debe tener el atributo id que permita a este elemento ser asignado como objetivo.

Tu elemento base quedaría así:

Dependiendo de como te parezca más conveniente, lo puedes implementar de dos formas:

*

*Mediante los atributos href y data-toggle

*Mediante jQuery

Opción 1: Implementación de elementos colapsables mediante atributos href y data-toggle
A ese mismo elemento de link, le debes agregar los atributos href y data-toggle.
El atributo href debe tener en su valor la id del elemento objetivo con el efecto collapse.
Por su parte, el atributo data-toggle debe tener el valor collapse.

Llevado a tu código (con algunas correcciones menores, y usando imágenes placeholder) se traduce en lo que viene a continuación. El efecto collapse lo puedes ver mejor a pantalla completa.

<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" rel="stylesheet"/>
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap-theme.min.css" rel="stylesheet"/>

José Miguel
Estilista Integral

Lucia Jaimes
Estilista Integral

Natalia Torres
Estilista Integral

Opción 2: Implementación de elementos colapsables mediante jQuery
Para este caso, cabe destacar que lo que viene a continuación no es la única forma de implementación que puedes usar con jQuery.
Para el elemento de link, vas a necesitar el atributo href con el valor de id del elemento colapsable, y una id que la vas a necesitar en tu código:

Ahora se procede a programar el comportamiento colapsable. Para ello se usa el método .collapse() y el evento click, de modo que al hacer click en el elemento de link, se muestra u oculta el elemento con el texto, con efecto collapse.
$("#linkToText").on("click", function() {
    $("#myText").collapse("toggle");
});

Traducido a tu código, quedaría como viene a continuación. El efecto collapse lo puedes ver mejor a pantalla completa.

$(document).ready(function() {
  $("#linkToText1").on("click", function() {
    $("#myText1").collapse("toggle");
  });

  $("#linkToText2").on("click", function() {
    $("#myText2").collapse("toggle");
  });

  $("#linkToText3").on("click", function() {
    $("#myText3").collapse("toggle");
  });
});

<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" rel="stylesheet"/>
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap-theme.min.css" rel="stylesheet"/>

José Miguel
Estilista Integral

Lucia Jaimes
Estilista Integral

Natalia Torres
Estilista Integral

Véase también

*

*Bootstrap Collapse (Documentación de W3Schools) (en inglés)

*Bootstrap JS Collapse (Documentación de W3Schools) (en inglés)

redpajama_set_name: RedPajamaStackExchange