Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

On Shadows Of Intersecting Families

The shadow minimization problem for t-intersecting systems of finite sets is considered. Let be a family of k-subsets of . The -shadow of is the set of all (k-)-subsets contained in the members of . Let be a t-intersecting family (any two members have at least t elements in common) with . Given k,t,m the problem is to minimize (over all choices of ). In this paper we solve this problem when m is big enough.     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

Set Systems with few Disjoint Pairs

Let X = {1, . . . , n}, and let be a family of subsets of X. Given the size of , at least how many pairs of elements of must be disjoint? In this paper we give a lower bound for the number of disjoint pairs in . The bound we obtain is essentially best possible. In particular, we give a new proof of a result of Frankl and of Ahlswede, that if satisfies then contains at least as many disjoint pairs as X^(r).The situation is rather different if we restrict our attention to : then we are asking for the minimum number of edges spanned by a subset of the Kneser graph of given size. We make a conjecture on this lower bound, and disprove a related conjecture of Poljak and Tuza on the largest bipartite subgraph of the Kneser graph.* Research partially supported by NSF grant DMS-9971788     

The number oft-wise balanced designs

We prove that the number oft-wise balanced designs of ordern is asymptotically , provided that blocks of sizet are permitted. In the process, we prove that the number oft-profiles (multisets of block sizes) is bounded below by and above by for constants c₂>c₁>0.     

Spectral triangles of Schrödinger operators with complex potentials

Consider the Schrödinger operator with a complex-valued potential v of period Let and be the eigenvalues of L that are close to respectively, with periodic (for n even), antiperiodic (for n odd), and Dirichelet boundary conditions on [0,1], and let be the diameter of the spectral triangle with vertices We prove the following statement: If then v(x) is a Gevrey function, and moreover      

Natural spline functions,their associated eigenvalue problem

Summary We consider the problem of studying the behaviour of the eigenvalues associated with spline functions with equally spaced knots. We show that they are wherem is the order of the spline andn, the number of knots.This result is of particular interest to prove optimality properties of the Generalized Cross-Validation Method and had been conjectured by Craven and Wahba in a recent paper.     

Projectively flat affine surfaces

We study non-degenerate affine surfaces in A³ with a projectively flat induced connection. The curvature of the affine metric , the affine mean curvature H, and the Pick invariant J are related by . Depending on the rank of the span of the gradients of these functions, a local classification of three groups is given. The main result is the characterization of the projectively flat but not locally symmetric surfaces as a solution of a system of ODEs. In the final part, we classify projectively flat and locally symmetric affine translation surfaces.     

Tubes of even order and flat π.C 2 geometries

Atube of even orderq=2 ^d is a setT={L, } ofq+3 pairwise skew lines in PG(3,q) such that every plane onL meets the lines of in a hyperoval. Thequadric tube is obtained as follows. Take a hyperbolic quadricQ=Q ₃ ⁺ (q) in PG(3,q); letL be an exterior line, and let consist of the polar line ofL together with a regulus onQ.In this paper we show the existence of tubes of even order other than the quadric one, and we prove that the subgroup of PL(4,q) fixing a tube {L, } cannot act transitively on . As pointed out by a construction due to Pasini, this implies new results for the existence of flat .C ₂ geometries whoseC ₂-residues are nonclassical generalized quadrangles different from nets. We also give the results of some computations on the existence and uniqueness of tubes in PG(3,q) for smallq. Further, we define tubes for oddq (replacing hyperoval by conic in the definition), and consider briefly a related extremal problem.Dedicated to luigi antonio rosati on the occasion of his 70th birthday     

Small Complete Arcs in Projective Planes

