text:
\section{Introduction}
Ever since the study of hydrogen atom inside an impenetrable spherical enclosure \cite{michels37},
confinement of quantum systems has witnessed many burgeoning activity in past few decades. This
work was motivated by an attempt to understand effects of extreme pressure on electronic states.
In such extremely small spatial dimensions, many fascinating phenomena occur in a quantum confined system,
relative to the respective free system. Some of these relate to, e.g., thermodynamic properties in
non-ideal gases, anharmonic effects in solids, impurity binding in quantum wells, partially ionized
plasmas, mesoscopic scale artificial structures, etc. Gradually their importance was realized in
various potential applications in physics and chemistry, such as quantum wells, quantum wires, quantum
dots, etc. They have also relevance in the development of numerous nano-sized circuits including quantum computers.
Usually, their unique physical, chemical properties are attributed to complex energy changes associated with them.
Most widely studied quantum systems are particle in a box, harmonic oscillator, H atom, He and other
many-electron atoms, as well as H$_2^+$, H$_2$ and other molecules. The literature is vast; here we mention
a few representatives \cite{fowler84, froman87, yngve88, jaskolski96, connerade00, buchachenko01,
gravesen05, heiss05}.

Confinement problem in 1D confined harmonic oscillator (CHO) has been theoretically investigated by a number of workers over a
long period of time \cite{vawter68,navarro80,fernandez81,arteca83,taseli93,vargas96,sinha99,aquino01,campoy02}.
For example, the effect of finite boundaries on a 1D CHO inside a potential enclosure was studied by means of WKB method
\cite{vawter68}. Perturbative, asymptotic and Pad\'e approximant solutions for boxed-in harmonic and inverted
oscillators were reported \cite{navarro80}. Eigenfunctions, eigenvalues in such 1D potentials were also
obtained by means of a hypervirial method \cite{fernandez81,arteca83}. Accurate energies of 1D polynomial potentials
having single and multiple wells inside a box were calculated through a Rayleigh-Ritz variation method by using
a basis set of trigonometric functions \cite{taseli93}. A robust, strongly convergent numerical method has
been proposed for harmonic, quartic and sextic oscillators \cite{vargas96}. Also, the trapped harmonic and quartic
oscillators have been studied by a WKB method with appropriate boundary condition \cite{sinha99}. This employed a modified
airy function method that ultimately leads to a modified Bohr-Sommerfeld-type quantization rule. Eigenvalues, dipole moments,
Einstein coefficients of CHO have been considered by perturbation method \cite{aquino01} as well. Symmetric and asymmetric confinement
was studied in \cite{campoy02} by a power series expansion and numerical method.

In parallel to the 1D problem mentioned above, some attention was been paid for similar studies in 2D, 3D and higher
dimension, however with lesser intensity \cite{fernandez81a,navarro83,marin91,aquino97,taseli97a,taseli97,sinha03,filho03,sen06,
montgomery07,jaber08,stevanovic08a,stevanovic08, montgomery10,serrano13}. Several unique phenomena occur in such systems,
especially related to \emph{simultaneous, incidental and interdimensional} degeneracy \cite{sen06,jaber08,stevanovic08a,
stevanovic08,montgomery07}. In one of the earliest studies a hypervirial treatment was suggested for multidimensional isotropic
bounded oscillators, including 3D CHO \cite{fernandez81a}. The 2D and 3D CHOs enclosed in circular and spherical boxes were
considered in \cite{navarro83} by a Rayleigh-Schr\"dinger perturbative expansion as well as Pad\'e approximant solution.
A variational method \cite{marin91} was proposed where the trial function was constructed as a product of ``free" solutions of
corresponding Schr\"odinger equation. However, the first systematic and accurate ground, excited states of 3D CHO (in terms
of energies, eigenfunctions, spatial expectation values) with respect to box size were obtained in variational calculation
of \cite{aquino97}. Later, results were also obtained by a WKB method \cite{sinha03}. A super-symmetric method
\cite{filho03} also offered reasonably accurate results. The $N$-dimensional CHO enclosed in an impenetrable spherical cavity
was also computed by searching for the roots of hypergeometric function $_1F_1 (a,b,z)$ \cite{jaber08}. Later, high-precision
energies for $N$-dimensional CHO were presented by exploiting certain properties of hypergeometric function within the MAPLE
computer algebra system \cite{montgomery10}. Very recently, a combination of WKB method and a proper quantization rule has been
advocated for CHO energy levels \cite{serrano13}. Energy characteristics of a 2D isotropic CHO, enclosed in a
symmetric box were followed through annihilation and creation operators coupled with the infinitesimal operators of
SU(2) group \cite{stevanovic08}. Likewise, characteristic features in energy spectrum of 3D CHO were established by invoking
analytical properties of Bessel and confluent hypergeometric functions. However, the most extensively studied confined system
is H atom. A vast amount of reference exists on the subject emphasizing different kinds of confinement and theoretical
methods \cite{aquino95,burrows06,aquino07,ciftci09}.

In present communication, we are interested in the confinement studies in 3D quantum polynomial oscillators. It may be
noted that while all these above methods produce reasonably good-quality results, only two \cite{aquino97, montgomery10}
of these offer energies with ten or higher significant figure accuracy for 3D oscillators. Moreover, there is a lack of
good results in the \emph{low radius of confinement}, and \emph{higher excited states}. Further, while a substantial
amount of accurate results exist for enclosed H atom problem, same for 3D CHO is much less and almost none for other polynomial
potentials. We will use the generalized pseudospectral (GPS) method for this purpose, which in recent years, has been
successfully applied to a wide range of \emph{unconfined} physical and chemical systems. Some
of these are spiked harmonic oscillator, Hulth\'en, Yukawa, logarithmic, rational, power-law potentials, ro-vibrational
levels in molecules as well as ground and Rydberg states in atoms, etc. \cite{roy04, roy04a, roy04b, roy05, roy05a, sen06,
roy08}. Only in \cite{sen06}, however, this was employed for confined quantum states. There, a few low-lying states such
as $1s, 2p, 1d$ of 3D CHO were examined; additionally some degeneracy conditions were established.
However a detailed performance of the GPS method in case of \emph{confined} systems has not been made so far. In this
work, we want to test its validity and relevance in such a context, which could extend its domain of applicability to
larger set of problems. To this end, eigenvalues, eigenfunctions, expectation values are reported for low, high states. A detailed
variation of eigenvalues with box size is also presented. Correlation between energies in \emph{free} and respective \emph{confined}
system is discussed. Further, a similar study is made on quartic oscillator, which was not done before. Finally we consider
confinement in even-degree polynomial oscillators (up to 20) in terms of changes in ground-state energy with radius of
confinement. Section II gives a brief outline of the method used. Results are discussed in section III. We conclude with a
few remarks in section IV.

\section{Method of calculation}
The GPS method has been found to be very successful for various physical and chemical systems as evidenced by the following
applications \cite{roy04, roy04a, roy04b, roy05, roy05a, sen06, roy08}. Therefore here we highlight only the essential aspects.
Unless otherwise mentioned, atomic unit is employed.

The single-particle, non-relativistic time-independent radial Schr\"odinger equation can be written in following form (the
problem is separable in radial and angular variables),
\begin{equation}
\left[-\frac{1}{2} \ \frac{\mathrm{d^2}}{\mathrm{d}r^2} + \frac{\ell (\ell+1)} {2r^2}
+v(r) +v_c(r) \right] \psi_{n,\ell}(r) = E_{n,\ell}\ \psi_{n,\ell}(r)
\end{equation}
where $v(r)$ is a polynomial potential of degree $2K$ containing only the dominant term, i.e., $v(r) = \frac{1}{2} r^{2K}$.
In this work we consider $K=1,2,3, \cdots , 10$, while $n$, $\ell$ signify usual radial and angular momentum quantum
numbers respectively. Last term in square bracket represents the confinement potential ($r_c$ is the radius of confining
spherical box),
\begin{equation} v_c(r) = \begin{cases}
+\infty \ \ \ \ r> r_c  \\
0,  \ \ \ \ \ \ \ r \leq r_c   \\
 \end{cases}
\end{equation}
This equation needs to be solved with Dirichlet boundary condition $\psi_{n, \ell}(0)=\psi_{n,\ell}(r_c)=0$.

A very distinctive feature of this approach is that it allows one to work in a \emph{nonuniform}, \emph{optimal} spatial
discretization; a coarser mesh at larger $r$ and a denser mesh at smaller $r$, while maintaining similar accuracies at both
regions. Thus, compared to many other methods, much smaller number of grid point often suffices to recover
very good accuracy for low and high states.

