TITLE: Is there a more intuitive/easier way to solve these combined rate problems?
QUESTION [1 upvotes]: I am helping my brother study for the GRE and we have come across some problems like this in my old precalculus textbook:

1) Karen and Betty have been hired to pain a house. Working together, they can paint the house in $\dfrac 23$ the time it would take Karen working alone. Betty could paint the house by herself in $6$ hours. How long would it take Karen to paint the house working alone?
2) Stan and Hilda can mown the lawn in 40 minutes if they work together. If Hilda works twice as fast as Stan, how long would it take Stan to mown the lawn alone?

The way I advised my brother to do these is to write the "$d=rt$" equation for every case: each person working alone, and both people working together; introduce as many variables as you need. From then, I just told him to try to manipulate the equations to solve for the unknown variable. However, he found this approach difficult. He said that somebody really smart could understand what's going on better and not have to rely on algebraic manipulations. Is there a better way to do these?
This is how I solved them:
1) Suppose the house has $x$ square meters of surface area that needs to be painted.
$r_k =$ rate of Karen (in $m^2$/hour)
$r_B =$ rate of Betty (in $m^2$/hour)
$t_k =$ time it takes Karen to paint the house alone (in hours)
$r_k = 6$ hours (given)
The three $d=rt$ equations are
$$x = r_k \cdot t_k$$
$$x = 6 \cdot r_B$$
$$x = \dfrac 23 \cdot t_k \cdot (r_B + r_k)$$
We are trying to solve for $t_k$. Transform the second equation into $r_B = \dfrac x6$ and substitute in for $r_B$. Distribute $\dfrac 23 t_k$ as well:
$$x = \dfrac 23 \cdot t_k \cdot \dfrac x6 + \dfrac 23 t_k r_k$$
Substitute $r_k \cdot t_k = x$
$$x = \dfrac 23 \cdot t_k \cdot \dfrac x6 + \dfrac 23 x$$
Now you can cancel the $x's$ and solve for $t_k$.
2) Using similar definitions as above (and $x$ is $m^2$ of lawn now)
$$x = r_S \cdot t_S$$
$$x = (2 r_S) \cdot t_H$$
$$x = (r_S + 2r_S) \cdot 40$$
Setting the first and third equations equal to each other,
$$r_S \cdot t_S = (3r_S) \cdot 40$$
Now you can cancel $r_S$ and solve for $t_S$.

REPLY [1 votes]: Om$\overline{\mbox{nom}}$ is right.  The usual way to work such problems to work out how much of the job is done in one hour (or day or whatever.)  If Karen can do the job in $k$ hours, then she paints $1/k$ of the house in one hour.  Betty paints $1/6$ of the house in one hour.  So here's the good part:  Together they paint $1/k + 1/6$ of the house in one hour.
On the other hand, we know it takes $2k/3$ hours for both of them to paint the house, so that's $1/(2k/3)$ of the house per hour.  Now you have an equation in one variable:
$$\frac{1}{k}+\frac{1}{6} = \frac{1}{2k/3}.$$
Multiply through by $6k$ to clear fractions:
$$6+k=9.$$
So $k=6$.
The philosophy here is that math lives and dies on equal signs.  So you need things that are equal, so you can stick a $=$ between them.  The great equalizer on these problems is expressing everything in one unit:  "How much of the job is done in ONE hour?"
For the second problem, if Hilda takes $h$ minutes then Stan takes $2h$ minutes.  In one minute they do $1/h+1/2h$ of the job.  But the problems says this is $1/40$ of the job, and there's your equal sign.
We did both problems with one variable.  Your way, I think, overcomplicates things.


TITLE: Solving $\cos\pi x +x^2 -6x +10 = 0$
QUESTION [0 upvotes]: I have the following equation:

$$\cos\pi x +x^2 -6x +10 = 0$$

I have no idea where to begin. I tried taking the derivative multiple times, but it leads to nonsense.

REPLY [3 votes]: HINTS:
$\cos(\pi x) +x^2 -6x +10 = 0 \implies \cos(\pi x) + (x-3)^2 + 1 = 0$
Since $(x-3)^2\ge 0$ and $\cos(\pi x) \ge -1\ldots $


TITLE: General Advice on the proof of inequalities
QUESTION [2 upvotes]: I've got a pretty basic question that has been slightly confusing to me (I kinda understand this, but I  need some affirmation).
Basically, say I have an inequality $(2n+3)^2>4(n+1)(n+2)$, which, when both sides are expanded and like terms are collected and removed, you get $1>0$. But why does this result prove that the initial inequality is true?
Thanks

REPLY [3 votes]: Consider the function $f(n) = LHS - RHS$, i.e. $f(n) = (2n+3)^2 - 4(n+1)(n+2)$
Now when you simplfy the function you get $f(n) = 4n^2 - 4n^2 +12n -12n + 9 - 8 = 1$ i.e. $f(n) = 1$, so, $f(n) = (2n+3)^2 - 4(n+1)(n+2) = 1 > 0$ i.e. $LHS -RHS > 0$ so that  $LHS > RHS$


