The Monodromy Conjecture for hyperplane arrangements

The Monodromy Conjecture asserts that if c is a pole of the local topological zeta function of a hypersurface, then exp(2πic) is an eigenvalue of the monodromy on the cohomology of the Milnor fiber. A stronger version of the conjecture asserts that every such c is a root of the Bernstein-Sato polynomial of the hypersurface. In this note we prove the weak version of the conjecture for hyperplane arrangements. Furthermore, we reduce the strong version to the following conjecture: −n/d is always a root of the Bernstein-Sato polynomial of an indecomposable essential central hyperplane arrangement of d hyperplanes in C ⁿ .     

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 ) .     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

A geometric connection to threshold logic via cubical lattices

A cut-complex is a cubical complex whose vertices are strictly separable from the rest of the vertices of the n-cube by a hyperplane of R ⁿ . These objects render geometric presentations for threshold Boolean functions, the core objects of study in threshold logic. By applying cubical lattices and geometry of rotating hyperplanes, we prove necessary and sufficient conditions to recognize the cut-complexes with 2 or 3 maximal faces. This result confirms a positive answer to an old conjecture of Metropolis-Rota concerning cubical lattices.     

A simpler and tighter redundant Klee–Minty construction

By introducing redundant Klee–Minty examples, we have previously shown that the central path can be bent along the edges of the Klee–Minty cubes, thus having 2 ⁿ −2 sharp turns in dimension n. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and N, the total number of the redundant hyperplanes is reduced by a factor of n ², further tightening the gap between iteration-complexity upper and lower bounds.     

Estimates on Conjectures of Minkowski and woods

Let ℝ ⁿ be the n-dimensional Euclidean space. Let ∧ be a lattice of determinant 1 such that there is a sphere |X| < R which contains no point of ∧ other than the origin O and has n linearly independent points of ∧ on its boundary. A well known conjecture in the geometry of numbers asserts that any closed sphere in ℝ ⁿ of radius $ \sqrt {n/4} $ \sqrt {n/4} contains a point of ∧. This is known to be true for n ≤ 8. Here we give estimates on a more general conjecture of Woods for n ≥ 9. This leads to an improvement for 9 ≤ n ≤ 22 on estimates of Il’in (1991) to the long standing conjecture of Minkowski on product of n non-homogeneous linear forms.     

Quivers of semi-maximal rings

In this paper, the set of quivers of semi-maximal rings is investigated. It is proved that the elements of this set are formed by the elements of the set of quivers of tiled orders and that the set of quivers of tiled orders with n vertices is determined by the integer points of a convex polyhedral domain that lie in the nonnegative part of the space . It is also proved that the set of quivers of tiled orders with n vertices contains all simple, oriented, strongly connected graphs with n vertices and n loops, does not contain any graphs with n vertices and n − 1 loops, and contains only a part of the graphs with n vertices and m (m < n − 1) loops. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 215–223, 2005.     

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

Asymptotic formulas for the enumerator of trees with a given number of hanging or internal vertices

Let t(r, n) be the number of trees with n vertices of which r are hanging and q are internal (r=n−9). For a fixed r or q we prove the validity of the asymptotic formulas (r > 2)t(r, n)≈t/r|(r−2)| 2^2−r n ^2r−4 (n→∞)t(n−q, n)≈1/q|(q&#x2212;1)|q ^q−2 n ^q−1 (n→∞) In the derivation of these formulas we do not use the expression for the enumerator of the trees with respect to the number of hanging vertices. Translated from Matematicheskie Zametki, Vol. 21, No. 1, pp. 65–70, January, 1977.     

A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

Finite sets on curves and surfaces

A complete proof is given for Schnirelmann’s theorem on the existence of a square inC ² Jordan curves. The following theorems are then proved, using the same method: 1. On every hypersurface inR ⁿ,C ³-diffeomorphic toS ⁿ⁻¹, there exist 2n points which are the vertices of a regular 2 ⁿ -cellC _n. 2. Every planeC′ Jordan curve can beC′ approximated by a curve on which there are 2N distinct points which are the vertices of a centrally symmetric 2N-gon (anglesπ not excluded). 3. On every planeC ² curve there exist 5 distinct points which are the vertices of an axially symmetric pentagon with given base anglesa, π/2≦a<π. (The angle at the vertex on the axis of symmetry might beπ). Research supported by Grant AF-AFOSR-664-64, Air Force Office of Scientific Research.     

P4k?1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k−1-factorization of λK _m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer.     

Depth in an Arrangement of Hyperplanes

A collection of n hyperplanes in ^d forms a hyperplane arrangement. The depth of a point is the smallest number of hyperplanes crossed by any ray emanating from θ . For d=2 we prove that there always exists a point θ with depth at least . For higher dimensions we conjecture that the maximal depth is at least . For arrangements in general position, an upper bound on the maximal depth is also established. Finally, we discuss algorithms to compute points with maximal depth. Received December 1, 1997, and in revised form June 6, 1998.     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

A Note on the Sticky Matroid Conjecture

A matroid is sticky if any two of its extensions by disjoint sets can be glued together along the common restriction (that is, they have an amalgam). The sticky matroid conjecture asserts that a matroid is sticky if and only if it is modular. Poljak and Turzík proved that no rank-3 matroid having two disjoint lines is sticky. We show that, for r ≥ 3, no rank−r matroid having two disjoint hyperplanes is sticky. These and earlier results show that the sticky matroid conjecture for finite matroids would follow from a positive resolution of the rank-4 case of a conjecture of Kantor.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. Received: December 16, 1996 / Revised: September 17, 1997     

Each 3-strong Tournament Contains 3 Vertices Whose Out-arcs Are Pancyclic

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it is in a cycle of length k for all 3 ≤ k ≤ n. Yeo (Journal of Graph Theory, 50 (2005), 212–219) proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong tournaments. The author is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH Aachen University, Germany.