At first, a function $f(x)$ defined in an interval $x \in [-1,1]$ is approximated by an N-th order polynomial $f_N(x)$,
\begin{equation}
f(x) \cong f_N(x) = \sum_{j=0}^{N} f(x_j)\ g_j(x),
\end{equation}
so that the approximation is \emph {exact} at \emph {collocation points} $x_j$, i.e., $ f_N(x_j) = f(x_j).$
In the Legendre pseudospectral method used here, $x_0=-1$, $x_N=1$, while  $x_j (j=1,\ldots,N-1)$ are obtained from roots of
first derivative of Legendre polynomial $P_N(x)$ with respect to $x$, i.e., $P'_N(x_j) = 0.$
Cardinal functions, $g_j(x)$ in Eq.~(3) satisfy the relation, $g_j(x_{j'}) = \delta_{j'j}$. Next, one can map the
semi-infinite domain $r \in [0, \infty]$ onto finite domain $x \in [-1,1]$ by a transformation $r=r(x)$ and introduce a
nonlinear algebraic mapping of following form,
\begin{equation}
r=r(x)=L\ \ \frac{1+x}{1-x+\alpha},
\end{equation}
where L and $\alpha=2L/r_{max}$ are two adjustable mapping parameters. Now, introducing a transformation of the type
$\psi(r(x))=\sqrt{r'(x)} f(x), $
followed by a symmetrization procedure leads to a \emph {symmetric} matrix eigenvalue problem which can be easily solved by
standard available routines (NAG libraries used) to yield accurate eigenvalues and eigenfunctions.

Sample calculations were performed for a sufficiently large sets of mapping parameters to monitor the accuracy and reliability
of present method, so as to produce ``stable'' results with respect to reference results. This lead to a choice of
$\alpha=25, N=200$, which appeared to be satisfactory for the problem at hand. Results in various tables are reported only up
to the precision that maintained stability and they are {\em truncated} rather than {\em rounded-off}. Thus, they may be
considered as correct up to the decimal place given.

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table1}Energies (a.u.) of 3D CHO for $n=\{0,1\}; \ell=\{0,1,2\}$ states. PR means Present Result.}
\begin{ruledtabular}
\begin{tabular}{l|ll|ll}
$r_c$  & E$_{0,0}$ (PR)   & E$_{0,0}$ (Literature) &  E$_{0,1}$ (PR)  &  E$_{0,1}$ (Literature)   \\
\hline
0.1    & 493.48163346     &  493.481632\footnotemark[1]$^,$\footnotemark[2]
       & 1009.5383008     &  1009.538302\footnotemark[1]$^,$\footnotemark[2]         \\
0.3    & 54.843855432     &  54.843855\footnotemark[1]$^,$\footnotemark[2]
       & 112.18757119     &  112.187571\footnotemark[1]$^,$\footnotemark[2]         \\
0.5    & 19.774534180     & 19.774534\footnotemark[1]$^,$\footnotemark[2]$^,$\footnotemark[3],19.774534179\footnotemark[4]$^,$\footnotemark[5]
       & 40.428276496     &  40.428277\footnotemark[1]$^,$\footnotemark[2],40.428276497\footnotemark[4],40.428276496\footnotemark[5]   \\
1.0    & 5.0755820154     & 5.0755820\footnotemark[3],5.0755820152\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],4.98501\footnotemark[7]
       & 10.282256939     & 10.282256939\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],10.13941\footnotemark[7] \\
1.5    & 2.5049761786     & 2.502471\footnotemark[1],2.504976\footnotemark[2],2.5049761\footnotemark[3],
       & 4.9035904193     & 4.901782\footnotemark[1],4.903590\footnotemark[2],            \\
       &                  & 2.5049761785\footnotemark[4]$^,$\footnotemark[6],2.54357\footnotemark[7]
       &                  & 4.9035904194\footnotemark[4]$^,$\footnotemark[6],4.87758\footnotemark[7]                                                 \\
2.0    & 1.7648164388     & 1.732515\footnotemark[1],1.764816\footnotemark[2],
       & 3.2469470987     & 3.224167\footnotemark[1],3.246947\footnotemark[2],   \\
       &                  & 1.7648087\footnotemark[3],1.7648164387\footnotemark[4]$^,$\footnotemark[5]
       &                  & 3.2469470987\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],3.31861\footnotemark[7]                     \\
3.0    & 1.5060815273     & 1.544195\footnotemark[1],1.506082\footnotemark[2],1.5060815272\footnotemark[4]
       & 2.5312924665     & 2.688286\footnotemark[1],2.531292\footnotemark[2],2.5312924666\footnotemark[4]  \\
4.0    & 1.5000146030     & 1.504181\footnotemark[1],1.5000015\footnotemark[2],1.50000146030\footnotemark[4]
       & 2.5001437781     & 2.517144\footnotemark[1],2.500144\footnotemark[2],2.5001437781\footnotemark[4]   \\
5.0    & 1.5000000037     & 1.500581\footnotemark[1],1.500000\footnotemark[2],1.5000000036\footnotemark[4]$^,$\footnotemark[5]
       & 2.5000000584     & 2.502500\footnotemark[1],2.500000\footnotemark[2],2.5000000584\footnotemark[4]$^,$\footnotemark[5] \\
6.0    & 1.5000000000     & 1.5000000000\footnotemark[4]
       & 2.5000000000     & 2.5000000000\footnotemark[4]      \\
\hline
       & E$_{0,2}$ (PR)    & E$_{0,2}$ (Literature) &  E$_{1,0}$ (PR)  &  E$_{1,0}$ (Literature)   \\
\hline
0.1    & 1660.8752892     &
       & 1973.9224834     &                             \\
0.3    & 184.56119633     &
       & 219.33897241     &                             \\
0.5    & 66.489756534     & 66.489756534\footnotemark[4]
       & 78.996921147     & 78.996921150\footnotemark[4]$^,$\footnotemark[5]                                          \\
1.0    & 16.827777109     & 16.827777109\footnotemark[4]
       & 19.899696502     & 19.899696501\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],19.78300\footnotemark[7]  \\
1.5    & 7.8717304875     & 7.8717304877\footnotemark[4]
       & 9.1354220880     & 9.1354220876\footnotemark[4]$^,$\footnotemark[6],9.10021\footnotemark[7]                 \\
2.0    & 5.0100408655     & 5.0100408656\footnotemark[4]
       & 5.5846390792     & 5.5846390790\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],5.59685\footnotemark[7]   \\
3.0    & 3.5982476989     & 3.5982476989\footnotemark[4]
       & 3.6642196451     & 3.6642196450\footnotemark[4]$^,$\footnotemark[6],4.01642\footnotemark[7]                                \\
4.0    & 3.5008420737     & 3.5008420738\footnotemark[4]
       & 3.5016915386     & 3.5016915385\footnotemark[4]                                                        \\
5.0    & 3.5000005566     & 3.5000005567\footnotemark[4]
       & 3.5000012215     & 3.5000012214\footnotemark[4]$^,$\footnotemark[5]                                   \\
6.0    & 3.5000000000     & 3.5000000003\footnotemark[4]
       & 3.5000000001     & 3.5000000000\footnotemark[4]                                                       \\
\hline
       & E$_{1,1}$ (PR)   & E$_{1,1}$ (Literature) &  E$_{1,2}$ (PR)  &  E$_{1,2}$ (Literature)   \\
\hline
0.1    & 2983.9775336     &
       & 4135.9634334     &                                                                \\
0.3    & 331.56849477     &
       & 459.56818797     &                                                                \\
0.5    & 119.40244526     & 119.40244525\footnotemark[4],119.40244526\footnotemark[5]
       & 165.48541838     &                                                                \\
1.0    & 30.013487593     & 30.013487592\footnotemark[4],30.013487591\footnotemark[5]$^,$\footnotemark[6],29.88263\footnotemark[7]
       & 41.547472167     & 41.547472166\footnotemark[6],41.40000\footnotemark[7]                                       \\
1.5    & 13.653740893     & 13.653740893\footnotemark[4],13.653740892\footnotemark[6],13.60644\footnotemark[7]
       & 18.805042927     & 18.805042927\footnotemark[6],18.74733\footnotemark[7]                                       \\
2.0    & 8.1595288818     & 8.1595288816\footnotemark[4]$^,$\footnotemark[5]$^,$\footnotemark[6],8.15237\footnotemark[7]
       & 11.093419194     & 11.093419194\footnotemark[6],11.07445\footnotemark[7]                                       \\
3.0    & 4.9138976907     & 4.9138976907\footnotemark[4]$^,$\footnotemark[6],5.05725\footnotemark[7]
       & 6.3076308117     & 6.3076308118\footnotemark[6],6.37769\footnotemark[7]                                        \\
4.0    & 4.5083304309     & 4.5083304308\footnotemark[4]
       & 5.5286815696     &                                                                            \\
5.0    & 4.5000105731     &  4.5000105730\footnotemark[4]$^,$\footnotemark[5]
       & 5.5000647985     &                                                                            \\
6.0    & 4.5000000011     &  4.5000000008\footnotemark[4]
       & 5.5000000098     &                                                                            \\
\end{tabular}
\end{ruledtabular}
\begin{tabbing}
$^{\mathrm{a}}$Ref.~\cite{navarro83}. \hspace{15pt}  \=
$^{\mathrm{b}}$As quoted in \cite{navarro83}. \hspace{15pt}  \=
$^{\mathrm{c}}$Ref.~\cite{fernandez81a}. \hspace{15pt}  \=
$^{\mathrm{d}}$Ref.~\cite{aquino97}. \hspace{15pt} \=
$^{\mathrm{e}}$Ref.~\cite{montgomery10}. \hspace{15pt} \=
$^{\mathrm{f}}$As quoted in \cite{serrano13}. \hspace{15pt} \=
$^{\mathrm{g}}$Ref.~\cite{serrano13}.
\end{tabbing}
\end{table}
\endgroup

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table2}Eigenvalues (in a.u.) of $n=8, \ell=\{0-8\}$ states of 3D CHO as function of $r_c$.}
\begin{ruledtabular}
\begin{tabular}{lllllll}
$\ell$  & $r_c=0.5$ & $r_c=1.5$       &  $r_c=2.5$     &  $r_c=3.5$      &   $r_c=4.5$     &  $r_c=10$   \\
\hline
0   &  1598.9175016  &  178.02733028   &  64.998075416   &  34.693293571   &  23.225703703   &  17.500000000  \\
1   &  1777.5046290  &  197.87206375   &  72.146061470   &  38.344628587   &  25.432849261   &  18.499999999  \\
2   &  1961.9446659  &  218.36830761   &  79.531522574   &  42.122176083   &  27.724249606   &  19.499999999  \\
3   &  2152.2122548  &  239.51291591   &  87.152525538   &  46.023630724   &  30.096639843   &  20.500000000  \\
4   &  2348.2769485  &  261.30226934   &  95.007188871   &  50.047065889   &  32.547442956   &  21.500000000  \\
5   &  2550.1056822  &  283.73252093   &  103.09370240   &  54.190838285   &  35.074586281   &  22.500000000  \\
6   &  2757.6642785  &  306.79974464   &  111.41033572   &  58.453522134   &  37.676374299   &  23.499999999  \\
7   &  2970.9183755  &  330.50002581   &  119.95544047   &  62.833862466   &  40.351398586   &  24.499999999  \\
8   &  3189.8339986  &  354.82951614   &  128.72744924   &  67.330741133   &  43.098472783   &  25.499999999  \\

