A note on the colorful fractional Helly theorem

Helly’s theorem is a classical result concerning the intersection patterns of convex sets in ${\mathbb{R}}^d$. Two important generalizations are the colorful version and the fractional version. Recently, Bárány et al. combined the two, obtaining a colorful fractional Helly theorem. In this paper, we give an improved version of their result.     

A topological colorful Helly theorem

Let be d+1 families of convex sets in . The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if for all choices of then there exists an 1?i?d+1 such that .Our main result is both a topological and a matroidal extension of the colorful Helly theorem. A simplicial complex X is d-Leray if for all induced subcomplexes Y⊂X and i?d.Theorem.LetXbe ad-Leray complex on the vertex setV. Suppose M is a matroidal complex on the same vertex setVwith rank functionρ. IfM⊂Xthen there exists a simplexτ∈Xsuch thatρ(V−τ)?d.     

On a generalization of Pólya’s theorem

We consider generalizations of Pólya’s theorem to the case of entire functions taking algebraic values at natural or integer points.     

射影空间中代数曲线与超曲面的一些新的性质

发现了代数曲线的新的不变量一特征数,并得到了Pascal定理的不同于3次曲线的Cllasles定理和高次曲线中的Cayley-Bacharach定理等形式的高次推广.进一步研究了平面代数曲线的一些性质.通过定义m次Pascal超曲面,将Pascal定理推广到n维射影空间的m次超曲面中,证明了n-单纯形上的Pascal点位于一个m次Pascal超曲面的充要条件是其每个2维面上的Pascal点分别位于m次平面Pascal空间的一条代数曲线上.进一步,给出了一定条件下m次Pascal超曲面与m-1次Pascal超曲面之间的内在关系.     

Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

On solving equations of algebraic sum of equal powers

It is well known that a system of equations of sum of equal powers can be converted to an algebraic equation of higher degree via Newton's identities. This is the Viete-Newton theorem. This work reports the generalizations of the Viete-Newton theorem to a system of equations of algebraic sum of equal powers. By exploiting some facts from algebra and combinatorics, it is shown that a system of equations of algebraic sum of equal powers can be converted in a closed form to two algebraic equations, whose degree sum equals the number of unknowns of the system of equations of algebraic sum of equal powers.     

Variations on the Theorem of Birkhoff – von Neumann and Extensions

 The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived by using elementary properties of graph theory. Received: October 10, 2000 Final version received: April 11, 2002     

Equivariant Gysin maps and pulling back fixed points

We develop a new approach to the pulling back fixed points theorem of W. Browder and use it in order to prove various generalizations of this result.

     

A Tverberg-type generalization of the Helly number of a convexity space

In 1966 H. Tverberg gave a far reaching generalization of the well-known classical theorem of J. Radon. In this paper a similar generalization of the classical Helly theorem is given and it is shown that among these two generalized theorems a relationship holds similar to a theorem proved by F.W. Levi in 1951. Also the generalized Helly theorem in the convex product and convex sum space are investigated.     

New developments in the theory of Gröbner bases and applications to formal verification

We present foundational work on standard bases over rings and on Boolean Gröbner bases in the framework of Boolean functions. The research was motivated by our collaboration with electrical engineers and computer scientists on problems arising from formal verification of digital circuits. In fact, algebraic modelling of formal verification problems is developed on the word-level as well as on the bit-level. The word-level model leads to Gröbner basis in the polynomial ring over Z/2ⁿ while the bit-level model leads to Boolean Gröbner bases. In addition to the theoretical foundations of both approaches, the algorithms have been implemented. Using these implementations we show that special data structures and the exploitation of symmetries make Gröbner bases competitive to state-of-the-art tools from formal verification but having the advantage of being systematic and more flexible.     

n-distributivity,dimension and Carathéodory's theorem

A. Huhn proved that the dimension of Euclidean spaces can be characterized through algebraic properties of the lattices of convex sets. In fact, the lattice of convex sets of isn+1-distributive but notn-distributive. In this paper his result is generalized for a class of algebraic lattices generated by their completely join-irreducible elements. The lattice theoretic form of Carathéodory's theorem characterizesn-distributivity in such lattices. Several consequences of this result are studied. First, it is shown how infiniten-distributivity and Carathéodory's theorem are related. Then the main result is applied to prove that for a large class of lattices beingn-distributive means being in the variety generated by the finiten-distributive lattices. Finally,n-distributivity is studied for various classes of lattices, with particular attention being paid to convexity lattices of Birkhoff and Bennett for which a Helly type result is also proved.Presented by J. Sichler.     

Unconditionally τ-closed and τ-algebraic sets in groups