In the late 1950s, B. Segre introduced the fundamental notion of arcs and complete arcs [48,49]. An arc in a nite projective plane is a set of points with no three on a line and it is complete if cannot be extended without violating this property. Given a projective plane , determining , the size of its smallest complete arc, has been a major open question in finite geometry for several decades. Assume that has order q, it was shown by Lunelli and Sce [41], more than 40 years ago, that . Apart from this bound, practically nothing was known about , except for the case is the Galois plane. For this case, the best upper bound, prior to this paper, was O(q ^3/4) obtained by Sznyi using the properties of the Galois field GF(q).In this paper, we prove that for any projective plane of order q, where c is a universal constant. Together with Lunelli-Sces lower bound, our result determines up to a polylogarithmic factor. Our proof uses a probabilistic method known as the dynamic random construction or Rödls nibble. The proof also gives a quick randomized algorithm which produces a small complete arc with high probability.The key ingredient of our proof is a new concentration result, which applies for non-Lipschitz functions and is of independent interest.* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.Part of this work was done at AT&T Bell Labs and Microsoft Research     

Linear Codes and Character Sums

Let V be an rn-dimensional linear subspace of . Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and Linial and show that the fraction of vectors in V with weight d is exponentially small. Specifically, in the interesting case of a small r, this fraction does not exceed .We also answer a question of Ben-Or and show that if , then for every k, at most vectors of V have weight k.Our work draws on a simple connection between extremal properties of linear subspaces of and the distribution of values in short sums of -characters.* Supported in part by grants from the Israeli Academy of Sciences and the Binational Science Foundation Israel-USA. This work was done while the author was a student in the Hebrew University of Jerusalem, Israel.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

Set of involutions arising from an egglike inversive plane

To every egglike inversive plane there is associated a family of involutions of the point set of such that circles of are the fixed point sets of the involutions in . Korchmaros and Olanda characterized a family of involutions on a set of size n² + 1to be for an egglike inversive plane of order n by four conditions. In this paper, we give an alternative proof where the Galois space PG(3,n) in which is embedded is built up directly by using concepts and results on finite linear spaces.     

Gray codes from antimatroids

We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.For antimatroid (E, ), letJ( ) denote the graph whose vertices are the sets of , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( ;k) to be the subgraph ofJ( )² induced by the sets in with exactlyk elements. Both graphsJ( ) andJ( ;k) are connected, and the former is bipartite.We show that there is a Hamiltonian cycle inJ( )×K ₂. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( ;k) has a Hamilton path if (E, ) is the poset antimatroid of a series-parallel poset.Similarly, we show thatG( )×K ₂ is Hamiltonian, whereG( ) is the basic word graph of a language antimatroid (E, ). This result was known previously for poset antimatroids.Research supported in part by NSERC.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.     

Beckman-Quarles type theorems for mappings from $$ \mathbb{R}^n $$ to $$ \mathbb{C}^n $$

Summary. Let We say that preserves the distance d 0 if for each implies Let A _n denote the set of all positive numbers d such that any map that preserves unit distance preserves also distance d. Let D _n denote the set of all positive numbers d with the property: if and then there exists a finite set S _xy with such that any map that preserves unit distance preserves also the distance between x and y. Obviously, We prove: (1) (2) for n 2 D _n is a dense subset of (2) implies that each mapping f from to (n 2) preserving unit distance preserves all distances, if f is continuous with respect to the product topologies on and      

Self-dual sets of type (m, n) in projective spaces

In this paper we introduce and analyze the notion of self-dual k-sets of type (m, n). We show that in a non-square order projective space such sets exist only if the dimension is odd. We prove that, in a projective space of odd dimension and order q, self-dual k-sets of type (m, n), with , are of elliptic and hyperbolic type, respectively. As a corollary we obtain a new characterization of the non-singular elliptic and hyperbolic quadrics.     

Polynomial Lym Inequalities

For a Sperner family A 2^[n] let A _i denote the family of all i-element sets in A. We sharpen the LYM inequality by adding to the LHS all possible products of fractions , with suitable coefficients. A corresponding inequality is established also for the linear lattice and the lattice of subsets of a multiset (with all elements having the same multiplicity).* Research supported by the Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, University of Bielefeld.     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

The probability of generating a permutation group

It is well known that a permutation group of degree can be generated by elements. In this paper we study the asymptotic behavior of the probability of generating a permutation group of degree n with elements. In particular we prove that if n is large enough and elements generate a permutation group G of degree n modulo G G ², then almost certainly these elements generate G itself. Received: 2 January 2002