On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

Topological games and continuity of group operations

We consider a topological game GΠ involving two players α and β and show that, for a paratopological group, the absence of a winning strategy for player β implies the group is a topological one. We provide a large class of topological spaces X for which the absence of a winning strategy for player β is equivalent to the requirement that X is a Baire space. This allows to extend the class of paratopological or semitopological groups for which one can prove that they are, actually, topological groups.Conditions of the type “existence of a winning strategy for the player α” or “absence of a winning strategy for the player β” are frequently used in mathematics. Though convenient and satisfactory for theoretical considerations, such conditions do not reveal much about the internal structure of the topological space where they hold. We show that the existence of a winning strategy for any of the players in all games of Banach-Mazur type can be expressed in terms of “saturated sieves” of open sets.     

Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t=2, while it is NP-hard for any t⩾4; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t=3.     

Cores in random hypergraphs and Boolean formulas

We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of a k‐core in a random r‐uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r‐SAT, r ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

Ramsey Functions for Quasi-Progressions

 A quasi-progression of diameter n is a finite sequence for which there exists a positive integer L such that for . Let be the least positive integer such that every 2-coloring of will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for in terms of k and i that holds for all . Upper bounds are obtained for in all cases for which . In particular, we show that . Exact formulae are found for and . We include a table of computer-generated values of , and make several conjectures. Received: September 22, 1995 / Revised: February 28, 1997     

Das Anfangs-Randwertproblem eines dünnen Profils in kompressibler Unterschallströmung

Summary The initial boundary value problem of a thin profile in a compressible subsonic flow is investigated, being important for the gust problem. Existence and uniqueness of the solution are shown. By a generalizedWiener-Hopf-equation, the solution is reduced to the solution of a system of integro-differential equations for the downwashes in the profile plane. This system can be solved exactly by an iterative calculation of integrals for any value of timet>0. Finally, for smallt>0, the indicial-admittance function for vertical translation is found and is compared with a result given byLomax [6]. The asymptotic case for larget>0 will be investigated in a later paper.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

An upper bound for permanents of nonnegative matrices

A recent conjecture of Caputo, Carlen, Lieb, and Loss, and, independently, of the author, states that the maximum of the permanent of a matrix whose rows are unit vectors in lp is attained either for the identity matrix I or for a constant multiple of the all-1 matrix J.The conjecture is known to be true for p=1 (I) and for p?2 (J).We prove the conjecture for a subinterval of (1,2), and show the conjectured upper bound to be true within a subexponential factor (in the dimension) for all 1<p<2. In fact, for p bounded away from 1, the conjectured upper bound is true within a constant factor.     

Random change on a Lie group and mean glaucomatous projective shape change detection from stereo pair images

In this article we develop a nonparametric methodology for estimating the mean change for matched samples on a Lie group. We then notice that for k≥5, a manifold of projective shapes of k-ads in 3D has the structure of a 3k−15 dimensional Lie group that is equivariantly embedded in a Euclidean space, therefore testing for mean change amounts to a one sample test for extrinsic means on this Lie group. The Lie group technique leads to a large sample and a nonparametric bootstrap test for one population extrinsic mean on a projective shape space, as recently developed by Patrangenaru, Liu and Sughatadasa. On the other hand, in the absence of occlusions, the 3D projective shape of a spatial k-ad can be recovered from a stereo pair of images, thus allowing one to test for mean glaucomatous 3D projective shape change detection from standard stereo pair eye images.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

The Logical vs. the Ontological Understanding of Conditions

According to the truth-functional analysis of conditions, to be ‘necessary for’ and ‘sufficient for’ are converse relations. From this, it follows that to be ‘necessary and sufficient for’ is a symmetric relation, that is, that if P is a necessary and sufficient condition for Q, then Q is a necessary and sufficient condition for P. This view is contrary to common sense. In this paper, I point out that it is also contrary to a widely accepted ontological view of conditions, according to which if P is a necessary and sufficient condition for Q, then Q is in no sense a condition for P; it is a mere consequence of P.     

Efficient Recognition of Totally Nonnegative Matrix Cells

