Probabilistic Extensions of the Erdős–Ko–Rado Property

The classical Erdős–Ko–Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size , then the largest possible pairwise intersecting family has size . We consider the probability that a randomly selected family of size t=t _n has the EKR property (pairwise nonempty intersection) as n and k=k _n tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson’s inequality. Using the Stein–Chen method we show that the distribution of X ₀, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for X _i , the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution (X ₀, X ₁, ..., X _b ) can be approximated by a multidimensional Poisson vector with independent components.      

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

On the limit laws of the second order for additive functionals of Harris recurrent Markov chains

Let {X _n } _{n ≥0} be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals of the form

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

On the limit of large girth graph sequences

Let d≥2 be given and let μ be an involution-invariant probability measure on the space of trees T ∈ T _d with maximum degrees at most d. Then μ arises as the local limit of some sequence {G _n } _n=1^∞ of graphs with all degrees at most d. This answers Question 3.3 of Bollobás and Riordan [4].     

On the measure of approximation of the number π by algebraic numbers

By means of the method of the Laurent interpolation determinant, it is proved that, if ζ is an algebraic number, the real numbersd andL satisfy the inequalitiesd≥degζ,L≥L(ζ), andL≥3, and the numberd is sufficiently large, then the inequality

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

A Jordan–Brouwer Separation Theorem for Polyhedral Pseudomanifolds

The Jordan Curve Theorem referring to a simple closed curve in the plane has a particularly simple proof in the case that the curve is polygonal, called the “raindrop proof”. We generalize the notion of a simple closed polygon to that of a polyhedral (d−1)-pseudomanifold (d≥2) and prove a Jordan–Brouwer Separation Theorem for such a manifold embedded in ℝ ^d . As a by-product, we get bounds on the polygonal diameter of the interior and exterior of such a manifold which are almost tight. This puts the result within the frame of computational geometry. The research of Y.S. Kupitz was partially supported by the Landau Center at the Mathematics Institute of the Hebrew University of Jerusalem (supported by Minerva Foundation, Germany), and by Deutsche Forschungsgemeinschaft.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Asymptotic behavior of solutions to viscous conservation laws with slowly varying external forces

This paper considers the existence and large time behavior of solutions to the convection-diffusion equation u _t −Δu+b(x)·∇(u|u| ^{q −1})=f(x, t) in ℝ ⁿ ×[0,∞), where f(x, t) is slowly decaying and q≥1+1/n (or in some particular cases q≥1). The initial condition u ₀ is supposed to be in an appropriate L ^p space. Uniform and nonuniform decay of the solutions will be established depending on the data and the forcing term.This work is partially supported by an AMO Grant     

Using Lagrangians of Hypergraphs to Find Non-Jumping Numbers (I)

Let r ≥ 2 be an integer. A real number is a jump for r if for any and any integer m, m ≥ r, any r-uniform graph with vertices and density at least contains a subgraph with m vertices and density at least α + c, where c = c(α) does not depend on or m. It follows from a result of Erdős, Stone, and Simonovits that every is a jump for r = 2. Erdőos asked whether the same is true for r ≥ 3. Frankl and R?dl gave a negative answer by showing an infinite sequence of non-jumping numbers for r ≥ 3. However, there are a lot of unknowns on determining whether a number is a jump for r ≥ 3. In this paper, we first find two infinite sequences of non-jumping numbers for r = 4, then we extend one of the results to every r ≥ 4. Our approach is still based on the approach developed by Frankl and R?dl. Received November 30, 2005     

The d-Step Conjecture and Gaussian Elimination

The d-step conjecture is one of the fundamental open problems concerning the structure of convex polytopes. Let Δ (d,n) denote the maximum diameter of a graph of a d-polytope that has n facets. The d-step conjecture Δ (d,2d) = d is proved equivalent to the following statement: For each ``general position' real matrix M there are two matrices drawn from a finite group matrices isomorphic to the symmetric group on d letters, such that has the Gaussian elimination factorization L ^-1 U in which L and U are lower triangular and upper triangular matrices, respectively, that have positive nontriangular elements. If #(M) is the number of pairs giving a positive L ^-1 U factorization, then #(M) equals the number of d-step paths between two vertices of an associated Dantzig figure. One consequence is that #(M)≤ d!. Numerical experiments all satisfied #(M) ≥ 2 ^d-1 , including examples attaining equality for 3 ≤ d ≤ 15. The inequality #(M) ≥ 2 ^d-1 is proved for d=3. For d≥ 4, examples with #(M) =2 ^d-1 exhibit a large variety of combinatorial types of associated Dantzig figures. These experiments and other evidence suggest that the d-step conjecture may be true in all dimensions, in the strong form #(M) ≥ 2 ^d-1 . Received April 10, 1995, and in revised form August 23, 1995.     

Variations on the theme of repeated distances

We give an asymptotically sharp estimate for the error term of the maximum number of unit distances determined byn points in ^{d, d}4. We also give asymptotically tight upper bounds on the total number of occurrences of the favourite distances fromn points in ^{d, d}4. Related results are proved for distances determined byn disjoint compact convex sets in ².At the time this paper was written, both authors were visiting the Technion — Israel Institute of Technology.     

Asymptotic properties of combinatorial optimization problems in <Emphasis Type="Italic">p</Emphasis>-adic space

In this article we consider two well known combinatorial optimization problems (travel-ling salesman and minimum spanning tree), when n points are randomly distributed in a unit p-adic ball of dimension d. We investigate an asymptotic behavior of their solutions at large number of n. It was earlier found that the average lengths of the optimal solutions in both problems are of order n ^1−1/d . Here we show that standard deviations of the optimal lengths are of order n ^1/2−1/d if d > 1, and prove that large number laws are valid only for special subsequences of n.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

The density of rational points on non-singular hypersurfaces

LetF(x) =F[x₁,…,x_n]∈ℤ[x₁,…,x_n] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ ⁿ ;F(x)=0, |x|⩽X}, where . It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X ^n−2+2/n for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields. However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process. Dedicated to the memory of Professor K G Ramanathan     

Numerical integration with polynomial exactness over a spherical cap

This paper presents rules for numerical integration over spherical caps and discusses their properties. For a spherical cap on the unit sphere \mathbbS²\mathbb{S}^2, we discuss tensor product rules with n ²/2 + O(n) nodes in the cap, positive weights, which are exact for all spherical polynomials of degree ≤ n, and can be easily and inexpensively implemented. Numerical tests illustrate the performance of these rules. A similar derivation establishes the existence of equal weight rules with degree of polynomial exactness n and O(n ³) nodes for numerical integration over spherical caps on \mathbbS²\mathbb{S}^2. For arbitrary d ≥ 2, this strategy is extended to provide rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that have O(n ^d ) nodes in the cap, positive weights, and are exact for all spherical polynomials of degree ≤ n. We also show that positive weight rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that are exact for all spherical polynomials of degree ≤ n have at least O(n ^d ) nodes and possess a certain regularity property.     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002