A note on the independence number of triangle-free graphs

Let G be a triangle-free graph on n points with average degree d. Let α be the independence number of G. In this note we give a simple proof that α ? n (d ln d ? d + 1)/(d ? 1)². We also consider what happens when G contains a limited number of triangles.     

On partial polynomial interpolation

The Alexander-Hirschowitz theorem says that a general collection of k double points in Pⁿ imposes independent conditions on homogeneous polynomials of degree d with a well known list of exceptions. We generalize this theorem to arbitrary zero-dimensional schemes contained in a general union of double points. We work in the polynomial interpolation setting. In this framework our main result says that the affine space of polynomials of degree ?d in n variables, with assigned values of any number of general linear combinations of first partial derivatives, has the expected dimension if d≠2 with only five exceptional cases. If d=2 the exceptional cases are fully described.     

Dynamic point location in arrangements of hyperplanes

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure isÕ(polylog(n)), wheren is the number of hyperplanes at any given time, and theÕ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement isÕ(n ^d). The cost of update isÕ(n ^d?1 logn. The expected cost of update isO(n ^d?1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimalÕ(logn) query time, expectedO(n ^d) space requirement, and amortizedO(n ^d?1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. Ford=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.     

A note on lattice chains and Delannoy numbers

Fix nonnegative integers n₁,…,n_d and let L denote the lattice of integer points (a₁,…,a_d)∈Z^d satisfying 0?a_i?n_i for 1?i?d. Let L be partially ordered by the usual dominance ordering. In this paper we offer combinatorial derivations of a number of results concerning chains in L. In particular, the results obtained are established without recourse to generating functions or recurrence relations. We begin with an elementary derivation of the number of chains in L of a given size, from which one can deduce the classical expression for the total number of chains in L. Then we derive a second, alternative, expression for the total number of chains in L when d=2. Setting n₁=n₂ in this expression yields a new proof of a result of Stanley [Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999] relating the total number of chains to the central Delannoy numbers. We also conjecture a generalization of Stanley's result to higher dimensions.     

On the order of an automorphism of a smooth hypersurface

In this paper we give an effective criterion as to when a positive integer q is the order of an automorphism of a smooth hypersurface of dimension n and degree d, for every d ≥ 3, n ≥ 2, (n, d) ≠ (2, 4), and gcd(q, d) = gcd(q, d ? 1) = 1. This allows us to give a complete criterion in the case where q = p is a prime number. In particular, we show the following result: If X is a smooth hypersurface of dimension n and degree d admitting an automorphism of prime order p then p < (d ? 1) ⁿ⁺¹; and if p > (d ? 1) ⁿ then X is isomorphic to the Klein hypersurface, n = 2 or n + 2 is prime, and p = Φ _n+2(1 ? d) where Φ _n+2 is the (n+2)-th cyclotomic polynomial. Finally, we provide some applications to intermediate jacobians of Klein hypersurfaces.     

On the discrepancy of some special sequences

We obtain estimates for the discrepancy of the sequence (xs^(d)(q;n))_n=0^∞, where s^(d)(q;n) denotes the sum of the dth powers of the q-ary digits of the nonnegative integer n and x is an irrational number of finite approximation type. Furthermore metric results for a similar type of sequences are given.     

Leafy spanning trees in hypercubes

We prove that the d-dimensional hypercube, Q_d, with n = 2^d vertices, contains a spanning tree with at least

leaves. This improves upon the bound implied by a more general result on spanning trees in graphs with minimum degree δ, which gives (1 − O(log log n)/log₂n)n as a lower bound on the maximum number of leaves in spanning trees of n-vertex hypercubes.     

On units of real quadratic fields

Let ∈ = (t + u(d)2/2 be a unit of Q((d)1/2), whose norm = 1. We investigate the properties of the factors of the number u_n which is defined by ∈ⁿ = (t_n + u_n(d)1/2)/2.     

Conjectures on GCn sets

The paper gives a generalization of the counterexample of C. de Boor on ? ^d and provides an example of GC ₂ set in ?⁴ with three maximal hyperplanes. Also, a conjecture on the number of maximal lines of GC _n sets in ? ^d is discussed and proved that it is true in the case when n = 2, d = 3.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

Essentially optimal computation of the inverse of generic polynomial matrices

We present an inversion algorithm for nonsingular n×n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires O^∼(n³d) field operations for a generic input; the soft-O notation O^∼ indicates some missing log(nd) factors. Up to such logarithmic factors, this asymptotic complexity is of the same order as the number of distinct field elements necessary to represent the inverse matrix.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

On the number of minimal transversals in 3-uniform hypergraphs

We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cⁿ, where c≈1.6702. The best known lower bound for this number, due to Tomescu, is adⁿ, where d=10^1/5≈1.5849 and a is a constant.     

Defect indices of powers of a contraction

Let A be a contraction on a Hilbert space H. The defect index d_A of A is, by definition, the dimension of the closure of the range of I-A^∗A. We prove that (1) d_Aⁿ?nd_A for all n?0, (2) if, in addition, Aⁿ converges to 0 in the strong operator topology and d_A=1, then d_Aⁿ=n for all finite n,0?n?dimH, and (3) d_A=d_A^∗ implies d_Aⁿ=d_A^n∗ for all n?0. The norm-one index k_A of A is defined as sup{n?0:‖Aⁿ‖=1}. When dimH=m<∞, a lower bound for k_A was obtained before: k_A?(m/d_A)-1. We show that the equality holds if and only if either A is unitary or the eigenvalues of A are all in the open unit disc, d_A divides m and d_Aⁿ=nd_A for all n, 1?n?m/d_A. We also consider the defect index of f(A) for a finite Blaschke product f and show that d_f(A)=d_Aⁿ, where n is the number of zeros of f.     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

Construction of bent functions via Niho power functions

A Boolean function with an even number n=2k of variables is called bent if it is maximally nonlinear. We present here a new construction of bent functions. Boolean functions of the form f(x)=tr(α₁x^d₁+α₂x^d₂), α₁,α₂,x∈F_2ⁿ, are considered, where the exponents d_i (i=1,2) are of Niho type, i.e. the restriction of x^d_i on F_2^k is linear. We prove for several pairs of (d₁,d₂) that f is a bent function, when α₁ and α₂ fulfill certain conditions. To derive these results we develop a new method to prove that certain rational mappings on F_2ⁿ are bijective.     

On Cohen braids

For a general connected surface M and an arbitrary braid α from the surface braid group B _n?1(M), we study the system of equations d ₁ β = … = d _n β = α, where the operation d _i is the removal of the ith strand. We prove that for M ≠ S ² and M ≠ ?P², this system of equations has a solution β ∈ B _n (M) if and only if d ₁ α = … = d _n?1 α. We call the set of braids satisfying the last system of equations Cohen braids. We study Cohen braids and prove that they form a subgroup. We also construct a set of generators for the group of Cohen braids. In the cases of the sphere and the projective plane we give some examples for a small number of strands.     

Long paths and cycles in subgraphs of the cube

Let Q _n denote the graph of the n-dimensional cube with vertex set {0, 1} ⁿ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose G is a subgraph of Q _n with average degree at least d. How long a path can we guarantee to find in G? Our aim in this paper is to show that G must contain an exponentially long path. In fact, we show that if G has minimum degree at least d then G must contain a path of length 2 ^d ? 1. Note that this bound is tight, as shown by a d-dimensional subcube of Q _n . We also obtain the slightly stronger result that G must contain a cycle of length at least 2 ^d .     

Decompositions of vector spaces over GF(2) into disjoint equidimensional affine spaces

We investigate the possibilities for decomposing the vector space [GF(2)]ⁿ into a set of 2^r?d (necessarily disjoint) d dimensional affine subspaces.