Proposed new problems

Section 1.9, Problem #10

Estimate the packing density of the regular tetrahedron in 3-dimensional space.

Beth Chen proved that this number is larger than .7786157. In particular, it exceeds the packing density of the ball, contradicting a conjecture of John Conway and Salvatore Torquato.

Bibliography: J. H. Conway and S. Torquato: Packing, tiling, and covering with tetrahedra, Nat. Acad. Sci. 103 (2006), 10612-10617.

http://www.pnas.org/cgi/reprint/0601389103v1.pdf

B. Chen: Dense packings of regular terahedra, manuscript, 2007.

Section 5.9, Problem #1

How many colors are needed to color the points in the plane so

that points at odd distances have different colors? Moshe Rosenfeld

mentioned a construction by HJML (Hayri, Jano, Moshe @ Laco) which

proves that at least 5 colors are needed.

Bibliography:

Section 7.2, Problem #1

Chvatal extended the notion of lines to arbitrary finite metric spaces (X,r) and conjectured that if no line consists of the entire ground set X, then there is an ordinary line passing through only two points. This generalization of the Sylvester-Gallai theorem was proved by Chen.

Chen and Chvatal asked: Is it true that every finite metric space (X,r)

where no line consists of the entire ground set X

determines at least |X| distinct lines?

Bibliography: V. Chvátal, Sylvester-Gallai theorem and metric betweenness. Discrete Comput. Geom. 31 (2004), no. 2, 175--195.

X. Chen and V. Chvátal.

Problems related to a de Bruijn-Erdos theorem.

http://arxiv.org/abs/math.CO/0610036.

X. Chen, The Sylvester-Chvátal theorem,

http://www.research.rutgers.edu/~chvatal/chen.pdf

and Discrete & Computational Geometry 35(2): 193-199 (2006)

Section 9.3, Problem #1

Determine the crossing numbers of complete multipartite graphs.

Pak Tung Ho computed the crossing numbers of the following graphs: K

K

K

K

He also proved that the crossing number of

K

is floor(n/4)*(2n-4(1+floor(n/4))).

Bibliography: Pak Tung Ho.

On the Crossing Number of Some Complete

Multipartite Graphs.

Manuscript. 2006.

Pak Tung Ho.

The Toroidal Crossing Number of K

Manuscript. 2006.

Pak Tung Ho. The crossing number of K

Section 9.3, Problem #9

Richter and Thomassen conjectured that there exists a constant c such that every graph of crossing number CR(G) has an edge

e such that CR(G-e) > CR(G) - c sqrt(CR(G)).

Richter and Thomassen proved the existence of an edge e such that CR(G-e) > (2/5)CR(G) - O(1).

Improving a result of Jacob Fox and Csaba D. Toth,

Jakub Cerny, Jan Kyncl, and Geza Toth showed that for any espilon

there exists delta such that for every graph G with n vertices (n

sufficiently large) and m ≥ n

is a subgraph G' of G of at most (1-delta)m edges and crossing

number at least (1-epsilon)CR(G).

Bibliography: R. B. Richter, C. Thomassen. Minimal graphs with crossing number at least k. J. Combin. Theory Ser. B 58 (1993), no. 2, 217--224.

Jacob Fox and Csaba D. Tóth.

On the decay of crossing numbers.

Proc. 14th Sympos. on Graph Drawing (Karlsruhe, 2006), vol. 4372 of LNCS, Springer-Verlag, pp. 174-183.

Also in: J. Combin. Theory Ser. B (2007), to appear.

Jakub Cerny, Jan Kyncl, and Geza Toth.

Improvement on the decay of crossing numbers. Manuscript.

Section 9.4, Problem #1

Is it true that there exists an absolute constant c>0 such that the odd-crossing number of any finite graph is at least c times its crossing number?

Pelsmajer, Schaefer, and Stefankovic proved that if such a c exists, it must be smaller than 0.937.

Bibliography: Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2006) Odd Crossing Number Is Not Crossing Number. In: LNCS 3843 (2006), 386-396. Healy, Patrick and Nikolov, Nikola S., Eds. Proceedings Graph Drawing, Limerick, Ireland. See: http://gdea.informatik.uni-koeln.de/archive/00000720/

Section 11.2, Problem #10

Let g(n,π/2) denote the smallest number of ordered triples induced by n points in general position in the plane that determine obtuse angles. Then f(n,π/2)/n

It was shown by Conway et al. that the limit exists and that it is at most 4/27.

The above conjecture would follow from Turan's following old conjecture: the maximum number of hyperedges of a 3-uniform hypergraph on n vertices, which does not contain a complete subhypergraph on four points is (5/54+o(1))n

Bibliography: J. H. Conway, H. T. Croft, P. Erdös, and M. J. T. Guy: On the distribution of values of angles determined by coplanar points. J. London Math. Soc. (2) 19 (1979), no. 1, 137--143.

Section 11.4, Problem #1

Leo Moser's worm problem is stated in the introduction. Sira Sriswasdi and Tirasan Khandhawit improved the best known lower bound for the area of the smallest convex region thaat contains all worms (continuous arcs) of unit length from

0.2194 to 0.227498.

Bibliography: Sira Sriswasdi and Tirasan Khandhawit.

An Improved Lower Bound for Moser?s Worm Problemm.

http://arxiv.org/pdf/math.MG/0701391