Bounding the volume of facet-empty lattice tetrahedra

Discrete Geometry 963 to be positive if C(i, j)≥0 for every pair (i, j) and C(i, j) is strictly positive for at least one such pair. We prove that the maximum number of ones in an n×n zero-one matrix containing no positive orthogonal cycle is O(n4/3). The order of magnitude of this bound cannot be improved. Our results lead to a new proof of the celebrated theorem of Spencer, Szemer´edi, and Trotter [5] stating that the number of times that the unit distance can occur among npoints in the plane is O(n4/3). This is the first proof that does not use any tool other than a forbidden pattern argument. We present another geometric application, where the forbidden pattern Pis the adjacency matrix of an acyclic graph. A hippodrome is a c×drectangle with two semicircles of diameter d attached to its sides of length d. Improving a result of Efrat and Sharir [2], we show that the number of “free” placements of a convex n-gon in general position in a hippodrome Hsuch that simultaneously three vertices of the polygon lie on the boundary of H, is O(n).This result is related to the Planar Segment-Center Problem. References [1] P. Braß, Gy. K´arolyi, and P. Valtr, A Tur´an-type extremal theory of convex geometric graphs, Discrete and Computational Geometry—The Goodman-Pollack Festschrift (B. Aronov et al., eds.), Springer-Verlag, Berlin, 2003, 277–302. [2] A. Efrat and M. Sharir, A near-linear algorithm for the planar segment center problem, Discrete Comput. Geom. 16 (1996), 239–257. [3] Z. F¨uredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Mathematics 103 (1992), 233–251. [4] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, Journal of Combinatorial Theory, Series A 107 (2004), 153–160. [5] J. Spencer, E. Szemer´edi, and W.T. Trotter, Unit distances in the Euclidean plane, in: Graph Theory and Combinatorics (B. Bollob´as, ed.), Academic Press, New York, 1984, 293–303. Bounding the volume of facet-empty lattice tetrahedra Julian Pfeifle (joint work with Han Duong, Christian Haase, Bruce Reznick) A lattice polytope is empty if it contains no lattice points except for its vertices. Already in 1957, Reeve [10] noticed that empty three-dimensional lattice simplices may have unbounded volume. In 1982, Zaks, Perles & Wills [12] constructed a family of d-dimensional lattice simplices, each member of which contains klattice points in total and has the rather large volume k+ 1 d!22d−1−1. In the following year, Hensley [4] proved that the volume of any d-dimensional lattice polytope containing k≥1 lattice points in its interior is bounded by a constant that depends only on dand k. By sharpening Hensley’s basic diophantine approximation lemma, Lagarias & Ziegler [6] in 1991 improved his bound and 964 Oberwolfach Report 17/2005 showed that the maximal volume V(d, k) of a d-dimensional lattice polytope with kinterior lattice points is bounded by V(d, k)≤k7(k+ 1)d2d+1 , which for d= 3 reads V(3, k)≤k7(k+ 1)48 . This bound was further sharpened by Pikhurko [8], who was able to prove an upper bound with only a linear dependence on k: V(d, k)≤(8d)d·15d·22d+1 ·k , V(3, k)≤243·15384 k . Afacet-empty or clean lattice polytope is a lattice polytope whose only lattice points on the boundary are its vertices. In our talk we focused on the special class of facet-empty k-point lattice tetrahedra, which contain exactly k+4 lattice points, kof them in the relative interior. It is known [10], [11] that via unimodular transformations any facet-empty lattice tetrahedron may be brought into the normal form Ta,b,n = conv (0,0,0),(1,0,0),(0,1,0),(a, b, n), where (a, b, n) = (0,0,1), or n≥2, 0 ≤a, b ≤n−1, and gcd(a, n) = gcd(b, n) = gcd(1 −a−b, n) = 1. Note that vol Ta,b,n =n. We sketched a proof of the following theorem, which significantly improves Pikhurko’s bound for this special family of 3-dimensional lattice polytopes: Theorem 1. The maximal (normalized) volume of a clean lattice tetrahedron ∆ with k≥1interior lattice points is vol ∆ ≤12k+ 8 . This bound is attained by the family of clean k-point lattice tetrahedra T3,6k+1,12k+8 :k≥1. The overall structure of the proof is as follows. We first show that the number k of interior lattice points of ∆ equals the number of times that the sum f(z) = (a+b−1)z n−az n−bz n equals 1, as ztakes on integer values between 1 and n. Next, we use that f(z)∈ {0,±1}and f(n−z) = −f(z) for 1 ≤z≤n−1 to express kas half the second moment of the sequence (f(z) : 1 ≤z≤n−1). This second moment is then expressed using Dedekind sums s(a, n): Proposition 2. Set c= 1 −a−bmod nand let aa′=bb′=cc′= 1 mod n. Then 1 2 n−1 X z=1 f(z)2=n−3 6+1 3n−s(c, n)−s(a, n)−s(b, n)+s(a′b, n)+s(a′c, n)+s(b′c, n). Discrete Geometry 965 Remark 3. After obtaining this expression, we realized that we should have expected the appearance of Dedekind sums in this expression, because they appear in a formula of Pommersheim [9] for the Ehrhart polynomial of lattice tetrahedra. In fact, our derivation of Proposition 2 yields an elementary proof of this formula in the case of facet-empty tetrahedra; in particular, we do not need to evaluate the Todd class of the associated toric variety. There are now at least two ways to complete the proof of the theorem. First, we can express each Dedekind sum s(a, n) as essentially the sum of digits of the negative-regular continued fraction expansion of n/(n−a); see [1], [5], [7], [9]. Proposition 4. Let n/(n−a) = b1−1/(b2−1/(···−1/br)) be the negative-regular continued fraction expansion of n/(n−a), where 0≤a < n are coprime and we require bi≥2for i= 1,2,...,r. Moreover, define a′∈ N by aa′= 1 mod nand 0≤a′< n. Then s(a, n) = 1 12 r X i=1 3−bi+a+a′ n−2!. We then use a detailed analysis of the behavior of digit sums of negative-regular continued fraction expansions to bound kfrom below. This approach requires a fairly substantial amount of case distinctions. The other way of proving the theorem is not by passing to continued fractions, but instead by bounding the individual Dedekind sums directly and controlling the interaction between the six summands in Proposition 2. This alternative proof of the theorem is still work in progress; we have reason to hope that it requires a substantially smaller number of case distinctions. It has been observed several times that s(a, n) changes drastically if ais close to numbers of the form n·c/d. The behaviour of Dedekind sums in the neighborhood of such values was studied by Girstmair [2], [3], who introduced the notion of “F- neighbors”. First, define a Farey point to be a real number of the form n·c/d, where dis “small”; more precisely, 1 ≤d≤√n, 0 ≤c≤dand gcd(c, d) = 1. (Note that this cis different from the one used before.) The denominator dis called the order of the Farey point. The F-neighbors of order dare all real numbers xsuch that 0 ≤x≤nand |x−n·c/d| ≤ √n/d2, for some 0 ≤c≤dwith gcd(c, n) = 1. An integer x∈[0, n] that is not an F-neighbor of order 1 ≤d≤√nis called an ordinary integer. Proposition 5. [3, Theorem 1 and Section 3] (a) If n≥15 and x∈[0, n]is an ordinary integer, then |s(x, n)| ≤ 1 4√n+5 12 . (b) Let xbe a F-neighbor of order d, let n·c/d be the corresponding F-point, and put q=xd −cn, so that |q| ≤ √n/d. Then s(x, n) = n 12dq +1 12 E(d+|q|+ 4) , where Edenotes an error term such that |E(z)| ≤ z. The next proposition is crucial for analyzing the sum from Proposition 2. 966 Oberwolfach Report 17/2005 Proposition 6. Let x= (cn +q)/d with gcd(c, d) = gcd(x, n) = 1 be a Farey neighbor of order dto cn/d. Then for any 0≤c′< q relatively prime to q, there exists a parametrization n=αs +βwith α, β ∈ Z and s∈ N such that the inverse x′of xmodulo nhas the form x′= (c′n+d)/q. In particular, inverting xleaves the product dq invariant. It turns out that we may assume all of the six first arguments {a, b, c, a′b, b′c, c′a} of the Dedekind sums in Proposition 2 to be F-neighbors. Moreover, by the estimates from Proposition 5 we only need to consider those 20 sets of arguments such that the associated values diqisatisfy P6 i=1 1/(diqi)>1. We leave the completion of this argument for further study. References [1] P. Barkan,Sur les sommes de Dedekind et les fractions continues finies, C. R. Acad. Sci. Paris S´er. A-B, 284 (1977), pp. A923–A926. [2] K. Girstmair,Dedekind sums with predictable signs, Acta Arith., 83 (1998), pp. 283–294. [3] , Zones of large and small values for Dedekind sums, Acta Arith., 109 (2003), pp. 299– 308. [4] D. Hensley,Lattice vertex polytopes with interior lattice points, Pacific J. Math., 105 (1983), pp. 183–191. [5] D. Hickerson,Continued fractions and density results for Dedekind sums, J. Reine Angew. Math., 290 (1977), pp. 113–116. [6] J. C. Lagarias and G. M. Ziegler,Bounds for lattice polytopes containing a fixed number of interior points in a sublattice, Canad. J. Math., 43 (1991), pp. 1022–1035. [7] G. Myerson,On semiregular finite continued fractions, Arch. Math. (Basel), 48 (1987), pp. 420–425. [8] O. Pikhurko,Lattice points in lattice polytopes, Mathematika, 48 (2003), pp. 15–24. [9] J. E. Pommersheim,Toric varieties, lattice points and Dedekind sums, Math. Ann., 295 (1993), pp. 1–24. [10] J. E. Reeve,On the volume of lattice polyhedra, Proc. London Math. Soc. (3), 7 (1957), pp. 378–395. [11] B. Reznick,A classification of 1-point lattice tetrahedra. preprint, 18 pages, 2004. [12] J. Zaks, M. A. Perles, and J. M. Wills,On lattice polytopes having interior lattice points, Elem. Math., 37 (1982), pp. 44–46. On Geometric Graphs with no Pair of Parallel Edges Rom Pinchasi Ageometric graph is a graph drawn in the plane with its vertices as points and its edges as straight line segments connecting corresponding points. A topological graph is defined similarly except that its edges are simple Jordan arcs connecting corresponding points. Two edges in a geometric graph are said to be parallel, if they are two opposite edges of a convex quadrilateral. In [2, 3] Katchalski, Last, and Valtr prove a conjecture of Kupits and obtain the following result: Theorem 1. A geometric graph on nvertices with no pair of parallel edges has at most 2n−2edges.