Minimum cutsets for an element of a boolean lattice

An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B _n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B _n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076.     

The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

Representing an ordered set as the intersection of super greedy linear extensions

A linear extension [x ₁2<...t] of a finite ordered set P=(P, <) is super greedy if it can be obtained using the following procedure: Choose x ₁ to be a minimal element of P; suppose x ₁,...,x _i have been chosen; define p(x) to be the largest ji such that x _jj exists and 0 otherwise; choose x _i+1 to be a minimal element of P-{ x ₁,...,x _i} which maximizes p. Every finite ordered set P can be represented as the intersection of a family of super greedy linear extensions, called a super greedy realizer of P. The super greedy dimension of P is the minimum cardinality of a super greedy realizer of P. Best possible upper bounds for the super greedy dimension of P are derived in terms of |P-A| and width (P-A), where A is a maximal antichain.Research supported in part by NSF grant IPS-80110451.Research supported in part by ONR grant N00014-85K-0494 and NSERC grants 69-3378, 69-0259, and 69-1325.Research supported in part by NSF grant DMS-8401281.     

Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

Bessel identities in the waldspurger correspondence over the real numbers

We prove certain identities between Bessel functions attached to irreducible unitary representations ofPGL ₂(R) and Bessel functions attached to irreducible unitary representations of the double cover ofSL ₂(R). These identities give a correspondence between such representations which turns out to be the Waldspurger correspondence. In the process we prove several regularity theorems for Bessel distributions which appear in the relative trace formula. In the heart of the proof lies a classical result of Weber and Hardy on a Fourier transform of classical Bessel functions. This paper constitutes the local (real) spectral theory of the relative trace formula for the Waldspurger correspondence for which the global part was developed by Jacquet. Research of first author was partially supported by NSF grant DMS-0070762. Research of second author was partially supported by NSF grant DMS-9729992 and DMS 9971003.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Towards a characterization of generalized twisted field planes

In this work we study semifield planes of orderq ⁿ(q=p ^r ,p prime) with a collineation whose order is ap-primitive divisor ofq ⁿ–1.Research supported in part by NSF Grant No. DMS-9107372Research supported in part by NSF grants RII-9014056, component IV of the EPSCoR of Puerto Rico grant and ARO grant for Cornell MSI.     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

Involution codimensions and trace codimensions of matrices are asymptotically equal

We calculate the asymptotic growth oft _n (M _p (F),*) andc _n (M _p (F),*), the trace and ordinary *-codimensions ofp×p matrices with involution. To do this we first calculate the asymptotic growth oft _n and then show thatc _n ⋍t _n . In memory of Shimshon Amitsur, our teacher and our friend Work supported by NSF grant DMS 9303230. The first author would also like to thank Bar-Ilan University and The Hebrew University of Jerusalem for their kind hospitality during his sabbatical year. Work supported by NSF grant DMS 910488     

The cotype constant and an almost euclidean decomposition for finite-dimensional normed spaces

Every 2n-dimensional normed spaceE contains twon-dimensional subspacesE ₁ andE ₂ which are orthogonal with respect to the inner product induced by the John ellipsoid ofE and which satisfyd(E _i, l ₂ ⁿ )≦f(K ₂(E)), wheref(K ₂(E)) is some number that depends only on the cotype constant ofE, denotedK ₂(E). Supported in part by NSF grant DMS 8401906.     

Spanning trees and a conjecture of Kontsevich

Kontsevich conjectured that the number of zeros over the fieldF _q of a certain polynomialQ _G associated with the spanning trees of a graphG is a polynomial function ofq. We show the connection between this conjecture, the Matrix-Tree Theorem, and orthogonal geometry. We verify the conjecture in certain cases, such as the complete graph, and discuss some modifications and extensions.Partially supported by NSF grant #DMS-9743966.     

On the spanning trees of weighted graphs

Given a weighted graph, letW ₁,W ₂,W ₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW ₁ is at mostk–1 edge swaps away from some spanning tree of weightW _k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW _k .This work was supported in part by a grant from the AT&T foundation and NSF grant DCR-8351757.Primarily supported by a 1967 Science and Engineering Scholarship from the Natural Sciences and Engineering Research Council of Canada.     

Maximal Collections of Intersecting Arithmetic Progressions

Let N _t (k) be the maximum number of k-term arithmetic progressions of real numbers, any two of which have t points in common. We determine N ₂(k) for prime k and all large k, and give upper and lower bounds for N _t (k) when t 3.* Research supported in part by NSF grant DMS-0070618.     

On closures of orbits and arithmetic of quaternions

ForG=PGL₂(ℚ _p )×PGL₂ ℚ we study the closures of orbits under the maximal split Cartan subgroup ofG in homogeneous spacesΓ\G. We show that if a closure of an orbit contains a closed orbit then the orbit is either dense or closed. We show the relation of this to divisibility properties of integral quaternions and other lattices. Sponsored in part by the Edmund Landau Center for Research in Mathematical Analysis supported by the Minerva Foundation (Germany). Research at MSRI supported by NSF grant DMS8505550.     

Strong consistency of density estimation by orthogonal series methods for dependent variables with applications

Among several widely use methods of nonparametric density estimation is the technique of orthogonal series advocated by several authors. For such estimate when the observations are assumed to have been taken from strong mixing sequence in the sense of Rosenblatt [7] we study strong consistency by developing probability inequality for bounded strongly mixing random variables. The results obtained are then applied to two estimates of the functional Δ(f)=∫f ² (x)dx were strong consistency is established. One of the suggested two estimates of Δ(f) was recently studied by Schuler and Wolff [8] in the case of independent and identically distributed observations where they established consistency in the second mean of the estimate. Research supported in part by the National Research Council of Canada and in part by McMaster University Research Board. Now at Memphis State University, Memphis, Tennessee 38152, U.S.A.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

Data compression and histograms

Summary In this paper, the relationship between code length and the selection of the number of bins for a histogram density is considered for a sequence of iid observations on [0,1]. First, we use a shortest code length criterion to select the number of bins for a histogram. A uniform almost sure asymptotic expansion for the code length is given and it is used to prove the asymptotic optimality of the selection rule. In addition, the selection rule is consistent if the true density is uniform [0,1]. Secondly, we deal with the problem: what is the best achievable average code length with underlying density functionf? Minimax lower bounds are derived for the average code length over certain smooth classes of underlying densitiesf. For the smooth class with bounded first derivatives, the rate in the lower bound is shown to be achieved by a code based on a sequence of histograms whose number of bins is changed predictively. Moreover, this best code can be modified to ensure that the almost sure version of the code length has asymptotically the same behavior as its expected value, i.e., the average code length.Research supported in part by NSF grant DMS-8701426Research supported in part by NSF grant DMS-8802378     

Universal non-completely-continuous operators

A bounded linear operator between Banach spaces is calledcompletely continuous if it carries weakly convergent sequences into norm convergent sequences. Isolated is a universal operator for the class of non-completely-continuous operators fromL ₁ into an arbitrary Banach space, namely, the operator fromL ₁ into ⊆_∞ defined byT ₀(f) = (∫r _n f d μ) _n>-0, wherer _n is thenth Rademacher function. It is also shown that there does not exist a universal operator for the class of non-completely-continuous operators between two arbitrary Banach spaces. The proof uses the factorization theorem for weakly compact operators and a Tsirelson-like space. Supported in part by NSF grant DMS-9306460. Participant, NSF Workshop in Linear Analysis & Probability, Texas A&M University (supported in part by NSF grant DMS-9311902). Supported in part by NSF grant DMS-9003550.