[math-fun] Two questions in geometric combinatorics
(I don't know whether either of these problems has been solved. Here are the 3D versions of what could asked of any dimension.) 1. Analogous to a recent question posed here about triangles: Let A_n denote a regular tetrahedral arrangement of points in 3-space, n to an edge. (The layers successively contain 1, 3, 6,... points.) Define a "tetrad" to be any four mutually adjacent points of A_n. QUESTION: For which n is it possible to partition A_n into disjoint tetrads ??? Call such an n "tetrizable". Clearly, any such n = 0 (mod 4). It's not hard to show that the number of points #(A_n) is divisible by 4 exactly when n = 0,2,4,6, or 7 (mod 8). QUESTION: More concretely, n = 2 is the first tetrizable number. What is the next one (if any) ??? --------------------------------------------------------------- 2. Given any arrangement of congruent spheres in 3-space where any two are either disjoint or tangent, consider the graph formed by using each sphere as a node and each tangency as an edge. Call such a graph a "packing graph". QUESTION: What is the maximum chromatic number of a packing graph (if the maximum exists) ??? ------------------------------------------------------------- --Dan Asimov -- NOTE: Please direct any responses to <asimov@msri.org>, since I may not keep this AOL e-address much longer -- thanks.
Correction: The statement beginning with ***** is obviously in error. (What was I thinking?) The correct statement now follows the wrong one. ---------------------------------------------------------------------------- ------------------------------ (I don't know whether either of these problems has been solved. Here are the 3D versions of what could asked of any dimension.) 1. Analogous to a recent question posed here about triangles: Let A_n denote a regular tetrahedral arrangement of points in 3-space, n to an edge. (The layers successively contain 1, 3, 6,... points.) Define a "tetrad" to be any four mutually adjacent points of A_n. QUESTION: For which n is it possible to partition A_n into disjoint tetrads ??? Call such an n "tetrizable". *****(WRONG:) Clearly, any such n = 0 (mod 4). Clearly, any such n implies that the size of A_n is divisible by 4. It's not hard to show that #(A_n) is divisible by 4 exactly when n = 0,2,4,6, or 7 (mod 8). QUESTION: More concretely, n = 2 is the first tetrizable number. What is the next one (if any) ??? --------------------------------------------------------------- 2. Given any arrangement of congruent spheres in 3-space where any two are either disjoint or tangent, consider the graph formed by letting each sphere define a node, and each tangency an edge. Call such a graph a "packing graph". QUESTION: What is the maximum chromatic number of a packing graph (if the maximum exists) ??? ------------------------------------------------------------- --Dan Asimov
On Fri, Jan 30, 2004 at 05:17:01PM -0500, asimovd@aol.com wrote:
Let A_n denote a regular tetrahedral arrangement of points in 3-space, n to an edge. (The layers successively contain 1, 3, 6,... points.)
Can you be more explicit what this arrangement is? I am completely baffled. Peace, Dylan
Hi, Dylan. I hope all's well with you, not having chatted with you for many a moon! Your math-fun posting "Re: Two questions ..." arrived just as it appears below, with no letter body. (I don't know if the problem is at my end or yours, but I am very curious what you were trying to say. (My mail software says it stripped your message of an attachment; perhaps this caused the problem.) Best regards, Dan ----- Original Message ----- From: "Dylan Thurston" <dpt@lotus.bostoncoop.net> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Sunday, February 01, 2004 1:03 PM Subject: Re: [math-fun] Two questions in geometric combinatorics
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
At 05:17 PM 1/30/04, asimovd@aol.com wrote:
Let A_n denote a regular tetrahedral arrangement of points in 3-space, n to an edge. (The layers successively contain 1, 3, 6,... points.) Define a "tetrad" to be any four mutually adjacent points of A_n.
QUESTION: For which n is it possible to partition A_n into disjoint tetrads ???
Call such an n "tetrizable". Clearly, any such n = 0 (mod 4).
You mean #(A_n) = 0 (mod 4).
It's not hard to show that the number of points #(A_n) is divisible by 4 exactly when n = 0,2,4,6, or 7 (mod 8).
QUESTION: More concretely, n = 2 is the first tetrizable number. What is the next one (if any) ???
Every even n is tetrizable, every odd n is not. Given a partition for some even n - 2, you can obtain one for n by partitioning the two added layers in a fairly obvious way, illustrated here for n = 6: 1 / \ 1 1---1 7---7 2 7 3 \ / / \ / \ 2 7 3 2---2 3---3 8---8 9---9 4 8 5 9 6 \ / \ / / \ / \ / \ 4 8 5 9 6 4---4 5---5 6---6 On the other hand, examining a drawing that I can't reproduce here makes it clear that any point on an edge of the big tetrahedron can only be in a tetrad that contains another point on the same edge. (In fact, the four adjacent points not on the edge form a square.) This pairing means that the number of points on the edge must be even. -- Fred W. Helenius <fredh@ix.netcom.com>
participants (4)
-
asimovd＠aol.com -
Daniel Asimov -
dpt＠lotus.bostoncoop.net -
Fred W. Helenius