Wikipedia:Reference desk/Archives/Mathematics/2015 February 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 1

"For all vertices... but at most $\gamma n$ of them"

I am trying to decipher this:

Let $d(x)$ denote the degree of $x$ in $H$, and $d(x,y)$ the number of edges of $H$ containing both $x$ and $y$. Write $\pm \delta$ to mean a quantity between $-\delta$ and $\delta$.

For every integer $r\geq 2$ and reals $k\geq 1$ and $a>0$, there are $\gamma =\gamma (r,k,a)>0$ and $d_{0}=d_{0}(r,k,a)$ such that for every $n\geq D\geq d_{0}$ the following holds:

Every $r$-uniform hypergraph $H=(V,E)$ on a set $V$ of $n$ vertices in which all vertices have positive degrees and which satisfies the following conditions:

1. For all vertices $x\in V$ but at most $\gamma n$ of them, $d(x)=(1\pm \gamma )D$.
2. For all $x\in V$, $d(x)<kD$.
3. For any two distinct $x,y\in V$, $d(x,y)<\gamma D$.

contains a cover of at most $(1+a)(n/r)$ edges.

Specifically, I don't understand the first condition. "For all vertices" and "for at most $\gamma n$ vertices" seem like they contradict each other to me. --superioridad ^(discusión) 05:51, 1 February 2015 (UTC)

It is likely to mean "for all except at most γn of them". YohanN7 (talk) 09:54, 1 February 2015 (UTC)

Oh, as in "all but at most γn vertices". That makes complete sense, thank you.

Resolved

--superioridad ^(discusión) 10:47, 1 February 2015 (UTC)

Fitting cylinders inside a tube

How many cylinders with an external diameter of 34.2 mm can fit inside a cylinder with an internal diameter of 153.6 mm (no overlap allowed)? Roger (Dodger67) (talk) 19:31, 1 February 2015 (UTC)

At least 16, like so (the circles would actually touch each other, but I'm limited in what I can display here):

   O
  O O
 O O O
O O O O
 O O O
  O O
   O

Or maybe 20, like so:

    O
   O O
  O O O
 O O O O
O O O O
 O O O
  O O
   O

Or even 26, like so:

  O O
 O O O
O O O O
 O O O O
O O O O
 O O O O
  O O O
   O O

But I suggest you use MS Paint or some other simple drawing program to try to place them in different arrangements, to see if you can pack more in. StuRat (talk) 19:47, 1 February 2015 (UTC)

FWIW, the relevant articles are circle packing and Packing problem#Packing circles. -- ToE 20:19, 1 February 2015 (UTC)

And Circle packing in a circle. -- ToE 17:09, 2 February 2015 (UTC)

Packing problem#External links points to The best known packings of equal circles in a circle (complete up to N = 2600) which gives densities which should help bound your answer. If you are able to pack n circles of diameter 34.2 inside a circle of diameter 153.6, you will have achieved a density of (34.2²/153.6²) n ≈ 0.0496 n, so your [Stu's] lowest guess of 16 would give a density of 0.793, while the optimal [best known] density for 16 circles is only 0.751. Likewise, fitting 15 would give you a density of 0.744, greater than the optimal [best known] density of 0.734. But you should be able to fit 14 because that gives you a density of only 0.694, far less than the optimal [best known] density of 0.747. So the answer is 14. (And they should rattle a bit.) -- ToE 21:10, 1 February 2015 (UTC)

Something seems wrong there, as the 16 circles in a diamond arrangement shown should be at most 4 small circle diameters across at any point, and 4×34.2 < 153.6. StuRat (talk) 21:18, 1 February 2015 (UTC)

How can four circles in a row touch going across horizontally and leave room in the middle for four in a column to touch going down vertically? -- ToE 21:24, 1 February 2015 (UTC)

Looks like I miscalculated by using the wrong type of symmetry for hexagonal packing. Specifically, I was thinking that a 90 degree rotation would produce the same 4 touching circles vertically, just like the 4 circles touching horizontally, but a hexagonal packing arrangement only allows for rotations in multiplies of 60 degrees, which excludes 90 degrees. StuRat (talk) 21:30, 1 February 2015 (UTC)

Yeah, hexagonal packing is optimal for the plane, giving a density of π/(2√3) ≈ 0.907. This density is surpassed when packing circles for n = 1 (with a density of unity), but I'm fairly sure (though I don't know how to prove it) that the optimal density for packing a circle will alway be less than this for n > 1, but will approach this value for large n. -- ToE 22:05, 1 February 2015 (UTC)

Note that the optimal solution is only exactly known for n≤13 and n=19, so if you do figure out a way to fit 15 you should write a paper on it. -- ToE 21:16, 1 February 2015 (UTC)

The site cited by ToE gives the ratio of the big radius to the small radius for each packing shown, which you want to be no more than 4.491. The best known packing of 14 has ratio 4.328, and the best known for 15 has ratio 4.521; so your answer is 14, so far as is now known. —Tamfang (talk) 21:44, 1 February 2015 (UTC)

And I just noticed that the site even has a calculator which answers this sort of question with both numbers and a drawing, thanks to Eckard Specht at the Otto-von-Guericke University Magdeburg. (I wonder what the relation is to the German physicist Eckehard Specht at the same institution.) -- ToE 21:52, 1 February 2015 (UTC)

I find it amazing that so little is known with certainty. Makes me wonder if there is a grid computing project for finding better packings. -- Meni Rosenfeld (talk) 14:39, 2 February 2015 (UTC)

Good question. Two things I wonder are: A) Is there an easy proof that the density of packing n > 1 circles in a circle is always less than the hexagonal packing density in a plane? I though it seemed obvious at first, but I don't know where to start with a proof. B) For those n for which a proof is not know for the optimal density, but for which a strong lower bound is known for the density by way of a known (and perhaps conjectured optimal) packing (such as those listed in the external site), what techniques can be used to determine an upper bound for the density? My remark about Dodger67 publishing a paper if he manages to fit in a 15th cylinder was tongue-in-cheek, but I don't know how to find out if there is an upper bound on the density for n = 15 which, while being above the achieved 0.734, is below his required 0.744, in which case 15 cylinders are known to be impossible for the particular dimensions of his cylinders. -- ToE 17:09, 2 February 2015 (UTC)

One arrangement of 14, BTW, is like so:

  O O
 O O O
O O O O
 O O O
  O O

That's my original 16, but without the top and bottom circles. StuRat (talk) 21:59, 1 February 2015 (UTC)