New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of K<Subscript>n</Subscript>

We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the plane in general position. We show that for the number of (≤ k)-edges is at least

Distinct Distances in Homogeneous Sets in Euclidean Space

It is shown that every homogeneous set of n points in d-dimensional Euclidean space determines at least distinct distances for a constant c(d) > 0. In three-space the above general bound is slightly improved and it is shown that every homogeneous set of n points determines at least distinct distances.     

Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

Projective surfaces with many skew lines

We give an example of a smooth surface of degree that contains pairwise disjoint lines. In particular, our example shows that the degree in Miyaoka's bound is sharp.

     

A note on the isoperimetric inequality

We show that the sharp integral form on the isoperimetric inequality holds for those orientation-preserving mappings whose Jacobians obey the rule of integration by parts.

     

Stabbing Delaunay Tetrahedralizations

A Delaunay tetrahedralization of $n$ vertices is exhibited for which a straight line can pass through the interiors of $\Theta(n^2)$ tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than $O(n)$ tetrahedra. The construction generalizes to higher dimensions: in $d$ dimensions, a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$ Delaunay $d$-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a $d$-dimensional $n$-vertex polytope can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets. This last result was first demonstrated by Amenta and Ziegler, but the construction given here is simpler and more intuitive.     

Telescoping, rational-valued series, and zeta functions

We give an effective procedure for determining whether or not a series telescopes when is a rational function with complex coefficients. We give new examples of series , where is a rational function with integer coefficients, that add up to a rational number. Generalizations of the Euler phi function and the Riemann zeta function are involved. We give an effective procedure for determining which numbers of the form are rational. This procedure is conditional on 3 conjectures, which are shown to be equivalent to conjectures involving the linear independence over the rationals of certain sets of real numbers. For example, one of the conjectures is shown to be equivalent to the well-known conjecture that the set is linearly independent, where is the Riemann zeta function.

Some series of the form , where is a quotient of symmetric polynomials, are shown to be telescoping, as is . Quantum versions of these examples are also given.

     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Power integral bases in a parametric family of totally real cyclic quintics

We consider the totally real cyclic quintic fields , generated by a root of the polynomial

Assuming that is square free, we compute explicitly an integral basis and a set of fundamental units of and prove that has a power integral basis only for . For (both values presenting the same field) all generators of power integral bases are computed.

     

Upward Three-Dimensional Grid Drawings of Graphs

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every -vertex graph with bounded degeneracy has a three-dimensional grid drawing with volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the -direction. We prove that every dag has an upward three-dimensional grid drawing with volume, which is tight for the complete dag. The previous best upper bound was . Our main result concerning upward drawings is that every -colourable dag ( constant) has an upward three-dimensional grid drawing with volume. This result matches the bound in the undirected case, and improves the best known bound from for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.Research of Vida Dujmovi is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Remarks on summability of series formed of deviation probabilities of sums of independent identically distributed random variables

We make some remarks leading to a refinement of the recent work of Klesov (1993) on the connection between the convergence of the series $\Sigma _{n = 1}^\infty \tau _n P(|S_n | \ge \varepsilon n^\alpha )$ for every ε > 0 and the convergence of $\Sigma _{n = 1}^\infty n\tau _n P(|X_1 | \ge \varepsilon n^\alpha )$ again for every ε > 0.     

Relaxation and convexity of functionals with pointwise nonlocality

It is shown that the relaxation of the integral functional involving argument deviations

in weak topology of a Lebesgue space (where and are standard measure spaces, the latter with nonatomic measure), coincides with its convexification whenever the matrix of measurable functions : satisfies the special condition, called unifiability, which can be regarded as collective nonergodicity or commensurability property, and is automatically satisfied only if . If, however, either 1$"> or 1$">, then it is shown that as opposed to the classical case without argument deviations, for nonunifiable function matrix one can always construct an integrand so that the functional itself is already weakly lower semicontinuous but not convex.

     

A note on “Reducing the number of binary variables in cutting stock problems”

This study proposes a deterministic model to solve the two-dimensional cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with $m$ stocks and $n$ cutting rectangles requires $2n^{2}+n(m+1)$ binary variables in the traditional model. In contrast, the proposed model uses $n^{2}+n\lceil {\log _2 m}\rceil $ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.     

Point Counting in Families of Hyperelliptic Curves

Let E _Γ be a family of hyperelliptic curves defined by , where is defined over a small finite field of odd characteristic. Then with in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is and it needs bits of memory. A slight adaptation requires only space, but costs time . An implementation of this last result turns out to be quite efficient for n big enough. H. Hubrechts is a Research Assistant of the Research Foundation–Flanders (FWO–Vlaanderen).     

The expected norm of random polynomials

The results of this paper concern the expected norm of random polynomials on the boundary of the unit disc (equivalently of random trigonometric polynomials on the interval ). Specifically, for a random polynomial

let

Assume the random variables , are independent and identically distributed, have mean 0, variance equal to 1 and, if 2$">, a finite moment . Then

and

as .

In particular if the polynomials in question have coefficients in the set (a much studied class of polynomials), then we can compute the expected norms of the polynomials and their derivatives

and

This complements results of Fielding in the case, Newman and Byrnes in the case, and Littlewood et al. in the case.

     

Improved bounds on equilibria solutions in the network design game

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most \(H_n\), the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most \(H_n \left( 1-\frac{1}{\Theta (n^4)} \right) \), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most \(H_{n/2} + \varepsilon \) for any \(\varepsilon \) starting from some suitable \(n \ge n(\varepsilon )\).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of \(\frac{4}{3}\) and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of \(\frac{4}{3}\), and provide an upper bound of \(\frac{26}{19}\). To the end, we conjecture and argue that the right answer is \(\frac{4}{3}\).     

Partitions into Primes

We investigate the asymptotic behavior of the partition function defined by , where denotes the von Mangoldt function. Improving a result of Richmond, we show that , where is a positive constant and denotes the times iterated logarithm. We also show that the error term can be improved to if and only if the Riemann Hypothesis holds.

     

An asymptotic bound for the complexity of monotone graph properties

We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ¼n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ½n(n?1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ?n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ?n(n−1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) .     

Volume Formulas in Lp-Spaces

We extend classical volume formulas for ellipsoids and zonoids to p-sums of segments $${vol}\left( {\sum\limits_{i=1}^m { \oplus_p } [ -x_i ,x_i ]} \right)^{1/n} \sim_{c_p} n^{ - \frac{1}{{p'}}} \left( {\sum\limits_{card(I) = n} {|\det (x_i)_i |^p}} \right)^{\frac{1}{{pn}}}$$ where x1,...,xm are m vectors in $\mathbb{R}^n ,\frac{1}{p} + \frac{1}{{p\prime }} = 1$ . According to the definition of Firey, the Minkowski p-sum of segments is given by $$\sum\limits_{i = 1}^m { \oplus _p [ - x_{i,} x_i ]} = \left\{ {\sum\limits_{i = 1}^m {\alpha _i } x_i \left| {\left( {\sum\limits_{i = 1}^m {|\alpha _i |^{p^\prime } } } \right)} \right.^{\frac{1}{{p^\prime }}} \leqslant 1} \right\}.$$ We describe related geometric properties of the Lewis maps associated to classical operator norms.     

How often are two permutations comparable?

Two permutations of are comparable in the Bruhat order if one is closer, in a natural way, to the identity permutation, , than the other. We show that the number of comparable pairs is of order at most, and at least. For the related weak order, the corresponding bounds are and , where . In light of numerical experiments, we conjecture that for each order the upper bound is qualitatively close to the actual number of comparable pairs.