TITLE: Stein's lemma for Gaussian variables proof
QUESTION [1 upvotes]: I am reading a paper (https://arxiv.org/abs/1001.3448) and they mentioned Stein's lemma (below) as a useful fact without proof, I also read the reference in the paper but I got nothing. Please help me any material contained proof of this lemma.
(Stein's lemma) For jointly Gaussian variables $Z_1, Z_2$ with zero mean and for any function $\psi: \mathbb{R} \rightarrow \mathbb{R}$, where $\mathbb{E}\{\psi'(Z_1)\}, \mathbb{E}\{\psi'(Z_2)\}$ exist, the following holds
$$\mathbb{E}\{Z_1\psi(Z_2)\} = \text{Cov}(Z_1,Z_2)\mathbb{E}\{\psi'(Z_2)\}$$

REPLY [2 votes]: You can write $Z_1=\alpha Z_2+\tilde{Z}_1$ with $Z_2,\tilde{Z}_1$ are independent. Then $$\mathbb{E}(Z_1\psi(Z_2))=\alpha\mathbb{E}(Z_2\psi(Z_2))=\frac{\alpha}{\sqrt{2\pi\sigma^2}}\int_{\mathbb{R}}xe^{x^2/2\sigma^2}\psi(x)dx $$ one can conclude by integration by parts.


TITLE: Infinite series equality $\frac{1}{1+x}+\frac{2x}{1+x^2}+\frac{3x^2}{1+x^3}+\frac{4x^3}{1+x^4}+\cdots$
QUESTION [9 upvotes]: Prove the following equality ($|x|<1$).
$$\frac{1}{1+x}+\frac{2x}{1+x^2}+\frac{3x^2}{1+x^3}+\frac{4x^3}{1+x^4}+\cdots\\
=\frac{1}{1-x}+\frac{3x^2}{1-x^3}+\frac{5x^4}{1-x^5}+\frac{7x^6}{1-x^7}+\cdots\\$$

REPLY [4 votes]: Multiplying $x$ to both sides, the identity is equivalent to
$$ \sum_{k=1}^{\infty} \frac{kx^k}{1+x^k} = \sum_{k=1}^{\infty} \frac{(2k-1)x^{2k-1}}{1-x^{2k-1}}. $$
Expanding and rearranging, each series can be written as
\begin{align*}
\sum_{k=1}^{\infty} \frac{kx^k}{1+x^k}
&= \sum_{k=1}^{\infty} \sum_{j=1}^{\infty} (-1)^{j-1} k x^{jk} = \sum_{n=1}^{\infty} \Bigg( \sum_{d|n} (-1)^{d-1}\frac{n}{d} \Bigg) x^{n} \\
\sum_{k=1}^{\infty} \frac{(2k-1)x^{2k-1}}{1-x^{2k-1}}
&= \sum_{k=1}^{\infty} \sum_{j=1}^{\infty} (2k-1)x^{j(2k-1)} = \sum_{n=1}^{\infty} \Bigg( \sum_{\substack{d | n \\ d \text{ odd}}} d \Bigg) x^{n}
\end{align*}
So it is sufficient to prove that
$$ \color{blue}{\sum_{d|n} (-1)^{d-1}\frac{n}{d} = \sum_{\substack{d | n \\ d \text{ odd}}} d} \quad \text{for } n = 1, 2, \cdots. \tag{1}$$
To this end, write $n = 2^e m$ for $e \geq 0$ and $m$ is odd. Then
$$ \sum_{d|n} (-1)^{d-1}\frac{n}{d}
= \sum_{d'|m} \underbrace{\sum_{i=0}^{e} (-1)^{2^i d'-1} 2^{e-i}}_{=1} \frac{m}{d'}
= \sum_{d'|m} \frac{m}{d'}
= \sum_{d|m} d
= \sum_{\substack{d | n \\ d \text{ odd}}} d $$
and hence $\text{(1)}$ is proved.


TITLE: Are Colors Emitted at Specific Temperatures?
QUESTION [5 upvotes]: There are quite a few nagging questions I have been having over the years, I do not require a full explanation, just some guidance in my assumptions and pointers if I am very wrong.
My basic knowledge of a lightbulb is that the power dissipated by the tungsten filament heats it to around 2,700–3,300K (inefficient!), emitting a yellow light. Something supporting my current (and next) claims is this image, see the bottom chart on temperatures:

With this, can I assert that fire is red (and yellow) due to the fact it is simply at those temperatures where those colours are emitted, and it happens to emit those frequency photons? What is this called? I recall "thermionic emission" however, I am unsure if this relates closely to visible light as it does "heat".
Of course, I've heard the phrase "white hot", iron (and other similar metals) melt at around 1800°K (tungsten at 3422°K), while that near-white temperature is below 10M°K! Not to mention it would glow green first before that blueish point. I will assert that metal cannot glow that hot - of course searching images of "white-hot metal" come up with red-ish metal, however "white hot" is used often enough to cloud my memory.
"Colour temperature" is another confusing topic I have looked at, does it directly relate to the colour emitted at the above temperatures? I do not see "5000K" (often referenced as a blueish white) being white unless other colours are combined, however how that is a "temperature" confuses me. Are they just separate from each other?
I can also as a sanity check assume that some gas generated flames being blue, is due to the gas burning and not the temperature. Are all of my assumptions correct? Can you clarify or add anything?

REPLY [2 votes]: Just to add to Vineet's answer.
Wien's displacement law only tells you the peak wavelength of a hot object's spectrum. The actual emmission spectra is a broad function and so a hot object will emit both longer and shorter wavelengths.

Remember also that a hot object will emit overall more power, and finally you have to include your eye's sensitivity to various wavelengths.
So a piece of hot metal will appear white because although it's peak emmission will be in the infrared it is still emitting a lot of power at shorter wavlengths and your eye is more sensitive to blue than red.


text:
\begin{document}
\maketitle

\begin{abstract}
\noindent
 By finding orthogonal representation for a family of   simple  connected  called $\delta$-graphs it is possible to show that $\delta$-graphs satisfy delta conjecture. An extension of the argument to graphs of the form $\overline{P_{\Delta(G)+2}\sqcup G}$ where $P_{\Delta(G)+2}$ is a path and $G$ is a simple connected graph it is possible to find an orthogonal representation of $\overline{P_{\Delta(G)+2}\sqcup G}$ in $\mathbb{R}^{\Delta(G)+1}$. As a consequence we prove delta conjecture.\end{abstract}

\noindent{{\bf Key words:} delta conjecture , simple connected graphs, minimum semidefinite  rank, $\delta$-graph, C-$\delta$ graphs, orthogonal   representation.}\\
\\
\noindent{{\bf DOI:} 05C50,05C76 ,05C85 ,68R05 ,65F99,97K30.}

\section{Introduction}

A {\it graph} $G$ consists of a set  of vertices $V(G)=\{1,2,\dots,n\}$ and a set of edges $E(G)$, where an edge is defined to be an unordered  pair of vertices. The {\it order} of $G$, denoted $\vert G\vert $,  is the cardinality  of $V(G)$. A graph is {\it simple} if it has no multiple  edges  or loops. The {\it complement } of a graph $G(V,E)$ is the graph $\overline{G}=(V,\overline{E})$, where $\overline{E}$ consists of all those edges of the complete  graph $K_{\vert G\vert}$ that are not in $E$.

 A matrix $A=[a_{ij}]$ is {\it combinatorially symmetric} when $a_{ij}=0$ if and only if $a_{ji}=0$. We say that  $G(A)$  is the graph of a combinatorially symmetric matrix $A=[a_{ij}]$ if $V=\{1,2,\dots,n\}$ and $E=\{\{i,j\}: a_{ij}\ne0\}$ . The main diagonal entries of $A$ play no role in determining $G$. Define $S(G,\F)$ as the set of all $n\times n$ matrices that are real symmetric if $\F=\Re$ or complex Hermitian if $\F=\C$ whose graph is $G$. The sets $S_+(G,\F)$ are the corresponding subsets of positive semidefinite (psd) matrices. The smallest possible rank  of any matrix $A\in S(G,\F)$  is the {\it minimum rank} of $G$, denoted $\mr(G,\F)$, and the smallest possible rank of any matrix $A\in S_+(G,\F)$  is the {\it minimum semidefinite rank} of $G$, denoted $\mr_+(G)$ or $\msr(G)$.

In 1996, the minimum rank among real symmetric matrices with a given graph was studied  by  Nylen \cite{PN}. It gave rise to the area of minimum rank problems which led to the study of minimum rank among complex Hermitian matrices and positive semidefinite matrices associated with a given graph. Many results can be  found for  example  in  \cite{FW2, VH, YL, LM, PN}.

During  the   AIM workshop of 2006 in Palo Alto, CA, it  was  conjectured   that for any   graph $G$  and  infinite field  $F$, $\mr(G,\F)\le |G|-\delta(G)$ where $\delta(G)$  is the minimum  degree  of  $G$.  It  was  shown  that  for if  $\delta(G)\le 3$ or  $\delta(G)\ge |G|-2$    this inequality  holds.  Also  it  can be verified that  if  $|G|\le 6$ then  $\mr(G,F)\le |G|-\delta(G)$.  Also  it  was   proven  that any  bipartite graph  satisfies  this conjecture. This  conjecture   is called  the {\it Delta Conjecture}. If we   restrict  the study  to  consider  matrices  in $S_+(G,\F)$  then  delta conjecture  is  written  as $\msr(G)\le |G|-\delta(G)$. Some  results on delta conjecture  can be found in \cite{AB,RB1, SY1, SY} but  the   general problem  remains  unsolved. In  this paper,  by  using  a  generalization  of  the argument  in  \cite{PD},  we  give  an  argument  which  prove  that  delta  conjecture  is  true   for  any  simple and  connected  graph  which means  that delta  conjecture  is  true.

\section{Graph Theory Preliminaries}
\addtocontents{toc}{\vspace{-15pt}}
In  this section   we give   definitions and results from  graph theory which    will  be used in  the remaining  chapters. Further details  can be found  in \cite{BO,BM, CH}.

A {\bf graph} {$G(V,E)$} is a pair {$(V(G),E(G)),$} where {$V(G)$} is the set of vertices and {$E(G)$} is the set of edges together  with an  {\bf  incidence  function} $\psi(G)$ that associate with  each edge  of  $G$ an  unordered  pair  of (not necessarily  distinct) vertices  of  $G$. The {\bf order} of {$G$}, denoted {$|G|$}, is the number of vertices in {$G.$} A graph is said to be {\bf simple} if it has no loops or multiple edges. The {\bf complement} of a graph {$G(V,E)$} is the graph {$\overline{G}=(V,\overline{E}),$} where {$\overline{E}$} consists of all the edges that are not in {$E$}.
A {\bf  subgraph} {$H=(V(H),E(H))$} of {$G=(V,E)$} is a graph with {$V(H)\subseteq V(G)$} and {$E(H)\subseteq E(G).$} An {\bf induced subgraph} {$H$} of {$G$}, denoted G[V(H)], is a subgraph with {$V(H)\subseteq V(G)$} and {$E(H)=\{\{i,j\} \in E(G):i,j\in V(H)\}$}. Sometimes  we  denote the  edge $\{i,j\}$ as $ij$.

We  say  that  two  vertices of a graph $G$  are {\bf adjacent}, denoted  $v_i\sim v_j$,   if  there is an edge $\{v_i,v_j\}$ in  $G$.  Otherwise  we say  that the  two  vertices $v_i$ and $v_j$ are {\bf non-adjacent}  and  we denote this  by $v_i \not\sim v_j$.  Let {$N(v)$} denote the set of vertices that are adjacent to the vertex {$v$} and let {$N[v]=\{v\}\cup N(v)$}. The {\bf degree} of a vertex {$v$} in {$G,$} denoted {$\d_G(v),$} is the cardinality of {$N(v).$} If {$\d_G(v)=1,$} then {$v$} is said to be a {\bf pendant} vertex of {$G.$} We use {$\delta(G)$} to denote the minimum degree of the vertices in {$G$}, whereas {$\Delta(G)$} will denote the maximum degree of the vertices in {$G$}.

 Two  graphs $G(V,E)$ and $H(V',E')$  are  identical  denoted  $G=H$, if  $V=V',  E=E'$, and $\psi_G=\psi_H$  . Two  graphs $G(V,E)$ and $H(V',E')$ are {\bf isomorphic}, denoted  by  $G\cong H$, if  there exist bijections $\theta:V\to V'$  and $\phi: E\to  E' $ such  that $\psi_G(e)=\{u,v\}$  if  and  only if  $\psi_H(\phi(e))= \{\theta(u), \theta(v)\}$.

 A {\bf complete graph}  is a simple graph in which the vertices are pairwise adjacent.
  We will use {$nG$} to denote {$n$} copies of a graph {$G$}. For example, $3K_1$  denotes three  isolated vertices $K_1$ while {$2K_2$} is the graph given  by   two  disconnected  copies  of $K_2$.

 A {\bf path} is a list of distinct vertices in which successive vertices are connected by edges. A path on {$n$} vertices is denoted by {$P_n.$} A graph {$G$} is said to be {\bf connected} if there is a path between any two vertices of {$G$}. A {\bf cycle} on {$n$} vertices, denoted {$C_n,$} is a path such that the beginning vertex and the end vertex are the same. A {\bf tree} is a connected graph with no cycles. A graph $G(V,E)$ is  said  to be {\bf chordal}  if it has no induced cycles $C_n$ with $n\ge 4$.
 A  {\bf component}  of a graph $G(V,E)$ is  a maximal connected  subgraph. A  {\bf cut vertex}   is  a vertex  whose deletion  increases  the number of  components.

 The {\bf union}  $G\cup G_2$ of  two  graphs $G_1(V_1,E_1)$ and $G_2(V_2,G_2)$  is  the union  of  their  vertex  set  and  edge  set,  that is $G\cup G_2(V_1\cup V_2,E_1\cup E_2$. When  $V_1$ and $V_2$ are disjoint their union  is called  {\bf  disjoint union} and  denoted $G_1\sqcup G_2$.

\section{The Minimum  Semidefinite Rank  of  a Graph}

In  this section  we will establish   some of  the   results for  the minimum  semidefinite rank ($\msr$)of a graph $G$  that  we  will be using in the subsequent chapters.

A {\bf positive  definite} matrix  $A$ is an Hermitian   $n\times n$ matrix such  that $x^\star A x>0$  for all nonzero  $x\in \C^n$. Equivalently,  $A$  is a  $n\times n$ Hermitian positive definite matrix  if and  only  if   all the  eigenvalues of $A$ are positive (\cite{RC}, p.250).

A $n\times n$ Hermitian matrix  $A$ such  that $x^\star A x\ge 0$  for all $x\in \C^n$ is  said  to be  {\bf positive  semidefinite (psd)}. Equi\-va\-lently,   $A$ is a  $n\times n$ Hemitian positive  semidefinite matrix if and  only  if  $A$  has  all   eigenvalues nonnegative (\cite{RC}, p.182).

If $\overrightarrow{V}=\{\overrightarrow{v_1},\overrightarrow{v_2},\dots, \overrightarrow{v_n}\}\subset \Re^m$  is a set of  column vectors  then  the  matrix
$ A^T A$, where $A= \left[\begin{array}{cccc}
  \overrightarrow{v_1} & \overrightarrow{v_2} &\dots& \overrightarrow{v_n}
\end{array}\right]$
and $A^T$  represents  the  transpose matrix of  $A$, is a psd matrix  called  the  {\bf Gram matrix} of $\overrightarrow{V}$. Let $G(V,E)$  be a graph  associated  with  this Gram matrix. Then  $V_G=\{v_1,\dots, v_n\}$ correspond to  the set of  vectors in $\overrightarrow{V}$ and  E(G) correspond to  the nonzero inner products  among  the  vectors  in $\overrightarrow{V}$. In this  case $\overrightarrow{V}$  is  called an  {\bf orthogonal representation} of $G(V,E)$ in $\Re^m$. If  such  an  orthogonal  representation  exists  for  $G$ then $\msr(G)\le m$.

Some    results about  the minimum semidefinite  rank of a graph  are  the  following:

\begin{result}\cite{VH}\label{msrtree}
If  $T $ is a tree  then $\msr(T)= |T|-1$.
\end{result}
\begin{result}\cite{MP3}\label{msrcycle}

 The cycle $C_n$ has minimum semidefinite rank $n-2$.
\end{result}

\begin{result}\label{res2}
 \cite{MP3} \ If a connected  graph $G$  has a pendant  vertex $v$, then $\msr(G)=\msr(G-v)+1$ where $G-v$  is obtained as an induced subgraph of $G$ by  deleting $v$.
\end{result}

\begin{result} \cite{PB} \label{OS2}
 If {$G$} is a connected, chordal graph, then {$\msr(G)=\cc(G).$}
\end{result}

\begin{result}\label{res1}
\cite{MP2}\ If a graph $G(V,E)$ has a cut vertex, so that $G=G_1\cdot G_2$, then  $\msr(G)= \msr(G_1)+\msr(G_2)$.
\end{result}

\section{Delta-Graphs and  the Delta Conjecture}

In  \cite{PD}  is  is  defined   a   family of  graphs  called $\delta$-graphs  and  show  that  they satisfy  the  delta conjecture.

\begin{defn}\label{ccpg}
Suppose  that $G=(V,E)$  with $|G|=n \ge 4$  is simple  and  connected such  that  $\overline{G}=(V,\overline{E})$  is also  simple  and  connected. We  say  that  $G$ is a {\bf $\mathbf{\delta}$-graph} if  we  can  label  the vertices of $G$ in such a way that
\begin{enumerate}
  \item[(1)] the  induced    graph    of  the  vertices  $v_1,v_2,v_3$  in $G$ is  either $3K_1$  or  $K_2 \sqcup K_1$,  and
  \item[(2)] for $m\ge 4$,  the vertex  $v_m$  is  adjacent   to all   the  prior  vertices $v_1,v_2,\dots,v_{m-1}$  except  for at most $\dis{\left\lfloor\frac{m}{2}-1\right\rfloor}$ vertices.
  \end{enumerate}
 \end{defn}
  A second  family  of  graphs also   defined  in  \cite{PD} contains  the  complements  of $\delta$-graphs.
\begin{defn} Suppose   that  a graph $G(V,E)$  with $|G|=n \ge 4$  is  simple and  connected   such  that  $\overline{G}=(V,\overline{E})$  is also   simple and  connected.  We  say  that  $G(V,E)$  is a {\bf C-$\mathbf{\delta}$  graph}  if    $\overline{G}$   is a  $\delta$-graph.

In other  words,  $G$   is a  {\bf C-$\mathbf{\delta}$ graph} if  we can  label   the  vertices   of  $G$  in  such a  way   that
 \begin{enumerate}
 \item[ (1)] the  induced  graph  of  the vertices  $v_1,v_2,v_3$ in  $G$ is  either  $K_3$ or $P_3$,  and
 \item[(2)]  for  $m\ge 4$,  the vertex $v_m$  is adjacent  to at most  $\dis{\left\lfloor\frac{m}{2}-1\right\rfloor}$ of  the  prior  vertices $v_1,v_2,\dots,v_{m-1}$.
\end{enumerate}
\end{defn}
\begin{example}\label{examplecp}
The   cartesian product $K_3\square P_4$  is a C-$\delta$ graph and  its  complement  is  a  $\delta$-graph. By labeling as  the   following picture  we  can  verified  the definition  for  both  graphs.
\newpage
\begin{center}
\includegraphics[height=40mm]{K3cpP4.png}
 \end{center}
\vspace{-0.1in}\begin{figure}[h]
\centering
\caption{The  Graph $K_3\square P_4$  and  its  complement $\overline{K_3\square P_4}$ }\label{fig3.1}
\end{figure}

Note that we  can label  the vertices  of $K_3\square P_4$ clockwise $v_1=(1,1),v_2= (1,2),v_3=(1,3),\dots v_{12}=(3,4)$. The  graph  induced   by  $v_1,v_2,v_3$  is $P_3$. The    vertex $v_4$ is   adjacent to a prior vertex   which  is  $v_3$  in  the induced  subgraph of  $K_3\square P_4$ given  by $\{v_1,v_2,v_3,v_4\}$. Also,   the  vertex $v_5$ is adjacent only  to  vertex $v_1$  in  the  induced  subgraph of  $K_3\square P_4$ given  by $\{v_1,v_2,v_3,v_4, v_5\}$. Continuing   the process trough vertex $v_12$  we conclude   that  $K_3\square P_4$   is a  C-$\delta$  graph. In  the  same  way  we conclude  that  its  complement $\overline{K_3\square P_4}$  is a $\delta$-graph.
\end{example}
\begin{lemma}\label{lem2} Let {$G(V,E)$} be a $\delta$-graph. Then   the induced  graph of {$\{v_1,v_2,v_3\}$} in {$G$} denoted  by $H$ has an  orthogonal  representation  in {$\Re^{\Delta(\overline{G})+1}$} satisfying the  following  conditions:
\begin{enumerate}
\item [(i)] the  vectors   in  the orthogonal  representation  of  $H$ can be chosen  with nonzero coordinates, and
\item [(ii)]\label{L1}$\overrightarrow{v}\not\in \sp(\overrightarrow{u})$ for each pair   of  distinct  vertices  $u,v$ in  $H$.
\end{enumerate}
\end{lemma}

\begin{theorem} \label{main} Let $G(V,E)$ be a $\delta$-graph then
$$
\msr(G)\le\Delta(\overline{G})+1=|G|-\delta(G)\label{mrsineq1}
$$
\end{theorem}
The  proof  of  these  two  results  can  be  found  in  \cite{PD} and \cite{PD1}. The  argument  of  the  proof  is  based on   the construction  of a  orthogonal  representation  of  pairwise linear  independent vectors  for  a $\delta$  graph $G$  at $\Re^{\overline{G})+1}$.  Since  $\msr(G)$  is   the minimum dimension  in which   we can  get  an  orthogonal representation    for a  simple  connected  graphs  the  result  is a  direct  consequence of this  construction.

\section{A survey of  $\delta$-graphs  and upper bounds  their  minimum Semidefinite rank}
The  theorem \ref{main}   give us a  huge family  of  graph  which  satisfies  delta conjecture. Since,  the   complement    of   a  C-$\delta$ graphs  is ussually  a $\delta$-graph,  it  is  enough  to identify  a  C-$\delta$-graph    and  therefore  we know   that   its  complement  is a $\delta$-graph satisfying  delta  conjecture if  it  is  simple and  connected.

Some  examples   of  C-$\delta$ graphs that  we can  find  in  \cite{PD} are  the  Cartesian Product $K_n\square P_m,n\ge  3,  m\ge  4$, Mobi\"us Lader $ML_{2n}, n\ge 3$, Supertriangles $Tn, n\ge 4$,  Coronas $S_n\circ P_m, n\ge  2 , m\ge 1$ where  $S_n$  is a  star  and  $P_m$ a path, Cages like Tutte's (3,8) cage,  Headwood's (3,6) cage   and many others, Blanusa Snarks  of type  $1$ and  $2$  with  $26, 34$, and $42$ v\'ertices, and  Generalized Petersen Graphs $Gp1$ to  $Gp16$.

\subsection{Upper bounds   for  the  Minimum semidefinite rank of  some  families  of  Simple connected graphs}

 From the definition  of  C-$\delta$ graph   and the Theorem \ref{main} we  can obtain  upper  bounds   for  the graph  complement of a C-$\delta$  graphs. It is enough to  label  the  vertices  of $G$  in  such a way  that  the labeled sequence  of  vertices  satisfies  the definition. That is,  if  we  start   with  the induced  graph of  $ \{v_1,v_2,v_3\}$,  the  newly added  vertex $v_m$  is adjacent  to at most $\lfloor\frac{m}{2}-1\rfloor $  of  the prior  vertices $v_1,v_2,\dots,v_{m-1}$.   Then  $G$  is a C-$\delta$  graph  and  its graph  complement $\overline{G}(V,\overline{E})$ will  have an orthogonal representation   in $\Re^{\Delta(G)+1}$ any time it is  simple  and  connected.

 In  order   to  show  the  technique  used  in  the proved  result   consider  the following  examples

 \begin{example}\label{upper1}

If  $G$ is  the Robertson's (4,5)-cage on 19 vertices  then  it is  a 4-regular C-$\delta$ graph. Since $\Delta(G)=4$, the $\msr(G)\le 5$.  To  see  this is a C-$\delta$ graph it  is enough  to label its  vertices  in the  way  shown  in the next  figure:
\begin{center}
\includegraphics[height=50mm]{cage45.png}
 \end{center}
\vspace*{-0.1in}\begin{figure}[h]
\centering

{Figure B.2 Robertson's (4,5)-cage (19 vertices)}
\label{figA.1.2}
\end{figure}
\end{example}
\begin{example}\label{upper2}
If  $G$ is  the platonic  graph   Dodecahedron  then  it is  a 3-regular C-$\delta$ graph. Since $\Delta(G)=3$, the $\msr(\overline{G})\le 4$.  To  see  this is a C-$\delta$ graph it  is enough  to label its  vertices  in the  way  shown  in the next  figure:
\begin{center}
\includegraphics[height=60mm]{dodecahedron.png}
 \end{center}
\vspace*{-0.1in}\begin{figure}[h]
\centering

{Figure 3. Dodecahedron}
\label{figA.1.1}
\end{figure}
\end{example}

The  next  table contains  C-$\delta$  graphs  $G$  taken  from  \cite{RW}  and upper bounds for   $\msr(\overline{G})$ given  by  $\Delta(G)+1$ are  found in \cite{PD}.\\

\begin{table}[h]
\centering
\caption{Table  of  C-$\delta$  graphs  $G$  taken  from  \cite{RW}  and upper bounds for   $\msr(\overline{G})$ given  by  $\Delta(G)+1$.  }\label{App2}
\end{table}

\begin {center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Family & Name of  Graph      && $\msr(\overline{G})$\\
&$G$&$\vert G\vert$&$\le  \Delta(G)+1 $\\ \hline
Archimedean Graphs&&&\\ \hline
&Cuboctahedron&12&$4$\\ \hline
&Icosidodecahedron&30&$5$\\ \hline
&Rhombicuboctahedron&24&$5$\\ \hline
&Rombicosidodecahedrom&60&$6$\\ \hline
& Snub cube&24&$6$\\ \hline
& Snub dodecahedrom&60&$6$\\ \hline
&Truncated cube&24&$4$\\ \hline
&Truncated Cuboctahedron&48&$4$\\ \hline
&$G$&$\vert G\vert$&$\le  \Delta(G)+1 $\\ \hline
&Truncated dodecahedron&60&$4$\\ \hline
&Truncated icosahedrom &60&$4$\\ \hline
& Truncated icosidodecahedrom&120&$6$\\ \hline
&Truncated Tetrahedron&12&$4$\\ \hline
&Truncated octahedron&24&$4$\\ \hline
Antiprisms &$2n, n\in \N, \ n\ge 3$&$2n, n\ge 3$&$5$\\ \hline
&$4$-antiprism&$8$&$5$\\ \hline
&$5$-antiprism&$10$&$5$\\ \hline

Cages&&&\\ \hline
&Balaban's $(3,10)$ cage&70&$4$\\ \hline
&Foster $(5,5)$ cage&30&$6$\\ \hline
&Harries's $(3,10)$ cage &70&$4$\\ \hline
&Headwood's $(3,6)$ cage&14&$4$\\ \hline
&MacGee's $(3,7)$ cage&24&$4$\\ \hline
&Petersen's $(3,5)$ cage&10&4\\ \hline
&Robertson's $(5,5)$ cage&30&$6$\\ \hline
&Robertson's $(4,5)$ cage&19&$5$\\ \hline
&The Harries-Wong $(3,10)$ cage&70&$4$\\ \hline
&The $(4,6)$ cage&26&$5$\\ \hline
&Tutte's$(3,8)$ cage&30&$4$\\ \hline
&Wongs's $(5,5)$ cage &30&$4$\\ \hline
&The Harries-Wong $(3,10)$ cage&70&$4$\\ \hline
&The $(4,6)$ cage&26&$5$\\ \hline
&Tutte's$(3,8)$ cage&30&$4$\\ \hline
&Wongs's $(5,5)$ cage &30&$4$\\ \hline

\end{tabular}
\end{center}
\newpage
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Family & Name of  the   Graph      && $\msr(\overline{G})$\\
&$G$&$\vert G\vert$&$\le  \Delta(G)+1 $\\ \hline
Blanusa Snarks&&&\\ \hline
&Type 1:  26 vertices&26&4\\ \hline
&Type 2: 26 vertices&26&4\\ \hline
&Type 1: 34 vertices&34&4\\ \hline
&Type 2: 34 vertices&34&4\\ \hline
&Type 1: 42 vertices&42&4\\ \hline
&Type 2: 34 vertices&42&4\\ \hline
Generalized Petersen Graphs&&&\\ \hline
&Gp1&10&$4$\\ \hline
&Gp2&12&$4$\\ \hline
&Gp3&14&$4$\\ \hline
&Gp4&16&$4$\\ \hline
&Gp5&16&$4$\\ \hline
&Gp6&18&$4$\\ \hline
&Gp7&18&$4$\\ \hline
&Gp8&20&$4$\\ \hline
&Gp9&20&$4$\\ \hline
&Gp10&20&$4$\\ \hline
&Gp11&22&$4$\\ \hline
&Gp12&22&$4$\\ \hline
&Gp13&24&$4$\\ \hline
&Gp14&24&$4$\\ \hline
&Gp15&24&$4$\\ \hline
&Gp16&24&$4$\\ \hline
Non-Hamiltonian Cubic &&&\\ \hline
&Grinberg's Graph&44&4\\ \hline
&Tutte's Graph&46&$4$\\ \hline
&(38 vertices)&38&4\\ \hline
&(42 vertices)&42&$4$\\ \hline
Platonic Graphs&&&\\ \hline
&Cube&8&$4$\\ \hline
&Dodecahedron&20&$4$\\ \hline
Prisms &$n$-prism,$n\ge 4$ &$2n$&$4$\\ \hline
&$4$-prism &$8$&$4$\\ \hline
&$5$-prism &$10$&$4$\\ \hline
Snarks&&&\\ \hline
&Celmins-Swarf snark 1&26&$4$\\ \hline
&Celmins-Swarf snark 2&26&$4$\\ \hline
&Double Star snark&30&$4$\\ \hline
&Flower snark $J_7$&28&$4$\\ \hline
&Flower snark $J_9$&36&$4$\\ \hline
&Flower snark $J_{11}$&44&$4$\\ \hline

\end{tabular}
\end{center}
\newpage
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Family & Graph      && $\msr(\overline{G})$\\
&$G$&$\vert G\vert$&$\le  \Delta(G)+1 $\\ \hline
&Hypercube &$2^4$&$5$\\ \hline
&Loupekine's snark 1 (Sn28)&22&$4$\\ \hline
&Loupekine's snark 2 (Sn29)&22&$4$\\ \hline
&The Biggs-Smith&102&$4$\\ \hline
&The Greenwood-Gleason&16&$6$\\ \hline
&The Szekeres snark&50&$4$\\ \hline
&Watkin's snark &50&$4$\\ \hline
Miscelaneous Regular Graphs&&&\\ \hline
&Chvatal's graph&12&$5$\\ \hline
&Cubic Graph with no perfect matching &$16$&$4$\\ \hline
&Cubic Identity  graphs &$12$&$4$\\ \hline
&Folkman's graph&20&$5$\\ \hline
&Franklin's graph&12&$4$\\ \hline
&Herschel's graph&11&$5$\\ \hline
&Hypercube &$16$&$4$\\ \hline
&Meredith's graph&70&$4$\\ \hline
&Mycielslski's graph&11&$6$\\ \hline
&The  Greenwood-Gleason graph &$16$&$6$\\ \hline
&The Goldner-Harary dual&&$$\\
&( the truncated Prism)&18&$4$\\ \hline
&Tietze's graph&11&$4$\\ \hline
\end{tabular}
\end{center}

\section{Proof  of  Delta Conjecture}
In  this  section  we  give  an argument   which   prove  that  Delta  Conjecture  is  true  for any simple graph  not  necessarily connected  as a  generalization of  the  result  given  in \cite{PD}.   For  that  purpose  We    define  a  generalization  of  C-$\delta$ graphs called  {\bf  extended C-$\delta$ g graph}.

Previously,  we stablish that    Delta  Conjecture  holds for  $\delta-$Graphs. The  condition $2\le\Delta(G)\le\vert G\vert-2$ in the proof  of \ref{main} was given as  a  sufficient  condition  to obtain  that  the  graph  complement of  a C-$\delta$ graph is connected. We  will see  that the  condition  of connectivity  of  a  C-$\delta$  graphs   is not  necessary in order to proof  Delta  Conjecture  when   using  the  result \ref{main}.

Hence,  we can  define a  generalization  of  C-$\delta$  graphs  in   the  following  way.

\defn{ A {\bf extended C-$\delta$ graph} $G'$  is a  simple  graph  which  is  the  disjoint union  of  a  simple connected graph $G, \vert G\vert\ge 4$ ( not  necessarily connected) and a path $P_n$,  where  $n= 2\Delta(G)+2, n\ge 4$.  That  is
$$
G'=P_n\sqcup G ; n=2\Delta(G)+2.
$$}

All  vertices  of $G$ are connected  with  all vertices of $P_n$ in  $\overline{G'}$.  As  a  consequence $\overline{G'}$ is a simple  and  connected graph.

\newpage
\defn {A  graph $G, \vert G\vert\ge 4$ has  a {\bf C-$\delta$  construction} if  it  can  be  constructed   starting    with $K_3$ or  $P_3$  and  by  adding  one  vertex  at a time  in  such  a  way  that  the  newest  vertex $v_m, m\ge 4$ is adjacent to  at most $\dis{\left\lfloor\frac{m}{2}-1\right\rfloor}$ of  the prior  vertices $v_1,v_2,\dots,v_{m-1}$}.

\begin{center}
\includegraphics[height=50mm]{ecdgraph.png}
 \end{center}
\vspace{-0.1in}\begin{figure}[h]
\centering
\caption{Extended C-$\delta$ Graph }\label{fig1}
\end{figure}
\proposition\label{propo1}{ Let  $G'=P_n\sqcup G$ be  an  extended C-$\delta$  graph. Then  $\overline{G'}$  has an  orthogonal  representation  in $\Re^{\Delta(G)+1}$. }

\noindent\MakeUppercase{Proof}:

Let $G'(V',E')$  be an  extended  C-$\delta$ graph.  Then $G'=P_n\sqcup G ; n=2\Delta(G)+2$  and  $G(V,E)$  is a  simple  graph. Since  $P_n$  is a  C-$\delta$ graph we  know   that  we can label  its  vertices  in  such  a  way  that if $v_2,\dots,v_n$  are  its   vertices   then  $\overrightarrow{v_1},\dots,\overrightarrow{v_n}$ is an orthogonal  representation of  its  graph  complement $\overline{P_n}$ in  $\Re^3$. But  since $\Delta(G)\ge 2 $  because   $G$ is  connected   and  $\vert G\vert\ge 4$ then  we  can also obtain  an  orthogonal  representation  of  $P_n$  in $\Re^{\Delta(G)+1}$ getting $2\Delta(G)+2$ vectors    for $\overline{G'}$ in $\Re^{\Delta(G)+1}$ using  the  C-$\delta$  construction.

Thus,  in  $G'$, $v_{2\Delta(G)+2}$ is   adjacent with  all  prior  vertices $v_1,\dots,v_{2\Delta(G)+1}$ but  at most $$\dis{\left\lfloor\frac{2\Delta(G)+2}{2}-1\right\rfloor}\\ =\Delta(G)\ge 2$$
vertices. Actually   to  all of  them but  one.

Now,  choose a  vertex $v'$  in  $\overline{G}$  and label it  as $ v'=v_{2\Delta(G)+3}$. In  $\overline{G'}$ $v_{2\Delta(G)+3}$ is  adjacent
with  all of  the  vertices   of  $P_n$. As a consequence, $v_{2\Delta(G)+3}$ satisfies  the  delta  construction   in $G'$.

If  $Y_{2\Delta(G)+2}$  is  the induced  graph  of $G'$  given  by  $v_1,\dots,v_{2\Delta(G)+2}$  then  $Y_{2\Delta(G)+3}=Y_{2\Delta(G)+2}\cup \{v_{2\Delta(G)+3}\}$ is  simple  and  connected  and  $\overline{Y}_{2\Delta(G)+3}$ can  be  constructed   by using  $\delta$-construction because.
$v_{2\Delta(G)+3}$ is  adjacent with  all previous  vertices  $v_1,v_2,\dots v_{2\Delta(G)+2}$ in $\overline{G'}$. Then it is  adjacent   with all previous   vertices in $Y_{2\Delta(G)+2}$ but  at most $\dis{\left\lfloor \frac{2\Delta(G)+3}{2}-1\right\rfloor}\ge \Delta(G)$.

Now, by  labeling  the  remaining  vertices  in  $G'$ which  are    vertices  in  G in  any  random sequence    to  obtain  $v_{2\Delta(G)+4,\dots,v_{2\Delta(G)+2+\vert G\vert}}$  we  get     a sequence  of  induced  subgraph  of  $\overline{G}$
$$
Y_{2\Delta(G)+4}\subseteq Y_{2\Delta(G)+5}\subseteq\dots\subseteq Y_{2\Delta(G)+2+\vert G\vert}=\overline{G'}
$$

All  of  these   induced  subgraphs  can  be  constructed  using  $\delta$-construction.  As  a consequence $Y_{2\Delta(G)+2+\vert G\vert}\\ =\overline{G'}$  can  be  constructed using $\delta$-construction   which  implies   that    there  is  an  orthogonal  representation  $\overrightarrow{v}_1,\overrightarrow{v}_2,\dots,\overrightarrow{v}_{2\Delta(G)+2+\vert G\vert}$ of  the vertices  of  $\overline{G'}$ at  $\Re^{\Delta(G')+1}$.

But $\Delta(G')\ge \Delta(G)$ since  $\vert G\vert\ge 4$,  $\overline{G}$ is  simple a nd  connected, and  $G$   is an induced  graph  of  $G'$.

Then    we  can  get  the  orthogonal  representation of  $\overline{G'}$ in  $\Re^{\Delta(G)+1}$.

Finally,  if $\overrightarrow{v}_1,\overrightarrow{v}_2,\dots,\overrightarrow{v}_{2\Delta(G)+2+\vert G\vert}$ is   the orthogonal  representation of  $G'$ in  $\\Re^{\Delta(G)+1}$   take  the  vectors $\overrightarrow{v}_{2\Delta(G)+3},\overrightarrow{v}_{2\Delta(G)+4},\dots,\overrightarrow{v}_{2\Delta(G)+2+\vert G\vert}$.  These  vectors  satisfy  all the  adjacency  conditions  and  orthogonal  conditions  of  $\overline{G}$  because $\overline{G}$ is an  induced  subgraph  of  $\overline{G'}$. As  a consequence, $\overrightarrow{v}_{2\Delta(G)+3},\overrightarrow{v}_{2\Delta(G)+4},\dots,\overrightarrow{v}_{2\Delta(G)+2+\vert G\vert}$ is  an orthogonal   representation  of $\overline{G}$ in  $\Re^{\Delta(G)+1}$.\\ .\hfill$\square$

\theorem\label{teo1}{If  $G$ is  a  simple  connected  graph, $\vert G\vert \ge 4$  then  $G$  satisfies  Delta  conjecture}.

\noindent\MakeUppercase{Proof}:

Let $G$  be  a  simple  connected graph. Since  $G$ can  be seen  as a  component   of   a extended  C-$\delta$ graph $G'= P_{2\Delta(G)+2} \sqcup G$  by  the  proposition   proved  above $G$   has  an  orthogonal  representation   in   $\Re^{\Delta(G)+1}=\Re^{\vert G\vert-\delta(G)}$  which   implies   that
$\msr(G)\le \vert G\vert-\delta(G)$ . As  a  consequence   delta  conjecture  holds    for any  simple connected  graph  $G$ with  $\vert G\vert\ge 4$.\hfill $\square$

Finally, by  using   extended C-$\delta$ graphs $G'=P_{2\Delta(G)+2}\sqcup G$   for  all  $G, \vert G\vert \le 3$ and   the  technique   described  in  the proof  of   the proposition  above  or  any other    way  it is  easy    to  check that    all   of  simple  connected  graphs    with  $\vert G\vert \le 3$   satisfies Delta  conjecture.  As  a consequence   we  have the  following  theorem:

\corollary{ Let $G$  be a  simple  and  connected  graph. Then $G$   satisfies delta  conjecture}

\noindent\MakeUppercase{Proof}:

From \ref{teo1} we know  that  delta  conjecture  hold   for  any  simple  graph $G, \vert G\vert \ge 4$.  Checking  all  cases for   all  simple  connected  graph $G, \vert G\vert \le 3 $  we complete  the proof  for  delta conjecture. \hfill $\square$

\section{Conclusion}

In  this paper  we  proved  the  delta  conjecture  as  a  main  result. Also   we applied  the technique for finding  the  minimum  semidefinite  rank of  a  C-$\delta$  to  give a  table  of  upper bounds   of  a  large amount  of  families  of   simple  connected  graphs.  These upper  bounds  will  be usefull  in the  study   of the minimum  semidefinite  rank  of  a  graph.

In  the  future, the  techniques applied in  this paper   could  be  useful  to  solve  other  problems   related  with   simple connected  graphs and   minimum  semidefinite  rank.
\section{Acknowledment}
I  would like  to  thanks   to  my  advisor  Dr. Sivaram Narayan  for   his  guidance and  suggestions  of  this  research.  Also  I  want  to  thank  to  the math  department  of  University  of  Costa  Rica and  Universidad  Nacional Estatal  a Distancia  because  their  sponsorship  during my  dissertation  research  and    specially  thanks  to   the math  department    of  Central Michigan University   where  I  did  the  researh   for  C-$delta$ graphs which  was  a paramount  research  to proof delta  conjecture.
\input{bibliography}

\end{document}

config: arxiv


TITLE: Modified Sum of Products
QUESTION [1 upvotes]: A given number k is to be expressed as a sum of products of integers keeping in mind that the integers used in above process do not exceed their cumulative sum as 100.
For e.g.,
k = 19 can be expressed as 15 + 4 or 3*5 + 2*2, so the cumulative sum is 3 + 5 + 2 + 2 = 12
A simple approach is to prime factorize the given integer but the problem arises when the sum of prime factors exceed 100 and in expressing primes as in required form.
k can be large upto 100000.

REPLY [1 votes]: One method would be to use the base 3 (or ternary) representation of $k$.

For example, if the number is $k=500$, then you could notice that $3^5 = 243$, so $$500 = 3 \cdot 3\cdot 3\cdot 3\cdot 3\cdot 2 + 7\cdot 2$$
Or if $k=1000$, I would use $$1000 = 3^6 + 3^5 + 3^3 + 1 = 729 + 243 + 27 + 1$$


TITLE: Question about the function field of a noetherian, integral, locally factorial scheme
QUESTION [1 upvotes]: Let $X$ be a scheme. Assume $X$ is noetherian, integral, and locally factorial.
Let $\eta$ be the generic point of $X$, then the function field of $X$ is $K(X):=O_{X, \eta}$.
Let $Y$ be a prime divisor of $Y$, and $y$ its generic point.
I am trying to show that $K(X)$ is isomorphic to $Frac(O_{X,y})$.
I would appreciate if someone could explain me how to construct the isomorphism. Thank you.
Below is my attempt at this when $X = \operatorname{Spec}R$. In this case the generic point is the zero ideal. Let $Y$ be a prime divisor, say it is $Y = V(P)$ where $P$ is a prime ideal of $R$, in other words this is the generic point of $Y$. Then
$$
O_{X, P} = R_P
$$
and since we know that this is an integral domain because $R$ is.
Then it follows that
$$
Frac(R_P) \cong  Frac{R} = R_{(0)}
$$
where the isomorphism is given by
$$
\frac{r/x}{r'/y} \mapsto \frac{r y}{r'x}.
$$
This establishes the case when $X$ is affine. What am I not seeing is how can we reduce to this case when it $X$ is not affine. Can we always find an affine open that contains $\eta$ and $y$?

REPLY [3 votes]: The generic point $\eta$ is, more or less by definition, dense in $X$. So given any affine open neighborhood $U$ of $y$ in $X$, you also get $\eta \in U$ for free.
After that, since you have $\eta, y \in U$, the affine case applies.


TITLE: How would I do a derivation of this: ¬q→(q↔r), ¬q∧(p∨r) ⊢ p using inference rules?
QUESTION [0 upvotes]: I'm having a lot of trouble figuring out how to construct a derivation of

¬q→(q↔r), ¬q∧(p∨r) ⊢ p

So far I've used conjunction elimination to get (p∨r) but then this is where I get stuck.
I'm supposed to use disjunction elimination to get to p but I'm having trouble figuring out where to use it.
I'm allowed to use

∧Intro, ∨Intro, ¬Intro, →Intro, ↔Intro, ∧Elim, ∨Elim, ¬Elim, →Elim, and ↔Elim

inference rules.
Help!

REPLY [1 votes]: I'm not going to piece together exactly what rules to use and when, but here's the outline. Like you say, the conjunction gives you $p\lor r,$ and also gives you $\lnot q.$ Since you have $\lnot q$ and $\lnot q\to (q\leftrightarrow r),$ you obtain $(q\leftrightarrow r).$ Then proceed toward disjunction elimination on $p\lor r.$ In the case where you have $p,$ you obviously have $p$. In the case where you have $r,$ you can use $q\leftrightarrow r$ to obtain $q.$ However, you have $\lnot q,$ so a contradiction, and so you have anything you want, including $p.$
(Most of the steps of the reasoning map straightforwardly to inference rules. The very last step might require a bit of unpacking since you aren't working in a system where ex-falso is a fundamental rule. Just mimic whatever proof of ex-falso  you were given that works in your system to derive $p$.)


TITLE: Is the following optimization problem NP-hard?
QUESTION [2 upvotes]: Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:
$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$
Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.

REPLY [8 votes]: The new version of the problem is indeed NP-hard.
Reduction from set cover: Subsets are $S_1, S_2, ..., S_m$ and the universe is $U = \{ a_1, a_2, ..., a_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:

Nodes are $N = \{ a_1, a_2, ..., a_n, S_1, S_2, ..., S_m, S'_1, S'_2, ..., S'_m \}$.
Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S'_i)$ for all $i$.
Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S'_i) = 0$ for all $i$.

Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:

For each $a_j$ pick one set $S_i \in X$ in the cover with $a_j \in S_i$, and choose the edge $(a_j,S_i)$; we get the benefit of $M$ from $a_j$.
For each $S_i \notin X$ we choose the edge $(S_i, S'_i)$; we get the benefit of $1$ from $S_i$.

Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S_1, S_2, ..., S_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.


TITLE: Is the cardinality of an empty set comparable to some other sets by the definition?
QUESTION [0 upvotes]: I've been learning mathematical analysis written by B.A Zorich recently. The description of Card X ≤ Card Y in this book is "there exists a bijective mapping of X onto some subset of Y". But here comes my question: if X is an empty set, it is well known that the inequality Card X ≤ Card Y holds (Y is an nonempty set here), but is there an bijective mapping of X onto some subset of Y? I mean X is empty, how can we construct the bijective? Incidentally, my English is poor, if I don't make myself clear, please just tell me, I'll try to express it more clearly.

REPLY [1 votes]: Suppose that $X=\emptyset$. Consider the identity function $\text{id}\colon X\to\emptyset$. It is clear that $\emptyset\subseteq Y$ and that $\text{id}$ is a bijection, because it is vacously injective and surjective.


TITLE: How is this a matrix representation of $a+ib$?
QUESTION [0 upvotes]: Could somebody explain how this matrix represents $a+ib$? Really not sure what I’m missing here.

REPLY [1 votes]: Here's another way to think about this correspondence, using linear algebra. Think of $\Bbb{C}$ as a two-dimensional vector space over $\Bbb{R}$. Then, complex multiplication by a fixed number $a + ib$ is a linear map. That is, if we let $T_{a+ib}(z) = (a + ib)z$, for any $z_1, z_2 \in \Bbb{C}$ and $\lambda \in \Bbb{R}$, we have $T_{a+ib}(z_1 + z_2) = T_{a+ib}(z_1) + T_{a+ib}(z_2)$ and $T_{a+ib}(\lambda z_1) = \lambda T_{a+ib}(z_1)$.
Now, $B = \{1, i\}$ forms the standard ordered basis for $\Bbb{C}$, and we can compute the matrix for $T$ under this basis. We compute
\begin{align*}
T_{a+ib}(1) &= (a + ib)1 = a + ib \implies [T_{a+ib}(1)]_B = \begin{bmatrix}a \\ b\end{bmatrix} \\
T_{a+ib}(i) &= (a + ib)i = -b + ia \implies [T_{a+ib}(1)]_B = \begin{bmatrix}-b \\ a\end{bmatrix}.
\end{align*}
Thus, our matrix representation is
$$M(a + ib) = \begin{bmatrix} a & -b \\ b & a\end{bmatrix}.$$
Now, note that
$$T_{a + ib}T_{c + id}(z) = (a + ib)(c + id)z = T_{(a + ib)(c + id)}(z).$$
We also get
$$T_{a + ib}(z) + T_{c + id}(z) = (a + ib)z + (c + id)z = (a + ib + c + id)z = T_{a + ib + c + id}(z).$$
In terms of matrices, we get
\begin{align*}
M(a + ib) + M(c + id) &= M(a + ib + c + id) \\
M(a + ib)M(c + id) &= M((a + ib)(c + id)).
\end{align*}
In short, the matrix $\begin{bmatrix} a & -b \\ b & a\end{bmatrix}$ is the standard matrix for the linear transformation of multiplying by $a + ib$, hence multiplication and addition are respected, and the matrices act identically to the complex numbers.


text:
\section{\name} \label{s:design}

\name is a decentralized algorithm that adaptively {\em learns} to form optimal peer connections, purely based on a node's interactions with its neighbors.
Unlike hand-crafted protocols which often require extensive manual tuning to optimize protocol parameters for individual blockchain networks, \name is a flexible learning algorithm that automatically finds the best topology for any network setting.
In \namens, nodes continuously monitor the promptness of block delivery from each of their neighboring nodes, and decide whether to retain their neighbors or explore connecting to other potentially better-connected peers.
Since each node tries to locally find the best set of neighbors it can connect to, \name naturally  benefits the self-interests of peers.
In \S\ref{s:eval} we show through extensive experimental evaluations, that our protocol also globally optimizes block propagation delays under diverse settings.

\subsection{Algorithm Overview}

\name operates on top of existing block distribution protocols, and does not change the format of blocks or the gossip protocols used for broadcasting them.
Instead it simply decides what is the best set of neighbors for a node to connect to, for a given block size and gossip protocol.
Starting from an arbitrary initial set of neighbors (e.g, obtained randomly from a bootstrapping server), a node in \name periodically evaluates its current set of neighbors, to decide which neighbors offer the fastest connectivity to the rest of the network.
Connections to those neighbors providing a good connectivity are retained, while the rest are disconnected.
Additionally, \name also periodically connects to a small number of random nodes, as a means to discover previously unknown but potentially well-connected peers.

In \namens, a neighbor is evaluated purely based on timestamp measurements of when blocks, or advertisements for blocks, were received from the neighbor.\footnote{Our protocol is general, and can also be used with timestamp measurements of transactions received from neighbors.}
Based on these measurements, a real-valued {\em score} is computed and assigned to each neighbor, which is then used to decide which subset of neighbors to retain.
Using block reception times to score neighbors, is a key novelty in \name and has several advantages compared to algorithms discussed in \S\ref{s:baseline}.
A node is identified only by its IP address, and not based on auxiliary information such as its geographical location.
This makes our algorithm robust to geo-spoofing attacks.
Moreover, by explicitly using block arrival times for scoring neighbors, \name automatically takes into account heterogeneities, such as variations in link latencies across geographically separated nodes, and variations in hash power.
The resulting topology therefore, has a good connectivity to nodes with high hash power, rather than good connectivity in a simpler graph theoretic sense (e.g., low diameter).

\begin{algorithm}[t]
\DontPrintSemicolon
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{
neighbors $\Gamma_v$, outgoing neighbors $\Gamma_v^o$, set of blocks $B$ mined during the round, and observation set $\mathcal{O}_{v}$
}
\Output{updated set of outgoing neighbors $\Gamma_v^o$ for next round}
\tcc{Score each neighbor based on measurements collected in $\mathbb{O}_v$ using a scoring algorithm (see \S\ref{s:independent}, \S\ref{s:groupscoring} for different scoring methods)}
score($u$) $\leftarrow$ \textsc{ScoringAlgorithm}$(\mathbb{O}_v)$, for each ngbr. $u \in \Gamma_v^o$ \;
\tcc{Retain subset of $d_v$ neighbors with best score}

$\Gamma_v^o \leftarrow \{ u \in \Gamma_v^o: \text{score}(u) \in \text{ best } d_v \text{ scores of nodes in } \Gamma_v^o  \}$ \;
\tcc{Additionally connect to $e_v$  random peers for exploration}
$\Gamma_v^o \leftarrow \Gamma_v^o \cup (e_v \text{ randomly chosen neighbors from } V) $
\caption{{\sc \namens:} Algorithm template for updating neighbors of node $v$ after each round.}
\label{algo:highlevel}
\end{algorithm}

To simplify our exposition, we present \name (Algorithm~\ref{algo:highlevel}) under the network model of \S\ref{sec:model}.
The algorithm proceeds in rounds, where each round spans the time taken to mine and broadcast $K$ unique blocks $B= \{b_1, b_2, \ldots, b_K \}$ over the \pp network.

For a node $v \in V$, let $\Gamma_v$ denote the set of $v$'s neighbors in $G$, and let $\Gamma^o_v \subseteq \Gamma_v$ denote $v$'s outgoing neighbors.
When a block $b \in B$ is broadcast during a round, we let $t_{u,v}^b$ be the local time at $v$ when $b$ was received from neighbor $u \in \Gamma_v$.
We set $t_{u,v}^b = \infty$ if block $b$ was never relayed to $v$ by $u$.
During a round, each node $v$ collects information about when each block was received from its neighbors in the form of an observation set $\mathbb{O}_v = \{ (b, u, t_{u,v}^b) : b \in B, u \in \Gamma_v \}$.

Note that it is possible for $v$ to hear about a block for the first time from a non-outgoing neighbor.

The tuples collected in $\mathbb{O}_v$ allows \name to rate how quickly a neighbor relays blocks relative to other neighbors, and retain connections to the best subset of $d_v$ (e.g., $d_v = 6$) neighbors at the end of each round.
Neighbors are evaluated using a scoring function, which estimates the maximum delay taken by a neighbor to forward 90\% of blocks to the node $v$.

In addition, \name also connects to a small number $e_v$ (e.g., $e_v = 2$) of random peers during each round, for discovering previously unknown peers with good connectivity.

We propose two different scoring methods, depending on whether each neighbor is scored individually (\S\ref{s:independent}), or groups of neighbors are jointly assigned a score (\S\ref{s:groupscoring}).
In the latter case, the score is an estimate of the maximum delay taken by the group of neighbors as a whole to forward 90\% of blocks to $v$.
The joint scoring of different neighbor groups is better suited to our objective, since each peer ultimately just desires to receive blocks as fast as possible, regardless of which specific neighbor forwards the block.
Certain blocks may be relayed fast by some neighbors, while other blocks are relayed fast by the remaining neighbors---as long as, together, the set of neighboring nodes result in a quick delivery of a majority of blocks, it is beneficial for the node.

However, accurately evaluating scores for all possible groups of neighbors is computationally expensive, and therefore we propose faster approximate methods.
In our evaluations (\S\ref{s:eval}), we find both the independent scoring and approximate joint scoring methods to be competitive.

\subsection{Scoring Each Neighbor Individually}
\label{s:independent}

\subsubsection{Vanilla Scoring} \label{s:vanillascore}
We first consider a simple scoring method, called \textsc{VanillaScoring}, to illustrate how for each neighbor $u \in \Gamma_v^o$ of a node $v$, the timestamps $t_{u,v}^b$ of blocks $b \in B$ broadcast during a round can be used to estimate $u$'s score.

Recall that a timestamp $t_{u,v}^b$ recorded in the observation set $\mathbb{O}_v$ of a node $v$ corresponds to the local wall-clock time when the block $b$ was received at $v$.
In order to judge how well a neighbor is connected to the rest of the network, it is desirable to know the {\em relative} time between when a block was mined, and when it was delivered by the neighbor (\ie the propagation delay).
However, as it is difficult for a node $v$ to know the precise time when a block was mined, we use the relative time differences between when a block is forwarded by different neighbors, as a proxy for the propagation delay.
For a block $b$, the first time it was received by $v$ from some neighbor is at time $t_v^b := \min_{u\in \Gamma_v} t_{u,v}^b$.

The timestamps in $\mathbb{O}_v$ are then revised relative to times blocks were first received by $v$, and a time-normalized observation set $\tilde{\mathbb{O}}_v$ is computed as
\begin{align}
\tilde{\mathbb{O}}_v = \{ (b, u, t_{u,v}^b - t_v^b): u \in \Gamma_v, b \in B  \}.
\end{align}

In \textsc{VanillaScoring}, the score for a neighbor $u \in \Gamma_v^o$ is simply computed as the 90th percentile of the multi-set of relative timestamps $\tilde{T}_{u, v} := (\tilde{t}: (b, u, \tilde{t}) \in \tilde{\mathbb{O}}_v)$ observed in a round.
This scoring approach naturally reflects a node's preference to retain an outgoing neighbor from which it received transactions relatively earlier.
The lower the score for a neighbor, the higher is the preference for node $v$ to retain the neighbor in next round.

\subsubsection{UCB Scoring}
\label{sec:ucb}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.48\textwidth]{fig/ucb.pdf}
    \caption{Observe that $\text{lcb}(u_{4}) \geq  \text{lcb}(u)$ $\forall u \in \Gamma_v^o $, $\text{ucb}(u_{3}) \leq \text{ucb}(u)$ $\forall u \in \Gamma_v^o $. Moreover,  $\text{lcb}(u_{4}) > \text{ucb}(u_{3})$ and so the neighbor to be removed ($bad\_nbr$) is $u_{4}$.}
    \label{fig:ucb}
    \vspace{-5mm}
\end{figure}

In the \textsc{VanillaScoring} method, propagation delay estimates for individual neighbors (90th percentile of relative timestamp observations) are likely to be noisy if the number of blocks $|B|$ in a round is small.
The noise here arises due to the randomness in which node mines a block each time (\S\ref{s: background}).
While increasing $|B|$ by increasing the duration of each round improves accuracy of our estimates, it also slows down the overall convergence time of the algorithm.\footnote{We illustrate convergence of \name empirically in our experiments in \S\ref{s:eval}.}
To improve the accuracy of the \textsc{VanillaScoring} estimates, without sacrificing on convergence time, we propose a second scoring method motivated by the Upper Confidence Bound (UCB) algorithm for multi-armed bandits~\cite{auer2002using}.

In the \textsc{UCBScoring} method, a node maintains an estimate of propagation delay  for a neighbor, based on observed timestamps, and also computes lower and upper confidence bounds for it.
If a neighbor has been connected to $v$ for longer than one round, then the estimates and confidence bounds for the neighbor are computed not only using the observations $\mathbb{O}_v$ made during the current round, but also using past observations available for the neighbor.
For a neighbor $u\in \Gamma_v^o$, let $\tilde{T}_{u,v}(-i)$ denote the multi-set of relative timestamps obtained during a round $i$ rounds before the present round.
Supposing node $u$ has been $v$'s neighbor for the past $r_{u,v}$ rounds.
In the \textsc{UCBScoring} approach, we use a multi-set of relative timestamp observations $\dbtilde{T}_{u,v} = (\tilde{t}: (b, u, \tilde{t}) \in \cup_{i=0}^{-r_{u,v}} \tilde{T}_{u,v}(-i) \text{ such that } \tilde{t} < \infty )$ for a neighbor $u$.\footnote{Note that the union $\cup_{i=0}^{-r_{u,v}} \tilde{T}_{u,v}(-i)$ is a multi-set union.}
The propagation delay for $u$ is estimated as the 90th percentile of $\dbtilde{T}_{u, v}$,

and its
confidence bounds are computed as
\begin{align}
\text{ucb}(u) = \mathtt{90percentile}(\dbtilde{T}_{u,v}) + c\sqrt{\frac{\log(|\dbtilde{T}_{u,v}|)}{2 \times |\dbtilde{T}_{u,v}|}} \label{eq:ucb} \\
\text{lcb}(u) = \mathtt{90percentile}(\dbtilde{T}_{u,v}) - c\sqrt{\frac{\log(|\dbtilde{T}_{u,v}|)}{2 \times |\dbtilde{T}_{u,v}|}}, \label{eq:lcb}
\end{align}
where ucb and lcb denote the upper and lower confidence bounds respectively~\cite{auer2002using}, and $\mathtt{90percentile}(\cdot)$ computes the 90th percentile of its argument.
At the end of each round, in the \textsc{UCBScoring} approach we check whether $\max_{u\in\Gamma_v^o}(\text{lcb}(u)) > \min_{u\in\Gamma_v^o}(\text{ucb}(u))$, and if so, $v$ disconnects from the neighbor $\arg \max_{u\in\Gamma_v^o} (\text{lcb}(u))$ and connects to a random new neighbor instead; otherwise the current set of neighbors are retained for the next round.

Figure~\ref{fig:ucb} shows an example of upper and lower confidence bounds for a set of eight neighbors.
Node $u_4$ will be disconnected at the end of the round in this example.

Updating the set of neighbors this way based on confidence intervals, avoids accidentally disconnecting from a well-connected neighbor that has a poor 90th percentile score due to randomness in mining and lack of sufficient measurement samples.

\begin{figure*}[!tbp]
  \centering
  \subfigure[]{\includegraphics[width=0.71\textwidth]{fig/UniformHash.png}\label{fig:UniformHash}}

  \subfigure[]{\includegraphics[width=0.225\textwidth]{fig/ExpDistributedHash.png}\label{fig:ExpDistributedHash}}

  \caption{Minimum delay to nodes totaling 90\% of network's hash power on random, geographic, \namens-Vanilla, \namens-Subset, \namens-UCB, Kademlia and the fullly-connected graph (denoted as ideal). (a) All nodes have the same hash power. (b) Nodes have a hash power drawn from an exponential distribution.

  }
  \label{fig:Hash}
      \vspace{-3mm}
\end{figure*}

\subsection{Scoring Groups of Neighbors Jointly}
\label{s:groupscoring}

Next, we present an alternative scoring method, \textsc{SubsetScoring}, where scores are assigned  to each group $\gamma_v \subset \Gamma_v^o$ of neighbors (of a certain cardinality, e.g., 6) instead of to individual nodes.
At the end of a round, the group of neighbors having the best score are retained and neighbors that are not part of this group are disconnected.
As before, a small number of neighboring connections are made randomly in each round to encourage exploration.

To avoid the computational overhead of exhaustively evaluating scores for all possible subsets of neighbors, we consider a simpler, but approximate, greedy approach in which the neighbors to be retained are selected one by one.

First, the algorithm selects the neighbor $u_1 \in \Gamma_v^o$ having the best 90th percentile score in the relative timestamp observation multi-set $\tilde{T}_{u,v}$ (\S\ref{s:vanillascore}).
If $k$ neighbors $u_1, u_2, \ldots, u_k$ have been selected, the $(k+1)$st neighbor is selected by first computing a transformed observation set $\dbtilde{O}_v(u_1,u_2,\ldots,u_k) = \{ (b, u, \min(\tilde{t}_{u,v}^b, \min_{1\leq i \leq k} \tilde{t}_{u_i, v}^b)): b \in B, u \in \Gamma_v^o \backslash \{u_1, u_2, \ldots, u_k\} \} $, followed by the multi-set of relative timestamps $\dbtilde{T}_{u,v}(u_1,\ldots,u_k) = (\dbtilde{t}: (b, u, \dbtilde{t}) \in \dbtilde{O}_v(u_1,\ldots, u_k))$ for each neighbor $u \in \Gamma_v^o \backslash \{u_1,\ldots, u_k \}$.
The transformation essentially avoids penalizing nodes that do not have good connectivity to a certain part of the network, to which the neighbors already chosen have a good connectivity.
The node $u \in \Gamma_v^o \backslash \{u_1,\ldots, u_k \}$ with the lowest $\mathtt{90percentile}(\dbtilde{T}_{u,v}(u_1,\ldots,u_k))$ value is finally selected as the $(k+1)$st choice.

Thus, each time a neighbor is chosen whose connectivity to the rest of the network best complements the other neighbors selected thus far.

As in \S\ref{s:independent}, once $(d_{v} - e_{v})$ neighbors are selected, node $v$ also randomly selects $e_v$ nodes as part of exploration.
This set of $d_v$ nodes are $v$'s updated set of neighbors that it will monitor in the next round.


TITLE: What's the point with equilibrium in thermodynamics?
QUESTION [6 upvotes]: All the thermodynamics books I saw until now state that in thermodynamics we are mainly concerned with equilibrium states (I know there's "non-equilibrium thermodynamics", but I'm interested on the standard viewpoint).
Now, why is that? Books try to explain this in terms of the implications in measurements, but I don't feel comfortable with experimental physics, so that I just get more confusing with this kind of argument.
Why do we need to consider states of equilibrium? And also, what really is that equilibrium? I think it's different from the classical mechanics notion of equilibrium where we demand the net force to be zero at an equilibrium state. Does equilibrium in thermodynamics have any relationship with this notion of equilibrium in mechanics?

REPLY [6 votes]: First of all, from a computation point of view, thermal equilibrium is much simpler than out-of-equilibrium. In equilibrium, the state of the system is (more or less) straightforwardly defined by its Hamiltonian and a few thermodynamic parameters. Out-of-equilibrium contains everything that is not equilibrium and ranges from dropping a pencil to heavy ion collisions at CERN.
Equilibrium is, however, an important part of physics, because it is the asymptotic state systems normally assume if we wait long enough. Even though there are infinitely many more out-of-equilibrium states, most of them evolve to thermal equilibrium after a while and the simple calculation provides useful information.
But that's the easy part of your question. The real question is: "What is thermal equilibrium?" First, you are right; thermal equilibrium is not the same as mechanical equilibrium. Being in mechanical equilibrium just means that none of your parts are moving. In thermal equilibrium however, it is only the thermodynamic parameters (average energy, temperature, pressure, volume, average number of particles, etc.) that do not change. Individual particles move around wildly.
First note that being in thermal equilibrium is a relative property. A system is equilibrated with another system. For example, when you pour a cup of tea, the water starts by swirling around. You can say that when the swirling has died out your tea is equilibrated (although I would call that mechanical equilibrium). On the other hand, you could wait an hour until you tea is a room temperature and then say that it's at equilibrium.
However, if you open the window, turn off the heating and come back a couple hours later your tea will be colder than room temperature and you will say that the tea has equilibrated with the local weather system. You can go on like this almost forever.
The truth is that there is always a (space or/and time) scale at which your system is not equilibrated. If you leave your tea for a century on the moon, you might notice that your the mug has changed shape. Glass is actually a very complicated system that has a (very slow) evolution of its own which is comparable to hyper-viscous fluids. Before you talk about equilibrium you must first restrict your observation range.
A super cool example of this is the free falling Bose condensate. Experimental physicists are studying the equilibrium properties of an ultra-cold Bose gas in zero gravity. To do so, they prepare their gas in an electromagnetic container and drop the whole apparatus down a high (110 m) tower. During the fall, the gas equilibrates and they make their measurements. After a few (4.5) seconds, the apparatus reaches the ground and the gas is dispersed. Even though the whole system is clearly out-of-equilibrium the gas is at equilibrium during the time of the fall.
But this still does not really answer your question. In practice, theoretical physicists define thermal equilibrium with statistical physics as the state of matter that has the largest entropy consistent with the macroscopic constraints of the system (fixed energy, volume, numbers of particles, etc.). This is the micro-canonical ensemble. Then, computing equilibrium properties is a well-defined mathematical procedure.
This definition is valid for a closed system and can be used to define an "absolute" thermal equilibrium. It says that the system is equilibrated when its dynamics visits all the micro-states that are consistent with the macroscopic constraints with the same probability.
The dynamics of the microscopic degrees of freedom are maximally disordered. In practice however, no system is really closed. Moreover, if you can find a closed system, it will take an infinite time to equilibrate because energy conserving dynamics never really forgets its initial conditions.
Another definition from Wikipedia is:
"Two physical systems are in thermal equilibrium if no heat flows between them when they are connected by a path permeable to heat."
This definition is a much more practical, but it is only relative. You first must pick a system and declare it to be equilibrated. Then you can compare it to other systems and check weather they are equilibrated as well. Moreover, it needs a definition of heat (the non-mechanical part of the energy that is spontaneously transferred in between two non equilibrated systems) to be useful and heat requires a definition of equilibrium to be useful.
Ok, I can't think of anything more to say. I hope that I didn't confuse you even more. This is a deep and difficult question. Intuitively, it is clear when a system is equilibrated. In theory, however, the definition can be quite tricky. Note however that physicists to not spend all their time thinking about the definition of thermal equilibrium. In experiments you can look at you system, nod and declare it to be equilibrated (sometimes you are wrong and that's when the interesting things start). In theory, the computation of equilibrium properties is a well-defined mathematical procedure which may seem a little remote from reality, but it works really well.


TITLE: Arrange the integers 1-100 in such a way that no eleven of the numbers selected from left to right form a strictly increasing or decreasing sequence
QUESTION [5 upvotes]: Arrange the integers 1-100 in such a way that no eleven of the numbers selected from left to right (adjacent or otherwise) form a strictly increasing or decreasing sequence.  (This means if 11 numbers are selected from anywhere in the pattern they cannot be in an increasing or decreasing pattern).

I think I have to divide the 100 integers into 10 groups, all with 10 integers.  But that's all I've thought about.

REPLY [0 votes]: I'd like to point out another construction:
$$91,81,71,\ldots,92,82,72,\ldots,93,83,73,\ldots
$$
If you want an increasing sequence, no matter which number you choose you must pass at each step to the next block of ten numbers $\implies$ at most ten choices.
If you want a decreasing sequence you must lower at each step the ten's figure $\implies$ at most ten choices.