Computing the face lattice of a polytope from its vertex-facet incidences

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(min{n,m}··), where n is the number of vertices, m is the number of facets, is the number of vertex-facet incidences, and  is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191–198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·²) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d··). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

Error-correcting nonadaptive group testing with d-disjunct matrices

d-disjunct matrices constitute a basis for nonadaptive group testing (NGT) algorithms and binary d-superimposed codes. The rows of a d-disjunct matrix represent the tests in a NGT algorithm which identifies up to d defects in a population. The columns of a d-disjunct matrix represent binary d-superimposable codewords. A d-disjunct matrix μ is called d^e-disjunct if given any d + 1 columns of μ with one designated, there are e + 1 rows with a 1 in the designated column and a 0 in each of the other d columns. d^e-disjunct matrices form a basis for e error-correcting NGT algorithms. In this paper, we construct d^e-disjunct matrices. In so doing, we simultaneously construct e error-correcting binary d-superimposed codes. The results of this paper can be used to construct pooling designs for the screening recombinant DNA libraries. Such screenings are a major component of the Human Genome Project.     

The smallest degree sum that yields potentially kCℓ-graphic sequences

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(_kC_ℓ,n) such that each n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(_kC_ℓ,n) has a realization G containing a cycle of length r for each r, krℓ.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

The relation of the d-orthogonal polynomials to the Appell polynomials

We are dealing with the concept of d-dimensional orthogonal (abbreviated d-orthogonal) polynomials, that is to say polynomials verifying one standard recurrence relation of order d + 1. Among the d-orthogonal polynomials one singles out the natural generalizations of certain classical orthogonal polynomials. In particular, we are concerned, in the present paper, with the solution of the following problem (P): Find all polynomial sequences which are at the same time Appell polynomials and d-orthogonal. The resulting polynomials are a natural extension of the Hermite polynomials.

A sequence of these polynomials is obtained. All the elements of its (d + 1)-order recurrence are explicitly determined. A generating function, a (d + 1)-order differential equation satisfied by each polynomial and a characterization of this sequence through a vectorial functional equation are also given. Among such polynomials one singles out the d-symmetrical ones (Definition 1.7) which are the d-orthogonal polynomials analogous to the Hermite classical ones. When d = 1 (ordinary orthogonality), we meet again the classical orthogonal polynomials of Hermite.     

Unconditional uniqueness of solution for $$\dot H^{s_c }$$ critical 4th order NLS in high dimensions

In this paper, we study the unconditional uniqueness of solution for the Cauchy problem of Ḣ^s_c(0 ≤ s_c < 2) critical nonlinear fourth-order Schrödinger equations i∂_tu + Δ²u-εu=λ|u|^αu. By employing paraproduct estimates and Strichartz estimates, we prove that unconditional uniqueness of solution holds in C_t(I; Ḣ^s_c(R^d)) for d ≥ 11 and min{1^-, (8)/(d-4)} ≥ α >(-(d-4)+√4(d-4)²+64)/4.     

On weights in duadic abelian codes

In this note, we prove that if C is a duadic binary abelian code with splitting μ=μ₋₁ and the minimum odd weight of C satisfies d²−d+1≠n, then d(d−1)n+11. We show by an example that this bound is sharp. A series of open problems on this subject are proposed.     

The Second Neighbourhood for Quasi-transitive Oriented Graphs

In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.     

Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance

In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l_∞-distance are considered. An O(2^d−1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d²·n + d²·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.     

Characterization of Laborde-Mulder graphs (extended odd graphs)

The identification of diametrical vertices in the d-dimensional hypercube (d 3) leads to a (0, 2)-graph of degree d on 2^d−1 vertices and of diameter d/2 namely the extended odd graph (or Laborde-Mulder graph) for odd values of d, and the half-cube for even values of d. In this paper we prove that the diameter of a (0, 2)-graph of degree d on 2^d−1 vertices is at least d/2 , and when d is odd the equality holds if and only if the graph is a Laborde-Mulder graph.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

On some integrals arising in mathematical physics

This paper presents in the first section the exact evaluation of three single integrals relating to the dielectric behavior of two-dimensional electron plasmas. In the second section we present a procedure for reducing 3d-dimensional integrals of the form: ∫∫∫dqdpdkD(q)(p+k+q)ƒ(p)[1−ƒ(p+q)]ƒ(k)[1−ƒ(k+q)], where the vectors lie in d-dimensional space and ƒ denotes the Fermi function, to tractable form. The second-order exchange integral for a d-dimensional electron gas is taken as an example and is evaluated in closed form as a function of d.     

On the number of flats spanned by a set of points in PG(d, q)

It is shown that for fixed 1 r s < d and > 0, if X PG(d, q) contains (1 + )q^s points, then the number of r-flats spanned by X is at least c()q^{(r+1)(s+1−r)}, i.e. a positive fraction of the number of r-flats in PG(s + 1,q).     

Approximate range searching

The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and >0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance w of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/)^d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/)^d−1) time. We also present a lower bound for approximate range searching based on partition trees of Ω(logn+(1/)^d−1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.     

The problem of minimax mean square filtration in parabolic systems : PMM vol. 42, no. 6, 1978, pp, 1016–1025

The problem of estimating parameters of state of a distributed parabolic system by observation results is considered. The system is assumed to function under conditions of undefined perturbations in the measurement channel and specified initial distribution. The problem is considered in minimax formulation [1] in conformity with the scheme accepted for ordinary differential equations [2].(^*), Analytic definition of sets X (/gJ, y (·)) (/gJ > 0) of states of a parabolic system compatible at instant /gJ with the realizable signal y (t) (t ε [0, /gJ]) is obtained. An element of region X (/gJ, y (·)) which satisfies the specified minimax criterion is chosen as the optimal estimate of the true state at instant /gJ. Integradifferential equations in partial derivatives are derived for parameters that define the evolution of regions X (/gJ, y (·)) in time. One of the methods of approximating the input problem of observation by similar problems for systems of ordinary differential equations is discussed on a specific example. Problems of observation for distributed systems in different formulations appear in [3 – 6].     

Notes on D-optimal designs

The purpose of this paper is to exhibit new infinite families of D-optimal (0, 1)-matrices. We show that Hadamard designs lead to D-optimal matrices of size (j, mj) and (j − 1, mj), for certain integers j ≡ 3 (mod 4) and all positive integers m. For j a power of a prime and j ≡ 1 (mod 4), supplementary difference sets lead to D-optimal matrices of size (j, 2mj) and (j − 1, 2mj), for all positive integers m. We also show that for a given j and d sufficiently large, about half of the entries in each column of a D-optimal matrix are ones. This leads to a new relationship between D-optimality for (0, 1)-matrices and for (±1)-matrices. Known results about D-optimal (±1)-matrices are then used to obtain new D-optimal (0, 1)-matrices.     

Convolution integral equations with Gegenbauer function kernel

In this paper we develop a concise and transparent approach for solving Mellin convolution equations where the convolutor is the product of an algebraic function and a Gegenbauer function. Our method is primarily based on

1. the use of fractional integral/differential operators;

2. a formula for Gegenbauer functions which is a fractional extension of the Rodrigues formula for Gegenbauer polynomials (see Theorem 3);

3. an intertwining relation concerning fractional integral/differential operators (see Theorem 1), which in the integer case reads (d/dx)²ⁿ⁺¹ = (x⁻¹ d/dx)ⁿx²ⁿ⁺¹(x⁻¹ d/dx)ⁿ⁺¹.

Thus we cover most of the known results on this type of integral equations and obtain considerable extensions. As a special illustration we present the Gegenbauer transform pair associated to the Radon transformation.     

Art galleries with guards of uniform range of vision

We are given an art gallery represented by a simple polygon with n sides and an angle (0°,360°]. How many guards of range of vision are required to monitor every point of the polygon in the worst case? After recent results on upper bounds of this problem, we prove new lower bounds for all 0°<<180°. Several lower bounds meet the best known upper bounds, and we expect our lower bounds to be best possible.

Surprisingly, it turns out that n/3 180°-guards are always enough to monitor a polygon of n sides, but if we wish to use (180−)°-guards for any >0, then possibly 2n/3−1 guards are necessary.