Families of unconditionally τ-closed and τ-algebraic sets in a group are defined, which are natural generalizations of unconditionally closed and algebraic sets defined by Markov. A sufficient condition for the coincidence of these families is found. In particular, it is proved that these families coincide in any group of cardinality at most τ. This result generalizes both Markov's theorem on the coincidence of unconditionally closed and algebraic sets in a countable group (as is known, they may be different in an uncountable group) and Podewski's theorem on the topologizability of any ungebunden group.     

On the Gorenstein injective dimension and Bass formula

In this paper, we compare Krull dimension, Gorenstein injective dimension and injective dimension of a module in several cases. In fact, we establish some generalizations of the Bass formula. To this end, we generalize the Grothendieck non-vanishing theorem to a class of modules larger than finitely generated modules. Received: 21 May 2007     

On the helly property working as a compactness criterion on graphs

The study of combinatorial topology and of the most important methods in algebraic topology (simplicial complexes, discretization) leads to the idea that it may be useful to translate some of the most classical problems in topology into a discrete context. Following this principle, several authors have already tried to study fixed point and retraction problems inside the theory of partially ordered sets. We try here to make a special study about the extension of homomorphisms and the fixed point problems on graphs. We introduce here, using the Helly property, a kind of compactness tool working on graphs, and we prove a generalization of Sperner's lemma which is used in the proof of the Brouwer fixed-point theorem by Kuratowski.     

Counter-examples to non-noetherian Elkik's approximation theorem

Elkik established a remarkable theorem that can be applied for any noetherian henselian ring. For algebraic equations with a formal solution (restricted by some smoothness assumption), this theorem provides a solution adically close to the formal one in the base ring. In this paper, we show that the theorem would fail for some non-noetherian henselian rings. These rings do not satisfy several conditions weaker than noetherianness, such as weak proregularity (due to Grothendieck et al.) of the defining ideal. We describe the resulting pathologies.     

Helly Theorem and Related Results

By using the classical Helly theorem, one cannot obtain information about a family of convex compact sets in the n-dimensional Euclidean space if it is known that only subfamilies consisting of k elements, 0 < k n, have nonempty intersections. We modify the Helly theorem to fix this issue and investigate the behavior of generalized convex families.     

Measures of Simultaneous Approximation for Quasi-Periods of Abelian Varieties

We examine various extensions of a series of theorems proved by Chudnovsky in the 1980s on the algebraic independence (transcendence degree 2) of certain quantities involving integrals of the first and second kind on elliptic curves; these extensions include generalizations to abelian varieties of arbitrary dimensions, quantitative refinements in terms of measures of simultaneous approximation, as well as some attempt at unifying the aforementioned theorems. In the process we develop tools that might prove useful in other contexts, revolving around explicit “algebraic” theta functions on the one hand, and Eisenstein's theorem and G-functions on the other hand.     

On Distinguished Solutions of Truncated Matricial Hamburger Moment Problems

We study two slightly different versions of the truncated matricial Hamburger moment problem. A central topic is the construction and investigation of distinguished solutions of both moment problems under consideration. These solutions turn out to be nonnegative Hermitian q × q Borel measures on the real axis which are concentrated on a finite number of points. These points and the corresponding masses will be explicitly described in terms of the given data. Furthermore, we investigate a particular class of sequences (s_j)^∞_{j = 0} of complex q × q matrices for which the corresponding infinite matricial Hamburger moment problem has a unique solution. Our approach is mainly algebraic. It is based on the use of particular matrix polynomials constructed from a nonnegative Hermitian block Hankel matrix. These matrix polynomials are immediate generalizations of the monic orthogonal matrix polynomials associated with a positive Hermitian block Hankel matrix. We generalize a classical theorem due to Kronecker on infinite Hankel matrices of finite rank to block Hankel matrices and discuss its consequences for the nonnegative Hermitian case.     

The Poincaré series of multiplier ideals of a simple complete ideal in a local ring of a smooth surface

For a simple complete ideal ℘ of a local ring at a closed point on a smooth complex algebraic surface, we introduce an algebraic object, named Poincaré series P_℘, that gathers in a unified way the jumping numbers and the dimensions of the vector space quotients given by consecutive multiplier ideals attached to ℘. This paper is devoted to prove that P_℘ is a rational function giving an explicit expression for it.     

Arithmetic on Groups of Positive Rationals

In this paper we develop a theory of unique factorization for subgroups of the positive rationals. We show that this theory is strong enough to include arithmetic progressions and the theory of genera in algebraic number fields. We establish generalizations of both Dirichlet's theorem on primes in arithmetic progressions and the theory of genera for Abelian extensions of the rationals.