The space of m×p totally nonnegative real matrices has a stratification into totally nonnegative cells. The largest such cell is the space of totally positive matrices. There is a well-known criterion due to Gasca and Peña for testing a real matrix for total positivity. This criterion involves testing mp minors. In contrast, there is no known small set of minors for testing for total nonnegativity. In this paper, we show that for each of the totally nonnegative cells there is a test for membership which only involves mp minors, thus extending the Gasca and Peña result to all totally nonnegative cells.     

Infinite Matroidal Version of Hall's Matching Theorem

Hall's theorem for bipartite graphs gives a necessary and sufficientcondition for the existence of a matching in a given bipartitegraph. Aharoni and Ziv have generalized the notion of matchabilityto a pair of possibly infinite matroids on the same set andgiven a condition that is sufficient for the matchability ofa given pair (M, W) of finitary matroids, where the matroidM is SCF (a sum of countably many matroids of finite rank).The condition of Aharoni and Ziv is not necessary for matchability.The paper gives a condition that is necessary for the existenceof a matching for any pair of matroids (not necessarily finitary)and is sufficient for any pair (M, W) of finitary matroids,where the matroid M is SCF.     

<Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free subgraphs of random graphs revisited

In Combinatorica 17(2), 1997, Kohayakawa, ?uczak and Rödl state a conjecture which has several implications for random graphs. If the conjecture is true, then, for example, an application of a version of Szemerédi’s regularity lemma for sparse graphs yields an estimation of the maximal number of edges in an H-free subgraph of a random graph G _{n, p} . In fact, the conjecture may be seen as a probabilistic embedding lemma for partitions guaranteed by a version of Szemerédi’s regularity lemma for sparse graphs. In this paper we verify the conjecture for H = K ₄, thereby providing a conceptually simple proof for the main result in the paper cited above.     

Self-witnessing polynomial-time complexity and prime factorization

For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-time complexity are presented. Our main result demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete factorization of p - 1.     

Equivariant fixed-point indices of iterated maps

We describe an equivariant version (for actions of a finite group G) of Dold’s index theory, [10], for iterated maps. Equivariant Dold indices are defined, in general, for a G-map U → X defined on an open G-subset of a G-ANR X (and satisfying a suitable compactness condition). A local index for isolated fixed-points is introduced, and the theorem of Shub and Sullivan on the vanishing of all but finitely many Dold indices for a continuously differentiable map is extended to the equivariant case. Homotopy Dold indices, arising from the equivariant Reidemeister trace, are also considered.      

Near invariance and kernels of Toeplitz operators

This paper makes a systematic study of kernels of Toeplitz operators on scalar and vector-valued H _p spaces (for 1 < p < ∞). The property of near invariance of a kernel for the backward shift is analysed and shown to hold in increased generality. In the scalar case, and in some vectorial cases, the existence of a minimal kernel containing a given function is established, and a symbol for a corresponding Toeplitz operator is determined; thus, for rational symbols, its dimension can be easily calculated. It is shown that every Toeplitz kernel in H _p is the minimal kernel for some function lying in it.     

Mixed multiplicities and the minimal number of generator of modules

Let (R,m) be a d-dimensional Noetherian local ring. In this work we prove that the mixed Buchsbaum-Rim multiplicity for a finite family of R-submodules of R^p of finite colength coincides with the Buchsbaum-Rim multiplicity of the module generated by a suitable superficial sequence, that is, we generalize for modules the well-known Risler-Teissier theorem. As a consequence, we give a new proof of a generalization for modules of the fundamental Rees’ mixed multiplicity theorem, which was first proved by Kirby and Rees in (1994, [8]). We use the above result to give an upper bound for the minimal number of generators of a finite colength R-submodule of R^p in terms of mixed multiplicities for modules, which generalize a similar bound obtained by Cruz and Verma in (2000, [5]) for m-primary ideals.     

Complex Hadamard matrices

R. J. Turyn introduced complex Hadamard matrices and showed that if there is a complex Hadamard matrix of order c and a real Hadamard matrix of order h> > 1, then there is a real Hadamard matrix of order he. Previously, complex Hadamard matrices were only known for a few small orders and the orders for which symmetric conference matrices were known. These latter are known only to exist for orders which can be written as 1+a² +b² where a, b are integers. We give many constructions for new infinite classes of complex Hadamard matrices and show that they exist for orders 306,650, 870,1406,2450 and 3782: for the orders 650, 870, 2450 and 3782, a symmetric conference matrix cannot exist.