A subanalytic triangulation theorem for real analytic orbifolds

Let X be a real analytic orbifold. Then each stratum of X is a subanalytic subset of X. We show that X has a unique subanalytic triangulation compatible with the strata of X. We also show that every Cr-orbifold, 1?r?∞, has a real analytic structure. This allows us to triangulate differentiable orbifolds. The results generalize the subanalytic triangulation theorems previously known for quotient orbifolds.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

On the genus of real projective spaces

We construct a crystallization of the real projective space whose associated contracted complex is minimal with respect to the number of n-simplexes. Then we compute the regular genus of , which is the minimum genus of a closed connected surface into which a crystallization of regularly embeds. Received: 7 February 2007     

The Gauss-Bonnet theorem for vector bundles

We give a short proof of the Gauss-Bonnet theorem for a real oriented Riemannian vector bundle E of even rank over a closed compact orientable manifold M. This theorem reduces to the classical Gauss-Bonnet-Chern theorem in the special case when M is a Riemannian manifold and E is the tangent bundle of M endowed with the Levi-Civita connection. The proof is based on an explicit geometric construction of the Thom class for 2-plane bundles. Dedicated to the memory of Philip Bell Research partially supported by NSF grant DMS-9703852.     

An approximation theorem in shape theory

In this paper it is shown that if X is a compactum in the interior of a PL manifold M and if U is a neighborhood of X in M, then there is a compactum X′ in U such that X and X′ have the same relative shape in U and the embedding dimension of X′ equals the fundamental dimension of X. Whenever the dimension of M is not equal to three, the relative shape equivalence from X′ to X can be realized by an infinite isotopy of M.     

Lower Bounds in Minimum Rank Problems

The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.     

A graph-theoretical representation of PL-manifolds — A survey on crystallizations

This is a survey of the techniques and results developed by M. Pezzana and his group, which includes, besides the authors, A. Cavicchioli, P. Bandieri and A Donati.The original concept is that of contracted triangulation, which was introduced with the main goal of finding a minimal atlas for topological manifolds ([P₁ 1968], [P₂ 1974], [P₃ 1974], [FG₂ 1979]). Only later did the possibility of deducing a graph-theoretical tool — the crystallization — for representing P.L. manifolds occur as a major aspect of the theory ([P₄ 1975], [F₁ 1976]). This leads to an application of graph theory to P.L. topology, which seems not to have been explored before. Recently, other authors outside Italy have independently become interested in this subject.For the sake of conciseness, definitions and statements often appear in a form other than that of the quoted references.     

Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes

In this paper we provide concrete combinatorial formal deformation algorithms, namely sequences of elementary collapses and expansions, which relate various previously extensively studied families of combinatorially defined polyhedral complexes.To start with, we give a sequence of elementary collapses leading from the barycentric subdivision of the neighborhood complex to the Lovász complex of a graph. Then, for an arbitrary lattice L we describe a formal deformation of the barycentric subdivision of the atom crosscut complex Γ(L) to its order complex . We proceed by proving that the complex of sets bounded from below J(L) can also be collapsed to .Finally, as a pinnacle of our project, we apply all these results to certain graph complexes. Namely, by describing an explicit formal deformation, we prove that, for any graph G, the neighborhood complex N(G) and the polyhedral complex Hom(K₂,G) have the same simple homotopy type in the sense of Whitehead.     

Lower bound of the hadwiger number of graphs by their average degree

The aim of this paper is to show that the minimum Hadwiger number of graphs with average degreek isO(k/√logk). Specially, it follows that Hadwiger’s conjecture is true for almost all graphs withn vertices, furthermore ifk is large enough then for almost all graphs withn vertices andnk edges.     

Spectral properties of threshold functions

We examine the spectra of boolean functions obtained as the sign of a real polynomial of degreed. A tight lower bound on various norms of the lowerd levels of the function's Fourier transform is established. The result is applied to derive best possible lower bounds on the influences of variables on linear threshold functions. Some conjectures are posed concerning upper and lower bounds on influences of variables in higher order threshold functions.Supported by an Eshkol fellowship, administered by the National Council for Research and Development—Israel Ministry of Science and Development.     

Vertex-minimal simplicial immersions of the Klein bottle in three space