\end{tabular}
\end{ruledtabular}
\end{table}
\endgroup

\section{Results and Discussion}
At first, in Table I, we present first six eigenvalues corresponding to radial quantum numbers $n=0$ and 1 having
$\ell=0,1,2,$ of 3D isotropic CHO in a spherical box with impenetrable walls. Depending on the box size, confinement
can be classified in three distinct regions, namely, \emph{small, intermediate} and \emph{large} $r_c$. Ten cage radii
were chosen for this purpose.  First definitive result of the lowest two states were presented through a
Rayleigh-Schr\"odinger-type perturbation expansion having free-particle in a box as the unperturbed system \cite{navarro83}.
They also computed these states employing various Pad\'e approximations. Here, we quote their $P[1/5]$ energies
in third column, while perturbation energies are omitted to save space. Perturbation and Pad\'e eigenvalues differ
amongst each other significantly, especially when the system is enclosed in a larger box (larger $r_c$). Their numerical
eigenvalues obtained by diagonalizing the Hamiltonian matrix in a basis of free particle-in-a-box eigenfunctions
appear to be superior to above both, and referred here. While these are decent initial estimates, present GPS
energies are significantly improved over these. Confinement in the intermediate region was studied for ground state by
means of a hypervirial method \cite{fernandez81a}. In this case, the accuracy generally becomes less precise as $r_c$
increases; for low $r_c$, these are more or less of similar quality as in \cite{navarro83}. Quite accurate eigenvalues
for all states except E$_{1,2}$ (in the range $r_c > 0.5$) have been reported through variational procedure \cite{aquino97}.
Here the two integers in subscript denote $n$, $\ell$ quantum numbers
respectively. Current energies are in excellent agreement with these values for whole range of $r_c$; in several occasions
exactly reproducing those of the reference. However the most accurate energies are those published in \cite{montgomery10};
these are obtained as roots of a transcendental equation written in terms of confluent hypergeometric functions.
The authors used familiar MAPLE algebra program to achieve impressive (as high as up to 100-digit) accuracy in eigenvalues.
These are available for $n=\ell=0,1$ states at selected $r_c$. Here also, the GPS results offer excellent agreement with
these energies. Very recently some of these states are also calculated by a combination of quantization rule and WKB
method \cite{serrano13}. These are also produced here for comparison. Obviously in all instances, isotropic free harmonic
oscillator (FHO) energies are recovered as $r_c \rightarrow \infty$.

