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: K1,1,1,1,n,
K1,2,2,n,
K1,1,1,2,n, and
K1,4,n.
He also proved that the crossing number of
K4,n on the torus and the Klein bottle
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 K4,n.
Manuscript. 2006.
Pak Tung Ho. The crossing number of K4,n on the real projective plane. Discrete Mathematics 304(1-3): 23-33 (2005)

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 ≥ n1+epsilon edges, there
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)/n3→4/27,as n tends to infinity.
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))n3.
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