Although the Klein bottle cannot be embedded inR ³, it can be immersed there, and in more than one way. Smooth examples of these immersions have been studied extensively, but little is known about their simplicial versions. The vertices of a triangulation play a crucial role in understanding immersions, so it is reasonable to ask: How few vertices are required to immerse the Klein bottle inR ³? Several examples that use only nine vertices are given in Section 3, and since any triangulation of the Klein bottle must have at least eight vertices, the question becomes: Can the Klein bottle be immersed inR ³ using only eight vertices? In this paper, we show that, in fact, eight isnot enough, nine are required. The proof consists of three parts: first exhibiting examples of 9-vertex immersions; second determining all possible 8-vertex triangulations ofK ²; and third showing that none of these can be immersed inR ³.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Discrete Morse theory on graphs

We characterize the topology of a graph in terms of the critical elements of a discrete Morse function defined on it. Besides, we study the structure and some properties of the gradient vector field induced by a discrete Morse function defined on a graph. Finally, we get results on the number of non-homologically equivalent excellent discrete Morse functions defined on some kind of graphs.     

Combinatorial handles and manifolds with boundary

In this work we complete the study ofcombinatorial handles in (n+1)-coloured graphs with boundary, introduced in [G₁], [L] and [GV] for graphs with empty boundary and in [BGV] for 3-coloured graphs with boundary. In particular, we study the cancelling of a combinatorial handle from an (n+1)-coloured graph and its effects on the associated complex.Work performed under the auspices of the G.N.S.A.G.A. — C.N.R., and within the Project Geometria reale e complessa, supported by M.U.R.S.T. of Italy.     

Polyhedra as domains of harmonic maps

Certain more or less known properties of polyhedra in combinatorial topology are established. In particular, the concept of normal pseudomanifolds is extended to so-called admissible polyhedra, whereby branching may occur. Admissible Riemannian polyhedra serve as domains of (generalized) harmonic functions or maps.     

Law of large numbers and central limit theorem for randomly forced PDE's

We consider a class of dissipative PDE's perturbed by an external random force. Under the condition that the distribution of perturbation is sufficiently non-degenerate, a strong law of large numbers (SLLN) and a central limit theorem (CLT) for solutions are established and the corresponding rates of convergence are estimated. It is also shown that the estimates obtained are close to being optimal. The proofs are based on the property of exponential mixing for the problem in question and some abstract SLLN and CLT for mixing-type Markov processes.     

Serre-Taubes duality for pseudoholomorphic curves

According to Taubes, the Gromov invariants of a symplectic four-manifold X with b₊>1 satisfy the duality Gr(α)=±Gr(κ−α), where κ is Poincaré dual to the canonical class. Extending joint work with Simon Donaldson, we interpret this result in terms of Serre duality on the fibres of a Lefschetz pencil on X, by proving an analogous symmetry for invariants counting sections of associated bundles of symmetric products. Using similar methods, we give a new proof of an existence theorem for symplectic surfaces in four-manifolds with b₊=1 and b₁=0. This reproves another theorem due to Taubes: two symplectic homology projective planes with negative canonical class and equal volume are symplectomorphic.     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

THE FUNDAMENTAL GROUP IN FIBRATIONS

A generalized Mayer-Vietoris sequence involving crossed homomorphisms is established and the construction is applied to the homotopy sequence of the CW-pair (X.X¹) to relate the homotopy sequences of (X.X¹) and the fibre bundle F → E → X in low dimensions. If there is a partial cross-section of E → X over X², the classical form, π₁ E ～ π₁ [xtilde] π₁ F as a semidirect product, results. In case there is no extension over X² of any cross-section of the restricted bundle χ:π₂ (x², x¹) → X¹ the corresponding obstruction map X_E:π₂(x²,x¹) → π₁F is non-trivial and in case F → E → X is an SO(n)-bundle (n ≥ 3), χ_E maps into a subgroup of the centre, Z(π₁ F), of order at most 2.     

Embeddings of homology equivalent manifolds with boundary

We prove a theorem on equivariant maps implying the following two corollaries:(1) Let N and M be compact orientable n-manifolds with boundaries such that M⊂N, the inclusion M→N induces an isomorphism in integral cohomology, both M and N have (n−d−1)-dimensional spines and . Then the restriction-induced map Embm(N)→Embm(M) is bijective. Here Embm(X) is the set of embeddings X→Rm up to isotopy (in the PL or smooth category).(2) For a 3-manifold N with boundary whose integral homology groups are trivial and such that N?D³ (or for its special 2-spine N) there exists an equivariant map , although N does not embed into R³.The second corollary completes the answer to the following question: for which pairs (m,n) for each n-polyhedron N the existence of an equivariant map implies embeddability of N into Rm? An answer was known for each pair (m,n) except (3,3) and (3,2).