\begin{figure}
\begin{minipage}[c]{0.40\textwidth}
\centering
\includegraphics[scale=0.45]{3dqho_l0_n0123456789.eps}
\end{minipage
\hspace{0.5in}
\begin{minipage}[c]{0.40\textwidth}
\centering
\includegraphics[scale=0.45]{3dqho_n0_l0123456789.eps}
\end{minipage
\caption{Energy changes (a.u.) in 3D isotropic CHO for (a) $l=0; n=0-9$ and (b) $n=0; l=0-9$ levels
respectively, as function of confining radius.}
\end{figure}

Next we proceed in Table II for sample results on high-lying states. In order to demonstrate the viability and efficiency
in such situations, nine states (having $\ell=0-8$) corresponding to $n=8$ are given. As in previous table, here
again we cover the entire domain of confinement choosing six representative $r_c$ values, \emph{viz.}, 0.5, 1.5, 2.5, 3.5,
4.5 and 10 a.u. respectively. As evident from above discussion, while a decent number of high-quality references exist
for confinement in low-lying states, there is a lack of such studies for higher excitations. Thus no literature values
could be quoted for any of these. We hope that they would be helpful in future calibration of other methodologies. Once
again, as box radius increases, energies of bounded system approach towards the 3D isotropic FHO eigenvalues.

\begin{figure}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{3dqho_ordering_223.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{3dqho_ordering_34.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{3dqho_ordering_56.eps}
\end{minipage}
\caption{Energy eigenvalues (a.u.) of (a) $(1d, 2s)$, $(1f, 2p)$, $(1g,2d,3s)$ (left), (b) $(1h,2f,3p)$, $(1i,2g,3d,3s)$
(middle), and (c) $(1l,2j,3h,4f,5p)$, $(1m,2k,3i,4g,5d,6s)$ (right) levels respectively, of 3D isotropic CHO as function
of cavity radius.}
\end{figure}

Energy variations of Tables I, II are vividly depicted in Figure 1. The left panel (a) gives such plots for ten
$s$-waves ($\ell=0$) having radial quantum numbers $n=0-9$, while in right panel (b), we consider same for ten
lowest states (having $\ell=0-9$ values) corresponding to the lowest $n$ quantum number. Energy axes in both
cases cover same range; whereas $r_c$ axes differ in two occasions. In both cases, however, confinement in very
small box radius is ignored to avoid high energy values, which makes these plots difficult to comprehend. To the best of our
knowledge, such energy plots have been attempted before \cite{montgomery10} only for ground state for a confinement
region of $r_c=0.5-3.5$ a.u. Present plots significantly extend the radius of sphere, and also cover low, high excited states,
corroborating the previous findings for ground state. In both panels, neighboring plots are parallel and remain well
separated. Generally, at low $r_c$, energies assume high values, falling off sharply with an increase in $r_c$ to approach
the isotropic FHO results and finally becomes constant after attaining those. This is in keeping with the fact that energy
of a confining system possessing spherical symmetry is a decreasing monotonic function of confining radius and as $r_c$ is
increased energy levels smoothly converge to the corresponding free system energy levels \cite{stevanovic08a}.

At this stage, we discuss the correlation in energy between 3D isotropic CHO and its unconfined counterpart FHO. It is well
known \cite{cohen92} that the 3D isotropic FHO energy levels, given by $E_{k,\ell}=(k+\ell+\frac{3}{2})=(m+\frac{3}{2})$ a.u.,
are degenerate. Here $k$ is zero or \emph{even} positive integer, $\ell$ is zero or
\emph{any} positive integer, so that $m$ can have \emph{all} integral values, zero or positive. Thus $\ell,m$ quantum numbers
have same parity. Interestingly, when the 3D isotropic FHO is confined inside a spherical box, not only this characteristic
degeneracy removed, but also the equal energy separation between adjacent
levels of 3D FHO disappears \cite{aquino97, stevanovic08}. In left panel (a) of Figure 2, is shown the degeneracy
breaking of three lowest degenerate levels of isotropic 3D FHO in presence of confinement, \emph{viz.,} $(1d, 2s)$, $(1f, 2p)$,
$(1g,2d,3s)$ having degeneracies of 2, 2, 3 respectively. For smaller values of $r_c$, the spectrum is clearly non-degenerate;
as the former gradually increased, energy differences become smaller and finally at sufficiently high $r_c$, the levels merge,
making them degenerate. However, in all these three instances, the three degenerate levels remain well separated and do not mix
with each other. In middle panel (b) is given the degeneracy breaking of two $(1h,2f,3p)$, $(1i,2g,3d,3s)$ levels of FHO
(both having degeneracy of 3) under the influence of confinement. In this case, one notices moderate mixing of $1i$
and $3p$ states. Such mixings also happen between $1h$ and $3s$ states (not shown). Finally, in right panel (c) such crossings
are shown between the first penta-degenerate $(1l,2j,3h,4f,5p)$ and hexa-degenerate $(1m,2k,3i,4g,5d,6s)$ levels respectively of the
FHO. It has been pointed out that, when energy levels are functions of radius of confinement, it may so happen that, for some
particular values of $r_c$, energies of two 3D CHO states coincide. This has been termed as \emph{accidental degeneracy} in the
sense it is defined in \cite{elliott79, stevanovic08a}. The above mixing characteristics are manifestations of such intersections
which happens for $(1h, 3s)$, $(1i, 3p)$, $(1j, 4s)$, $(1j, 3d)$, $(1j, 2g)$ pairs. The second one can be seen from (b), while in
(c) several such cases appear. Clearly one encounters many complex splitting of energy levels for high $n,\ell$ quantum numbers
as the box radius is decreased. In all these plots, as in Figure 1, energies in low-$r_c$ region is omitted for ease of
appreciation.

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table3}Selected expectation values (in a.u.) of some low-lying states of 3D isotropic CHO at
various $r_c$ values. Numbers in the parentheses denote literature results.}
\begin{ruledtabular}
\begin{tabular}{lllcccc}
$r_c$  & $n$   &  $\ell$ & $\langle r^{-2} \rangle $ &  $\langle r^{-1} \rangle $  &  $\langle r \rangle $ &  $\langle r^2 \rangle $   \\
\hline
0.5    &   0    &  0   &  35.669782840   &  4.8770025194               &  0.24993143144        &  0.07063332532        \\
       &        &      &  (35.670362626\footnotemark[1])               & (4.8770025195\footnotemark[2])
                       &  (0.24993143143\footnotemark[2])              &  (0.07063332531\footnotemark[1])       \\
       &   1    &  0   &  75.007610219(75.00992708\footnotemark[1]) &  6.2285137551 &  0.25002044046
                       & 0.08017671929(0.08017667193\footnotemark[1])        \\
       &   0    &  1   & 15.604579050(15.604579051\footnotemark[1]     & 3.7023250014          & 0.29578935362
                       & 0.09362593573(0.09362593572\footnotemark[1])        \\
       &   1    &  1   & 28.8493991749(28.8493991689\footnotemark[1])  & 4.6995657221          & 0.26969402489
                       & 0.08682928611(0.08682928612\footnotemark[1])          \\
1.0    &   0    &  0   & 9.0239897183(9.0241006941\footnotemark[1])    & 2.4512273473          & 0.49781081198
                       & 0.28044919195(0.2804491919\footnotemark[1])           \\
       &   1    &  0   & 18.773367559(18.773803815\footnotemark[1])    & 3.1127583237          & 0.50064924778
                       & 0.32128003811(0.3212800381\footnotemark[1])            \\
       &   0    &  1   & 3.9247112833(3.9247112835\footnotemark[1])    & 1.8561980355          & 0.59025087969
                       & 0.37296446428(0.3729644642\footnotemark[1])            \\
       &   1    &  1   & 7.2212001400(7.2212001399\footnotemark[1])    & 2.3501690242          & 0.53961515964
                       & 0.34762136892(0.3476213689\footnotemark[1])            \\
\end{tabular}
\end{ruledtabular}
\begin{tabbing}
$^{\mathrm{a}}$Ref.~\cite{aquino97}. \hspace{60pt}  \=
$^{\mathrm{b}}$Ref.~\cite{montgomery10}.
\end{tabbing}
\end{table}
\endgroup

Energy orderings in 3D isotropic CHO states in the limit of $r_c \rightarrow \infty$ is found to be,
\begin{multline}
 1s,1p,(1d,2s),(1f,2p),(1g,2d,3s),(1h,2f,3p),(1i,2g,3d,4s),(1j,2h, 3f,4p), \\  \nonumber
 (1k,2i,3g,4d,5s),(1l,2j,3h,4f,5p),(1m,2k,3i,4g,5d,6s), \cdots \nonumber
\end{multline}
For convenience, the degenerate states are grouped in parentheses.
Such orderings up to $4s$ were noticed in the variational calculation of \cite{aquino97} and up to $1j$ in \cite{stevanovic08a}
from the zeros of Bessel functions. Our calculation reproduces these two previous works and present an extended ordering
of levels. In the limit of $r_c \rightarrow 0$, the same changes to,
\[ 1s,1p,1d,2s,1f,2p,1g,2d,1h,3s,2f,1i,3p,1j,2g,3d,4s,1k,2h,3f,1l,4p,2i, \cdots \]

\begin{figure}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{rad_n0_l01234_0.5.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{rad_n012_l0_0.5.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{rad_00_0.5_1_1.5_2_3.eps}
\end{minipage}
\caption{Radial distribution functions (a.u.) of 3D isotropic CHO: (a) $n=0; l=0-4$ states for $r_c=0.5$; (b) $l=0; n=0-2$
states for $r_c=0.5$; (c) ground state for $r_c=0.5,1.0,1.5,2.0,3.0$.}
\end{figure}

\noindent
In this case also, the relative ordering of first 13 states given in \cite{aquino97} and 17 states considered in
\cite{stevanovic08a} are the same as found here, although we have covered some higher states.

As a further proof of the usefulness of present work, Table III reports four position expectation values, \emph{viz.},
$\langle r^{-2} \rangle$, $\langle r^{-1} \rangle$, $\langle r \rangle$, $\langle r^2 \rangle$ of 3D isotropic CHO
under the spherical confinement. Two lowest $n$ states (0 and 1) corresponding to two lowest $\ell$ values of 0 and 1 are
given for two $r_c$ (0.5, 1). The first and last expectation values for all the states were earlier reported quite accurately
in \cite{aquino97}.
Our results show very good agreement with these reference values, which is apparently better for latter than the former.
The other two expectation values, $\langle r^{-1} \rangle$, $\langle r \rangle$ are available only for ground state having an
$r_c=0.5$. Once again, GPS values are in excellent agreement with the literature values. No reference results could be found
for these two expectation values for remaining 7 states.

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table4} Lowest six eigenvalues (in a.u.) of 3D confined isotropic quartic oscillator at selected
$r_c$ values. Ground-state energy of the free oscillator is 1.8998365149 a.u. \cite{taseli97}.}
\begin{ruledtabular}
\begin{tabular}{l|llllll}
$r_c$  & E$_{0,0}$ & E$_{0,1}$       &  E$_{0,2}$     &  E$_{1,0}$      &   E$_{0,3}$     &  E$_{1,1}$   \\
\hline
0.1   &  493.48022579  &  1009.5364365   &  1660.8731068   &  1973.9208888   &  2441.5596954   &  2983.9758067  \\
0.3   &  54.831597579  &  112.17141900   &  184.54236135   &  219.32525354   &  271.28548566   &  331.55364336  \\
0.5   &  19.742773482  &  40.386895144   &  66.441916477   &  78.962323706   &  97.670693709   &  119.36502732  \\
0.8   &  7.7339639376  &  15.809618718   &  25.996944579   &  30.878482788   &  38.203785113   &  46.663916029  \\
1.0   &  4.9915845102  &  10.182113375   &  16.720373986   &  19.827020261   &  24.548286154   &  29.935709434  \\
1.3   &  3.0794268551  &  6.2185008173   &  10.143870741   &  11.930708685   &  14.823708103   &  17.930956677  \\
1.5   &  2.4678149050  &  4.9124620930   &  7.9342161030   &  9.2167903356   &  11.511774354   &  13.748897606  \\
2.0   &  1.9412531888  &  3.6821177561   &  5.7125440986   &  6.2917841210   &  8.0174364761   &  8.9903956010  \\
2.5   &  1.9002398159  &  3.5559309679   &  5.4265578434   &  5.8330487239   &  7.4754923256   &  8.0492393137  \\
3.0   &  1.8998367875  &  3.5542235225   &  5.4212247115   &  5.8223857288   &  7.4617247879   &  8.0163868627  \\
5.0   &  1.8998365150  &  3.5542220840   &  5.4212190000   &  5.8223727555   &  7.4617057604   &  8.0163311984  \\
\end{tabular}
\end{ruledtabular}
\end{table}
\endgroup

Now, Fig.~3 depicts some sample radial density distribution functions in case of isotropic bounded HO. In left panel (a),
we show such plots for 5 lowest $n=0$ states having $l$ values 0--4 confined in a box of radius $r_c=0.5$. As $l$ increases,
the peak height increases, shifts to the right side and tends to become more compact. The middle panel (b) displays
density plots for 3 lowest states (having $n =0-2$) corresponding to $l=0$ for same fixed $r_c$ as in (a). With an increase
in $n$, one notices an increase in the number of nodes, whereas the maxima in density peaks remain practically unchanged.
Finally (c) shows density changes in ground state of 3D CHO for five values of box radii, \emph{viz.}, 0.5,
1.0, 1.5, 2.0 and 3.0 covering a decent range of confinement. With increase in $r_c$, density peaks reduce to smaller
values and tend to spread, eventually assuming the shape of that of an FHO for sufficiently large $r_c$. Number of
nodes of a state remains same for all values of $r_c$.

Next we consider confinement in case of an isotropic 3D quartic harmonic oscillator. Six lowest eigenstates of this
system are tabulated in Table IV for various box radii $r_c$. Here too a broad range of $r_c$ is considered.
To the best of our knowledge, such confinement studies have not been presented before. However, some eigenstates in free system
have been reported in \cite{taseli97}, where extremely accurate energies were obtained by expanding the wave function in a
Fourier-Bessel series. Our ground-state energy of 1.8998365150 a.u. at last $r_c$ is in very good agreement with
their estimated value of 1.89988365149 a.u. Note that in this case, the critical boundary parameter $L_{cr}$, according to
\cite{taseli97} is 4.75. This is defined as the value of the boundary length for which $\mathrm{E(L_{cr})- E(L_{cr}+\delta)}$
remains below a certain predefined small value (they fixed at $10^{-30}$), for all values of $\delta > 0$. The energy
orderings (both unconfined and confined) in this case also follow same sequence as found for 3D isotropic harmonic oscillator
(this is confirmed for all the states given for harmonic oscillator). Of course, in the free quartic oscillator case, the
degeneracies now disappear.

Now, Fig. 4 displays the above energy variations of 3D quartic isotropic oscillator with respect to changes in box radius.
As in Fig.~1, here also, first ten $l=0$ states corresponding to $n=0-9$ are shown in left panel (a), whereas the right panel (b)
considers first
ten $n=0$ states with angular quantum number 0--9. The $r_c$ axis is kept fixed in both cases, while energy axis differs.
Very small confinements are again omitted for easy appreciation of the plots. Qualitatively speaking the general trend remains
very similar to those in Fig. 1 for 3D CHO. Adjacent curves remain well-separated and parallel in both occasions. Energies tend
to fall off sharply with an increase in $r_c$ at the beginning; then becomes stationary after reaching the value of that of
the respective 3D unconfined oscillator. One finds that, free unconfined oscillator energies are attained
for relatively smaller values of $r_c$ in this case, compared to the same in CHO. Such plots are given here for first time.

Next we shift our focus on confinement studies in 3D polynomial potentials of higher degree, namely $2K$, with $K=3-10$. At first,
however, Table V provides six eigenstates of respective free oscillators corresponding to $n,\ell$ quantum numbers
(0,5) and (0,5,10) respectively, i.e., (0,0), (0,5), (0,10), (5,0), (5,5), (5,10) states. In this case, literature data is
rather scanty; we could find only a lone reference of \cite{taseli97}. The authors reported first five of above states of
anharmonic oscillators having $K=3,4,10$. In all occasions, GPS results are identical to reference energies except for
lowest state, where they differ from each other by only $2 \times 10^{-10}$ a.u. This clearly demonstrates the validity
and efficiency of current approach.

\begin{figure}
\begin{minipage}[c]{0.40\textwidth}
\centering
\includegraphics[scale=0.45]{3dqtho_l0_n0123456789.eps}
\end{minipage
\hspace{0.5in}
\begin{minipage}[c]{0.40\textwidth}
\centering
\includegraphics[scale=0.45]{3dqtho_n0_l0123456789.eps}
\end{minipage
\caption{Energy changes of 3D confined quartic HO potential for (a) $l=0; n=0-9$ and (b) $n=0; l=0-9$ levels
respectively, as function of confinement radius $r_c$, in a.u.}
\end{figure}

Finally, we present results of spherical confinement in some high, even-order isotropic 3D anharmonic oscillators. Ground
states of six such polynomial oscillators having $2K=6,8,10,12,16$ and 20 are offered in Table VI, varying the box radius from
small to larger values. We are not aware of any such confinement studies before; hence no reference values could be quoted for
direct comparison. However, the lowest states of free anharmonic oscillators having $2K$ values 6,8 and 20 were estimated
earlier \cite{taseli97}. Our GPS energies in these three occasions show very good agreement with these reference values. For
lower $r_c$, energies seem to change rather slowly with increase in $2K$. The estimated values of critical boundaries
$L_{cr}=3.6, 2.9$ and 1.72 in these three states \cite{taseli97}, decrease with the power and are well supported by energies given
in this table. Considering the performance of our present approach in the context of various confinement situations discussed
earlier, we are confident that these results of higher order polynomials would also be equally accurate and reliable. Although
we have not ventured into estimating the $L_{cr}$, in general, however, the present calculation seems to corroborate the results
of \cite{taseli97}.

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table5}Some low- and high-lying eigenvalues (in a.u.) of unconfined 3D polynomial potentials of even
degree (2K). Literature values in parentheses are quoted from \cite{taseli97}.}
\begin{ruledtabular}
\begin{tabular}{lllllll}
$K$  &  E$_{0,0}$    &   E$_{0,5}$     &   E$_{0,10}$     &  E$_{5,0}$      &   E$_{5,5}$     &   E$_{5,10}$   \\
\hline
3  &  2.1692993559   &  15.859640450   &  36.010035895    &  44.196187884   &  74.182455900   &  107.23827462  \\
   & (2.1692993557)  & (15.859640450)  & (36.010035895)   & (44.196187884)  & (74.182455900)  &                \\
4  &  2.3779372071   &  18.693357492   &  44.256045884    &  57.560400554   &  99.689155552   &  147.06867947  \\
   & (2.3779372069)  & (18.693357492)  & (44.256045884)   & (57.560400554)  & (99.689155552)  &                \\
5  &  2.5489382648   &  20.856314303   &  50.629764312    &  68.606297125   &  121.31727693   &  181.41445326  \\
6  &  2.6934707830   &  22.574874381   &  55.691777381    &  77.756594924   &  139.54557480   &  210.69341741  \\
7  &  2.8180925155   &  23.984159530   &  59.816772453    &  85.407643316   &  154.97516807   &  235.68085749  \\
8  &  2.9271124526   &  25.168625012   &  63.253598497    &  91.876672206   &  168.13894256   &  257.12973408  \\
9  &  3.0235635760   &  26.183608461   &  66.170973123    &  97.407233060   &  179.46908706   &  275.67781244  \\
10 &  3.1096802645   &  27.066934477   &  68.686384500    &  102.18488145   &  189.30659360   &  291.84162253  \\
   & (3.1096802643)  & (27.066934477)  & (68.686384500)   & (102.18488145)  & (189.30659360)  &                \\
\end{tabular}
\end{ruledtabular}
\end{table}
\endgroup

These above features of previous table are well reflected in Fig. 5, where energies of three low-lying states, namely, (0,0),
(0,1) and (1,0), of 3D spherically confined isotropic anharmonic oscillators of even orders $2,4,6, \cdots, 20$ are plotted
against the radius of confinement. Energy ranges are different in three plots while $r_c$ axis remains same in (b), (c). From
very close values at smaller $r_c$, individual energies decrease sharply and then assumes the constant value of corresponding
unconfined potential, for critical values of the
boundary parameter $L_{cr}$. As evident, in all these three occasions, $L_{cr}$ decrease as $2K$ increase.

\begingroup
\squeezetable
\begin{table}
\caption {\label{tab:table6} Ground-state energies (in a.u.) of some higher degree ($2K=6,8,10,12,16,20$) 3D polynomial oscillators
enclosed within a spherical box of radius $r_c$ a.u.}
\begin{ruledtabular}
\begin{tabular}{lllllll}
$r_c$  &     $K=3\footnotemark[1]$     &        $K=4\footnotemark[1]$    &       $K=5$     &      $K=6$
       &       $K=8$     &        $K=10\footnotemark[1]$    \\
\hline
0.1   &  493.48022012  &  493.48022009   &  493.48022009   &  493.48022009   &  493.48022009   &  493.48022009    \\
0.3   &  54.831156039  &  54.831136597   &  54.831135622   &  54.831135569   &  54.831135565   &  54.831135565    \\
0.5   &  19.739647612  &  19.739270202   &  19.739218199   &  19.739210339   &  19.739208850   &  19.739208805    \\
0.8   &  7.7179857725  &  7.7132646295   &  7.7116613437   &  7.7110607571   &  7.7107156751   &  7.7106485219    \\
1.0   &  4.9627782237  &  4.9504713676   &  4.9443993675   &  4.9410809804   &  4.9378971947   &  4.9365423998    \\
1.5   &  2.4843022335  &  2.5349157915   &  2.6136557597   &  2.7133768531   &  2.9275486225   &  3.1096805499    \\
2.0   &  2.1713945253  &  2.3779504727   &  2.5489382668   &  2.6934707830   &  2.9271124526   &  3.1096802645    \\
2.5   &  2.1692993821  &  2.3779372071   &  2.5489382648   &  2.6934707830   &  2.9271124526   &  3.1096802645    \\
3.0   &  2.1692993559  &  2.3779372071   &  2.5489382648   &  2.6934707830   &  2.9271124526   &  3.1096802645    \\
4.0   &  2.1692993559  &  2.3779372071   &  2.5489382648   &  2.6934707830   &  2.9271124526   &  3.1096802645    \\
\end{tabular}
\end{ruledtabular}
\begin{tabbing}
$^{\mathrm{a}}$ Energies at $r_c \rightarrow \infty$ for $K=3,4,10$ respectively are: 2.1692993558, 2.3779372070 and
3.1096802643 a.u. \cite{taseli97}.
\end{tabbing}
\end{table}
\endgroup

\section{conclusion}
A detailed analysis has been made to understand confinement in the family of 3D anharmonic oscillators of even order enclosed
within spherically impenetrable walls. Energies, expectation values, radial densities are obtained by means of GPS method.
For isotropic 3D CHO, these quantities show excellent agreement with the best reference results available in literature,
covering \emph{small, intermediate and large} radius of confinement. It may be noted that, good-quality results in confined
systems are obtainable by a number of attractive and elegant methodologies for \emph{medium and large} $r_c$; however, same
for small $r_c$ is rather scarce. In this work, we are able to generate quite good results in both these regions with equal
ease and efficacy. Also, similar accuracy results are also offered in case of high-lying states. A thorough analysis of energy
changes with respect to confinement radius has been made. Energy ordering in case of 3D CHO and free oscillator, as well as
the degeneracy pattern is also discussed. Several interesting mixings have been pointed out. Next, we perform similar
investigation on 3D quartic oscillator. Finally we briefly touch upon the case of 3D isotropic even-order isotropic bounded
oscillators for higher orders up to as high as 20. Once again, low- and high-lying states in the confined system and free
oscillator are presented in some detail. Energy changes with variations in $r_c$ are monitored for selected low-lying states
in such oscillators. The method also delivers excellent quality results in case of unconfined oscillators. Comparison with
literature data reveals very good agreement in case of small as well as large box sizes. Confinement studies in other physical
and chemical situations such as the H atom or many-electron atoms may further consolidate the success of this approach, some of
which may be taken up in future works. Many new states are reported here for the first time. In summary, a simple, reliable
method is offered for accurate calculation of harmonic and other higher order polynomial oscillators under spherical confinement.

\begin{figure}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{e00.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{e01.eps}
\end{minipage}
\hspace{0.3in}
\begin{minipage}[c]{0.28\textwidth}
\centering
\includegraphics[scale=0.32]{e10.eps}
\end{minipage}
\caption{Energies in spherically confined isotropic 3D even-order anharmonic oscillators ($2K=2,3,4,\cdots,10$). Left, middle and
right panels (a), (b), (c) correspond to E$_{0,0}$, E$_{0,1}$ and E$_{1,0}$ states with respect to box radius $r_c$, respectively.
All quantities are in a.u. See text for details.}
\end{figure}


text:
\section{Introduction}
Throughout all graphs are assumed to be simple.  A \emph{triangle} in a graph $G$ is a subgraph of $G$ isomorphic to a complete graph on 3 vertices.  One of the first theorems in extremal graph theory is the following best possible result.

\begin{theorem}[Mantel \jm{\cite{Ma}}]\label{Ma}
If $G = (V,E)$ satisfies $|E| > \frac{1}{4}|V|^2$, then $G$ contains a triangle.
\end{theorem}

In this paper we are interested in graphs equipped with edge colourings.  We define a $k$-\emph{edge-coloured} graph to be a graph $G = (V,E)$ equipped with a disjoint union $E = \sqcup_{i=1}^k E_i$ called a \emph{colouring}.   Every subgraph $H \subseteq G$ we will view as a $k$-edge-coloured graph equipped with the colouring $E(H) = \sqcup_{i=1}^k \left(E_i \cap E(H)\right)$.  We say that $G$ is \emph{monochromatic} if there exists $1 \le i \le k$ so that $E = E_i$, and otherwise it is \emph{non-monochromatic}.  If $|E_i| \le 1$ holds for every $1 \le i \le k$ we call $G$ \emph{rainbow}.

One of the central problems in Ramsey Theory is to determine for every $k$ and $t$ the smallest integer $n$ so that every $k$-edge-coloured $K_n$ contains a complete subgraph of order $t$ which is monochromatic.  On the flip side, problems \jm{in} Anti-Ramsey Theory are concerned with conditions forcing the existence of rainbow subgraphs. \jm{See \cite{CFS} and \cite{FMO} for recent surveys of Ramsey Theory and Anti-Ramsey theory, respectively.} Here it is worth noting that Gallai has given a precise description of all possible edge-colourings of a complete graph that do not have a rainbow triangle.   Our problem is another variation on these themes.  Here we are focused on conditions on an arbitrary graph forcing the existence of a non-monochromatic triangle.  We prove the following \mdv{theorem and immediate corollary:}

\begin{theorem}
\label{main1}
If $G = (V,E)$ is a 2-edge-coloured graph with colouring $E = E_1 \sqcup E_2$, and
$|E| + \min\{ |E_1|, |E_2| \} > {|V| \choose 2}$, then $G$ contains a non-monochromatic triangle.
\end{theorem}

\mdv{\begin{corollary} \label{maincor} If $G = (V,E)$ is a 2-edge-coloured graph with colouring $E= E_1 \sqcup E_2$ and
$|E_1|, |E_2| > \frac{1}{3}{ |V| \choose 2}$, then $G$ contains a non-monochromatic triangle.
\end{corollary}}

\mdv{Theorem \ref{main1}} is tight in the sense that there exist graphs missing the bound by one edge for which there is no non-monochromatic triangle (i.e. all triangles are monochromatic).  We have characterized these graphs and we introduce them next.  For this discussion, we need to extend the usual notion of isomorphism to coloured graphs:  If $G=(V,E)$ and $G' = (V',E')$ are $k$-edge-coloured graphs relative to the colourings $E = \sqcup_{i=1}^k E_i$ and $E' = \sqcup_{i=1}^k E_i'$, then we say that $G$ and $G'$ are \emph{isomorphic} if there is an isomorphism from $G$ to $G'$ that maps every $E_i$ to some $E_j'$.

For every positive integer $m$, define the 2-edge-coloured graph $H_m$ as follows.  We let $V(H_m) = \sqcup_{i=0}^2 X_i$ where $|X_i| = m$ for $0 \le i \le 2$.  We add to $H_m$ all edges between $X_0$ and $X_1 \cup X_2$ and add a clique on $X_1$ and a clique on $X_2$.  We equip $H_m$ with a 2-edge-colouring by defining $E_i$ to be all edges incident with a vertex in $X_i$ for $i=1,2$.  We let $H_m^+$ be the 2-edge-coloured graph defined exactly as above with the exception that $|X_0| = m+1$ \jm{(see Figure \ref{HmPlus})}.  As we prove, the only cases where $|E| + \min\{ \am{|E_1|, |E_2|} \} = { |V| \choose 2}$ for which no non-monochromatic triangle exists are:
\begin{enumerate}
\item $G$ is a monochromatic complete graph.
\item $G$ is a 4-cycle and $E_i$ is a perfect matching for $i=1,2$
\item $G$ is isomorphic to either $H_m$ or $H_m^+$ for some $m \ge 1$.
\end{enumerate}

\begin{figure}
  \centering
  \includegraphics[width=280pt]{HmPlus}
  \caption{\jm{The graph $H_m^+$, with two colour classes indicated by the bold solid lines and bold dashed-dotted lines. Obtain $H_m$ from $H_m^+$ by deleting a vertex in $X_0$.}}
  \label{HmPlus}
\end{figure}

\mdv{Note that apart from monochromatic complete graphs, these examples satisfy $|E_1| = |E_2| = \frac{1}{3} {|V| \choose 2}$ showing that Corollary \ref{maincor} is also tight. }

We conjecture the following many colour variation\mdv{s} to Theorem \ref{main1} \mdv{and Corollary~\ref{maincor}:}

\am{\begin{conjecture}\label{cjt0}
If $G = (V,E)$ is a $k$-edge-coloured graph with colouring $E = \sqcup_{i=1}^k E_i$ and
$2|E|-\max\{|E_i|\,:\,1\leq i\leq k\}> \frac{1}{2} |V|^2$ then $G$ contains a non-monochromatic triangle.
\end{conjecture}}

\begin{conjecture}\label{cjt}
If $G = (V,E)$ is a $k$-edge-coloured graph with colouring $E = \sqcup_{i=1}^k E_i$ and
$|E_i| \mdv{>} \frac{1}{4k-2}|V|^2$ holds for $1 \le i \le k$, then $G$ contains a non-monochromatic triangle.
\end{conjecture}

If true, \mdv{these conjectures are} \mdv{essentially} \am{best possible} thanks to a generalization of the graph $H_m$.  For positive integers $k \ge 1$ and $m \ge 1$ define the $k$-edge-coloured graph $H_m^k$ as follows.  The vertex set of $H_m^k$ is the disjoint union of sets $X_0, \ldots, X_k$ where $|X_0| = (k-1)m$ and $|X_i| = m$ for $1 \le i \le m$.  Add to $H_m$ all edges between $X_0$ and $\cup_{i=1}^k X_i$ and add a clique on $X_i$ for $1 \le i \le k$.  Equip $H_m^k$ with a $k$-edge-colouring by defining $E_i$ to be all edges incident with a vertex of $X_i$ for $1 \le i \le k$.  Now \mdv{$H_m^k$ does not have a non-monochromatic triangle, but $|V(H_m^k)| = (2k-1)m$ and every $E_i$ satisfies
\[ |E_i| = \mbox{${m \choose 2}$} + (k-1)m^2 \approx (k - \tfrac{1}{2})m^2 = \tfrac{1}{4k-2} |V(H_m^k)|^2. \]
}

\begin{figure}
  \centering
  \includegraphics[width=190pt]{Hkm}
  \caption{\am{The graph $H_m^k$ with $k$ color clases. It indicates that Conjecture \ref{cjt0} is best possible.}}
  \label{Hkm}
\end{figure}

\mdv{
One might expect a stronger form Conjecture \ref{cjt0} to hold under the weaker assumption $2|E|-\max\{|E_i|\,:\,1\leq i\leq k\}> {|V| \choose 2}$ (indeed we originally did!).  However, Sophie Spirkl noted that a rainbow 4-cycle is a counterexample to this.   }

\section{The Proof}

For a graph $G=(V,E)$ we let $\alpha(G)$ denote the size of the largest independent set.  We define the \emph{density} of $G$ to be:
\[ d(G) = \frac{ |E| }{{ |V| \choose 2 }}. \]
We have introduced the concept of density in part because we find it easiest to think in these terms.  However, it is used somewhat sparingly in the proof because it is usually easier to write out our bounds in terms of edges.  The proof of our main theorem calls on the following straightforward lemma.

\begin{lemma}
\label{thelemma}
If $G$ is a graph with $|V(G)| \ge 2$ and density at least $\frac{2}{3}$, there is a \jm{component $G'$ of $G$ with $|V(G')|>\tfrac{2}{3}|V(G)|$}, and furthermore,
\[ \alpha(G') +1 \le 2 |V(G')| - |V(G)|. \]
\end{lemma}

\begin{proof}
Since $G$ must have a vertex with at least $\frac{2}{3}( |V(G)| - 1 )$ neighbours, it follows that there is a component $G'$ of $G$ containing at least $\frac{2}{3} |V(G)|$ vertices.  Define $a = \alpha(G')$, let $b = |V(G')| - a$ and  $c = |V(G)| - |V(G')|$, and note that $|V(G')| \ge \frac{2}{3} |V(G)|$ implies $a + b \ge 2c$.  Also note that $b > 0$ since otherwise the component $G'$ would be forced to be an isolated vertex.  Assume (for a contradiction) that $\alpha(G') \ge 2 |V(G')| - |V(G)| $, and note that this implies $c \ge b$.  Together with the bound $a + b \ge 2c$ we then have $a \ge c \ge b$.  But this gives the contradiction
\[ |E(G)| \le  \mbox{${b \choose 2}$} + \mbox{${c \choose 2}$} + ab  < \tfrac{2}{3} \Big( \mbox{${a \choose 2}$} +  \mbox{${b \choose 2}$} +  \mbox{${c \choose 2}$}   +  ab + ac + bc \Big) = \tfrac{2}{3} \mbox{${|V(G)| \choose 2}$}. \qedhere \]
\end{proof}

We need a little additional notation before proving the main result.  Let $G= (V,E)$ be a 2-edge-coloured graph with colouring $E = R \sqcup B$.  If $X \subseteq V$ we let $G[X]$ denote the 2-edge-coloured subgraph of $G$ induced by $X$.  We let $E(X)$ denote the set of edges with both ends in $X$, and define:
\[ e(X) = |E(X)| \qquad	e_B(X) = |E(X) \cap B| \qquad e_R(X) = |E(X) \cap R|.	\]
If $Y \subseteq V$ is disjoint from $X$, we let $E(X,Y)$ denote the set of edges with one end in $X$ and one end in $Y$.  Define:
\[ e(X,Y) = |E(X,Y)|	\qquad	e_B(X,Y) = |E(X,Y) \cap B|	\qquad	e_R(X,Y) = |E(X,Y) \cap R|. \]

Next we prove our main theorem, restated to allow for $|E| + \min\{ |R|, |B| \} \ge { |V| \choose 2 }$.

\begin{theorem}
\label{main2}
Let $G = (V,E)$ be a 2-edge-coloured graph with colouring $E = R \sqcup B$.  If
$|E| + \min\{ |R|, |B| \} \ge { |V| \choose 2 }$, then one of the following holds:
\begin{enumerate}
\item $G$ has a non-monochromatic triangle.
\item $G$ is a monochromatic clique.
\item $G$ is a 4-cycle and $R$, $B$ are perfect matchings.
\item $G$ is isomorphic to either \am{$H_m$ or $H_m^+$ for some $m \ge 1$}.
\end{enumerate}
\end{theorem}

\begin{proof}
Suppose (for a contradiction) that the theorem is false, and let \am{$G=(V,E)$} be a counterexample with \am{$|V|$} minimum.  Note that this implies $G$ is connected.  \mdv{We call edges in $R$ \emph{red} and edges in $B$ \emph{blue}, and for a vertex $v \in V$ an adjacent vertex is called a \emph{red} (\emph{blue}) neighbour if it is joined to $v$ by a red (blue) edge.}  We say that a subset $X \subseteq V$ with $|X| = 3$ is a \emph{seagull} if $X$ is the vertex set of a non-monochromatic two edge path $P$.  Note that since $G$ does not have a non-monochromatic triangle, the subgraph $P$ must be induced.  We say that a subset $\am{X} \subseteq V$ with $|\am{X}| = 4$ is an \emph{alternating square} if \am{$X$} is the vertex set of a properly coloured 4-cycle $C$ (i.e. every $x \in X$ is incident with one edge in $R \cap E(C)$ and one in $B \cap E(C)$).  Again in this case the subgraph $C$ must be induced.  We begin with a couple of straightforward claims about the behaviour of $G$.

\bigskip

\begin{claim}\label{d23}  $d(G) \ge \frac{2}{3}$ and if $d(G) = \frac{2}{3}$, then $|R| = |B|$.
\end{claim}

\begin{proofc}
This follows from $|E| + \tfrac{1}{2} |E| \ge |E| + \min\{ |R|, |B| \} \ge { |V| \choose 2}$.
\end{proofc}

\begin{claim}\label{seagull} If $\jm{X}$ is a seagull \am{in $G$} and $v \in V \setminus \jm{X}$, then $e(v, \jm{X} ) \le 2$
\end{claim}

\begin{proofc}
\jm{If $v$ has an edge to each of the three vertices in \jm{$X$} then, regardless of their colours, we get a non-monochromatic triangle.}
\end{proofc}

\begin{claim}\label{C4} $G$ does not have an alternating square
\end{claim}

\begin{proofc}
Suppose (for a contradiction) that $X \subseteq V$ is an alternating square.  Note that $X \neq V$ since in this case $G$ satisfies the third outcome of the theorem.  Define $Y = V \setminus X$ and note that by \am{Claim \ref{seagull}}, every $y \in Y$ must satisfy $e(y,X) \le 2$.  In particular, this implies
\begin{equation}\label{XY}
e(X,Y) \le \tfrac{1}{2} |X| |Y|.
\end{equation}
It follows from \am{(\ref{XY})} that
\begin{eqnarray}\label{YVR}
e(X) + e(X,Y) + \max\big\{&&\hspace*{-.4in} e_B(X) + e_B(X,Y), e_R(X) + e_R(X,Y) \big\}\nonumber\\
&\leq& \jm{4+ \tfrac{1}{2} |X| |Y| + (2+\tfrac{1}{2} |X| |Y|) = } \mbox{${ |X| \choose 2 }$} + |X| |Y|
\end{eqnarray}
\jm{We claim that $e(Y) + \min\{ e_R(Y), e_B(Y) \} \geq { |Y| \choose 2 }$. If not, then suppose, without loss of generality, that $e(Y) + e_R(Y) \am{<} { |Y| \choose 2 }$.}  \mdv{Equation (\ref{YVR}) implies that
$e(X) + e(X,Y) + e_R(X) + e_R(X,Y) \le { |X| \choose 2 } + |X| |Y|$.  Summing this and $e(Y) + e_R(Y) \am{<} { |Y| \choose 2 }$ give us $|E| + |R| < {|V| \choose 2}$ which contradicts our primary assumption.}
\jm{Hence $e(Y) + \min\{ e_R(Y), e_B(Y) \} \am{\geq} { |Y| \choose 2 }$, and by the minimality of $G$, the theorem holds for $G[Y]$.}
\am{Thus,} $G[Y]$ must be either a monochromatic clique, an alternating square, or $G[Y]$ is isomorphic to one of \am{$H_m$ or $H_m^+$ for some $m \ge 1$}.  In all but the first case, the density of $G[Y]$ is equal to $\frac{2}{3}$, \jm{and since the density of $G[X]$ is also $\tfrac{2}{3}$, inequality (\ref{XY}) implies that $d(G)<\tfrac{2}{3}$, contradicting Claim \ref{d23}.}  In the remaining case, $G[Y]$ is a clique and we may assume, \jm{without loss of generality, that} all edges of $G[Y]$ are in $R$.  Since $|E| + |B| \ge { |V| \choose 2 }$
it must be that $e(X,Y) = e_B(X,Y) = \frac{1}{2} |X| |Y|$ and every $y \in Y$ is incident with exactly two vertices in $X$.  If $|Y| \ge 3$, then there are two vertices in $Y$ with a common neighbour in $X$ and this triple forms a non-monochromatic triangle---a contradiction.  Otherwise, $1 \le |Y| \le 2$ and $e_R(X,Y) = 0$ give us a contradiction to the $|E| + |R| < { |V| \choose 2}$.
\end{proofc}

\begin{claim}\label{S1S2}
Let $S_1 , S_2$ be disjoint seagulls \am{in $G$. Let } $r = e_R(S_1,S_2)$ and $b = e_B(S_1,S_2)$, then
\begin{itemize}
\item $r + b \le 6$,
\item if $r+b = 6$ then $G[S_1 \cup S_2]$ is isomorphic to $H_2$, and
\item $r + b + \max \{ r, b \} \le 9$.
\end{itemize}
\end{claim}

\begin{proofc}
\jm{By Claim \ref{seagull}, there are at most 2 edges between a seagull and any other vertex, so in particular there are at most 6 edges between $S_1$ and $S_2$.} \am{If  $r+b = 6$ then each vertex in $S_1$  has exactly 2 neighbours in $S_2$.} \jm{Label the vertices of $S_1, S_2$ as $u, v, w$, $x, y, z$, respectively, with the edges $uv$ and $xy$ being in $R$, and the edges $vw$ and $yz$ being in $B$.} \am{Observe that  a blue  neighbor of $v$ cannot be a neighbor of $u$, and a red  neighbor of $v$  cannot be a neighbor of $w$. Hence, if each of  $u, v$ and $w$ has exactly 2 neighbours in $S_2$, it must be that $v$ has exactly one red neighbor  and one blue neighbor in $S_2$. Moreover, the red neighbour of $v$ in $S_2$ must be $x$ and the blue neighbour of $v$ in $S_2$ must be $z$ (otherwise, $v,x,y,z$ would induce alternating square contradicting Claim \ref{C4}).  This force  $G[S_1 \cup S_2]$ to be $H_2$ (see Figure \ref{TwoSeagulls3}). Note that the third instance of  the claim is satisfied in this case. It remains to prove the third instance of  the claim when $r+b\leq 5$. For that, it suffices to show that $\max\{r, b\} \le 4$. Suppose (for a contradiction, and without loss of generality) that $b=5$. Then, there are at least three $B$-edges between $\{u,v\}$ and $S_2$. Avoiding the existence of non-monochromatic triangles, the two possibilities for this to happen are depicted in Figure \ref{SeagullEdgeCases2}. In either case, we have created an alternating square,  a contradiction to Claim \ref{C4}.}
\end{proofc}

\begin{figure}
  \centering
  \includegraphics[width=350pt]{TwoSeagulls3_1}
  \caption{\jm{Forcing a copy of $H_2$ in the proof of Claim \ref{S1S2}. Here and elsewhere in the paper, solid bold lines indicate colour class $R$, and dashed-dotted bold lines indicate colour class $B$.}}
  \label{TwoSeagulls3}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=300pt]{SeagullEdgeCases2}
  \caption{\jm{The two  cases to consider in Claim \ref{S1S2} \am{when we assume that $b=5$}.}}
  \label{SeagullEdgeCases2}
\end{figure}

Choose a maximum size list of vertex disjoint seagulls $S_1, \ldots, S_m$ \am{in $G$} and define the sets $S = \cup_{i=1}^m S_i$ and $T = V \setminus S$. \jm{By Claim \ref{seagull}, each vertex in $T$ is adjacent to at most two of the three vertices in each seagull $S_i$.} \am{Hence,}

\begin{equation}\label{ST}
e(S,T) \le \tfrac{2}{3} |S| |T|.
\end{equation}

\begin{claim}\label{S} \jm{The set $S$ satisfies
\begin{equation}\label{Seq}
\tfrac{3}{2} e(S) \le e(S) + \max\big\{ e_R(S), e_B(S) \big\} \le \tbinom{|S|}{2}.
\end{equation}
Moreover, if \am{$e(S) =\frac{2}{3} { |S| \choose 2 }$}, then $G[S]$ is isomorphic to $H_m$.}
\end{claim}

\begin{proofc} \jm{Since $e(S) + \tfrac{1}{2} e(S) \leq e(S) + \max\big\{ e_R(S), e_B(S) \big\}$, the first inequality in (\ref{Seq}) is immediate.} \am{The second inequality in (\ref{Seq}) follows from the third instance of  Claim \ref{S1S2}, which states that} \jm{for any distinct $S_i, S_j$ we have
\begin{equation}\label{s1s2}
e(S_i, S_j) + \max\{e_R(S_i, S_j), e_B (S_i, S_j)\}\leq 9=|S_i|\cdot|S_j|,
\end{equation}
and from the fact that} \jm{for every $S_i$, $G[S_i]$ has exactly one edge in $R$ and one edge in $B$, and $2+1={3\choose 2}$.} \am{Finally, if $e(S) = \frac{2}{3}{ |S| \choose 2 }$ then $e(S_i,S_j)=6$ for any $i\neq j$. Thus, by the second instance of Claim \ref{S1S2}, $G[S_i \cup S_j]$ is isomorphic to $H_2$  for any distinct $S_i, S_j$. This gives $G[S]$ isomorphic to $H_m$.}
\end{proofc}

\am{For a given $x\in V$ we will use $N_B(x)$, and $N_R(x)$, to denote the set of blue neighbours of $x$, and the set of red neighbours of $x$, respectively.}

\begin{claim}\label{STvalues} \jm{$S\neq \emptyset$ and $|T|\geq 3$.}
\end{claim}

\begin{proofc} If $S = \emptyset$, then the assumption \am{that} $G$ is connected implies that one of $R$ \am{or} $B$ must be empty, and then the only way for $G$ to satisfy $|E| + \min\{|R|, |B| \} \ge { |V| \choose 2 }$ is for $G$ to be a monochromatic clique.  Therefore $m \ge 1$.

\am{Note that,  if $|T|\leq 2$ the only way for $G$ to satisfy Claim \ref{d23} is to have equalities in both (\ref{ST}) and (\ref{Seq}), that is
\begin{equation}\label{23}
e(S, T)=\tfrac{2}{3}|S||T| \mbox{ and } e(S)=\tfrac{2}{3}\tbinom{|S|}{2},
\end{equation}
and furthermore, if $|T|=2$, we must have $e(T)=1$. The second identity in (\ref{23})  implies that $G[S]$ is isomorphic to $H_m$ (by   Claim \ref{S}).  \mdv{So, we may write $V(G[S]) = X_0\sqcup X_1 \sqcup X_2$ as in Figure 1 where the edges incident with a vertex in $X_1$ are red and those incident with a vertex in $X_2$ are blue.}
\begin{itemize}
\item If $|T| = 0$ then $G=G[S]$ is isomorphic to $H_m$, a contradiction.
\item If $|T|=1$, say $T=\{v\}$. In this case we have $d(G)=\tfrac{2}{3}$, thus $|R|=|B|$ (by Claim \ref{d23}). Since $G[S]$ is isomorphic to $H_m$, and $e_R(H_m)=e_B(H_m)$ then we must have $e_R(v, S)=e_B(v, S)=m$. \mdv{First observe that $v$ cannot have a neighbour $x \in X_0$: If say $vx \in R$, then $N_B(v) \subset X_0 \setminus \{x\}$ is too small.  It follows from this and Claim \ref{C4} that $N_R(v)=X_1$ and $N_B(v)=X_2$, so $G$ is isomorphic to $H_m^+$, a contradiction.}
\item If $|T|=2$,  say $T=\{u,v\}$, and suppose without loss of generality that $uv\in R$. Since $G[S]$ is isomorphic to $H_m$, and $e_R(H_m)=e_B(H_m)$ then, in order  to satisfy $|E|+\min\{|R|, |B|\}\geq \tbinom{|V|}{2}$, it must be that $e_R(S,T)=e_B(S,T)=2m$. Thus,  there is a seagull $S_i$ with $e_B(T,S_i)\geq 2$. Recall that $e(u, S_i)=e(v, S_i)=2$. If $|N_B(x)\cap S_i|= 2$ for some $x\in\{u,v\}$ then there is at most one edge between $y$ and $S_i$, where $y\in \{u,v\}\setminus \{x\}$. Hence, $|N_B(x)\cap S_i|=|N_R(x)\cap S_i|= 1$ for both $x\in\{u,v\}$ which is impossible without creating either an alternating square or a non-monochromatic triangle.
\end{itemize}}
\end{proofc}

Now we have $S \neq \emptyset$ and $|T| \ge 3$ and we will show that this leads to a contradiction.  Note that the graph $G[T]$ must have all components monochromatic (by the maximality of our collection of seagulls).  It follows from \mdv{Claim \ref{d23}, Equation (\ref{ST}), and Claim \ref{S}} that $G[T]$ has density at least $\frac{2}{3}$.  \jm{Hence by Lemma \ref{thelemma}, $G[T]$ has a component $H$ with $|V(H)|>\tfrac{2}{3}|T|$.}  We shall assume (without loss) that $E(H) \subseteq R$.  Next we establish a key claim concerning blue edges between our seagulls and $V(H)$.

\begin{claim}\label{SH} For every $1 \le i \le m$ we have $e_B(S_i, V(H)) \le \alpha(H) + 1$.
\end{claim}

\begin{proofc}
To prove this claim, let $S_i = \{x,y,z\}$ be a seagull and assume that $xy \in R$ and $yz \in B$.
\am{Since} $G$ does not have an alternating cycle \am{(by Claim \ref{C4})} or a non-monochromatic triangle \am{(by assumption)} it follows that $N_B(x) \cap V(H)$ and $N_B(y) \cap V(H)$ are disjoint and moreover \am{$(N_B(x) \cup N_B(y)) \cap V(H)$} is independent (\jm{see the left image in Figure \ref{SeagullH2}}).  Similarly, $N_B(z) \cap V(H)$ is independent.  If $|(N_B(x) \cup N_B(y) ) \cap V(H)| \le 1$ the desired bound follows immediately, and we are similarly done if $|N_B(\mdv{z}) \cap V(H)| \le 1$.  So we may assume both of these sets have size at least two.  Choose $w \in N_B(z) \cap V(H)$ and (since $H$ is nontrivial) choose an edge $ww' \in E(H)$.  At most one of $w, w'$ can appear in $(N_B(x) \cup N_B(y) ) \cap V(H)$ since this set is independent.  Therefore, we may choose a vertex $u \in (N_B(x) \cup N_B(y) ) \cap V(H)$ with $u \neq w, w'$.  Now we have arrived at a contradiction as $\{z,w,w'\}$ and $\{x,y,u\}$ are both seagulls \jm{(see the right image in Figure \ref{SeagullH2})}.
\end{proofc}

\begin{figure}
  \centering
  \includegraphics[width=310pt]{SeagullH2}
  \caption{\jm{The situation under consideration in Claim \ref{SH}.}}
  \label{SeagullH2}
\end{figure}

\jm{In what follows, we use $|V(H)|=h$, $|T|=t$, and $|S|=s$.} For every seagull $S_i$, Claim 2 implies that $e(S_i,T) \le 2t$ and $e_B(S_i, T \setminus V(H)) \le e(S_i, T \setminus V(H)) \le 2(t-h)$.  Using these inequalities, together with Claim \ref{SH} and then Lemma \ref{thelemma}, we have
\begin{align}
e(S_i, T) + e_B(S_i,T)
	&=	e(S_i, T) + e_B(S_i, V(H)) + e_B(S_i, T \setminus V(H) )	\nonumber \\
	&\le	2t + \alpha(H) + 1 + 2(t-h)	\label{pre3t}
\\
	&\le	3t. \label{3t}
\end{align}
Summing this over all of our seagulls gives us $e(S,T) + e_B(S,T) \le st$.  Claim \ref{S} implies that $e(S) + e_B(S) \le { s \choose 2 }$.  Combining these with the assumption $|E| + |B| \ge { |V| \choose 2 }$ we deduce that
\begin{equation}
\label{Tdensity}
e(T) + e_B(T) \ge \mbox{${ t \choose 2}$}.
\end{equation}
\jm{Since $e(V(H), T\setminus V(H))=0$, we know that  $\tbinom{t}{2}-e(T) \geq h(t-h)$, and hence (\ref{Tdensity}) says that $e_B(T)\geq h(t-h)$. On the other hand, if $h\neq t$, then the fact that $h\geq t-h$ (by Lemma \ref{thelemma}) implies that $e_B(T)\leq \tbinom{t-h}{2} <(t-h)^2\leq h(t-h)$.} Therefore, we must have $V(H) = T$ and $e_B(T) = 0$.  Now the only way for inequality (\ref{Tdensity}) to hold is for $H$ to be a clique; \jm{in particular this means $\alpha(H)=1$}. Since $t \ge 3$ \jm{(by Claim \ref{STvalues}) we can return to (\ref{pre3t}) and improve upon (\ref{3t})}:
\[ e(S_i, T) + e_B(S_i, T) \le 2t + 2 < 3t. \]
\jm{Summing over all of our seagulls gives us $e(S,T) + e_B(S,T) < st$}.  Combining this with the bound $e(S) + e_B(S) \le {|S| \choose 2}$ (from  \jm{Claim (\ref{S})}) gives us the contradiction
$$|E| + |B| = e(S) + e_B(S) + e(S,T) + e_B(S,T) + \tbinom{t}{2} < \tbinom{ |V|}{2 }$$
and this completes the proof.
\end{proof}

\jm{\bibliographystyle{amsplain}

redpajama_set_name: RedPajamaArXiv