Please clarify how entropy increases when matter gravitationally coalesces On John Baez's website, http://math.ucr.edu/home/baez/entropy.html, he discusses the problem of how entropy increases when a cloud of ideal gas collapses gravitationally (no black holes - keeping it simple).  But he doesn't give away the answer - instead he implies that, I presume, either gravitons or photons are released during collapse and these increase the overall system entropy.
Can someone please answer which it is, gravitons or photons?  If gravitons (or gravity waves), then does this mean that pre-20th century physicists, with no notion of gravity waves, would have concluded that gravitational attraction violates the 2nd law?  And if photons, then what about if the gas particles were totally neutral - wouldn't they not emit any EM radiation in that case?  Or am I wrong that gravitons or photons are the answer? Thanks!
 A: The answer would be actually much simpler if the collapse produced a black hole. It can be easily shown to have entropy vastly exceeding the entropy of any gas of the same mass.
Concerning your main question, the answer is, of course, that any system with many degrees of freedom - both in classical physics as well as quantum physics - always satisfies the second law of thermodynamics. The second law may always be proved - quite generally. The proofs are the proofs of the H-theorem or its generalization for any physical system you consider.
Just think about the "balls" in the phase space - any phase space - how it gets deformed via the time evolution. The "smoothened" version of this evolved "spaghetti" has a higher volume whose logarithm represents the entropy increase.
If you didn't allow the molecules to emit photons when they collide, they wouldn't ever shrink spontaneously by obeying the laws of gravity. The probability that a molecule slows down (or gets closer) under the gravitational influence of the other molecules would be equal to the probability that it speeds up (or gets further) - in average. If you introduce some objects and terms in the Hamiltonian that allow inelastic collisions, these inelastic collisions will selectively slow down the molecules that happened to be closer to each other, which is the mechanism that will be reducing the average distance between the molecules (the actual rate will depend on the gravitational attraction, too).
I wrote photons because, obviously, the probability of the emission of a photon is much higher for real-world gases because most of their interactions are electromagnetic interactions. Because a photon carries as much entropy as a graviton would, but you produce many more photons by random collisions, the entropy increase is stored in the photons. The entropy carried by gravitons is smaller by dozens of orders of magnitude.
A: The situation Baez describes is of a virialized ball of gas shrinking gravitationally. As he points out (and further emphasizes in his hint), this process doesn't conserve energy. Once you know where the energy is going, you've got the answer to what's happening with the entropy.
Your guesses about what's carrying off the energy (photons and gravitons) are both good ones, and in some contexts "photons" is the answer. (I know of no astrophysical context in which gravitons are responsible for a significant fraction of the energy loss.) In other astrophysical contexts the answer is actually something else: it's just gas particles "evaporating off." The way a cloud of gas often shrinks is that some particles acquire speeds greater than escape velocity and fly off, leaving behind less-energetic particles. A small fraction of the particles may escape, but they carry off enough energy to cause the collapse, and enough entropy to satisfy the second law.
A: The result is generic to matter which is under greater pressure due to gravitational implosion.  The hydrostatic equilibrium of a star is the condition where the internal pressure of the material keeps the star in a static configuration against the inward push of gravity
$$
\frac{dP}{dr}~=~-\frac{GM\rho}{r^2},
$$
for $P$ the pressure and $\rho$ the density of matter.  We may think of an adiabatic situation where a small variation in the stellar radius occurs, where the star shrinks inwards from $R$ to $R~-~\Delta R$.  The density of a unit of material is then $\rho~=~3m/(4\pi r^3)$, which we sum up to $M$.  We consider the equation of state as the natural gas law $PV~=~NkT$.  So the change in the pressure is
$$
\Delta P~=~\int_P^{P+\Delta P}dP~=~\int_R^{R~-~\Delta R}\frac{3GM^2}{4\pi r^5}dr
$$
$$
=~-\frac{15GM^2}{4\pi r^4}\Big|_R^{R~-~\Delta R}~=~-\frac{15GM^2}{4\pi}\Big(\frac{1}{(R~-~\Delta R)^4}~-~\frac{1}{R^4}\Big)~\simeq~\frac{15GM^2}{\pi R^4}\frac{\Delta R}{R}
$$
This means the change in the pressure is positive, as we might expect, and the change in the temperature within a unit volume in the star is similarly positive $\Delta T~=~\frac{V}{Nk}\Delta P$.  Then the entropy is $\Delta S~=~c\Delta T/T$.
So we expect the star to increase its luminosity, and the hydrostatic equation of Eddington was derived to compute that.  This applies up to the point the implosion increases the gravity field enough to red shift light.  The delay coordinate
$$
r^*~=~r~+~2GM log\Big(\frac{r~-~2GM}{2GM}\Big)
$$
maybe used to compute the red shift.  General relativity then predicts a dimming of the star as it collapses.
A: Thermodynamically, only materials which are totally transparent to electromagnetic radiation will fail to emit photons when heated. The stellar clouds are hardly transparent, especially when dense enough.
A: The entropy of a collapsing gas cloud is calculated in detail at http://rickbradford.co.uk/AppendixB1_EntropyofCollapsingGasCloud.pdf . The main result is 

...we find the change in the total entropy of the gas plus the radiation
  for a change in gas volume of dV to be zero

$$
dS_{total} = dS_{gas} + dS_{rad} = 0
$$

Thus, the overall change in entropy is zero, consistent with the
  second law of thermodynamics in the limiting case of a reversible
  change. Q.E.D. [Aside: This implies that we could return to the
  original gas volume and temperature by applying radiant heat from
  outside]

So because the release of electromagnetic radiation during the collapse doesn't increase the entropy, but only balances out the apparent decrease of entropy in the remaining gas, the increase of entropy during gravitational collapse must happen by gravitational radiation.
