New star discrepancy bounds for (t,m,s)-nets and (t,s)-sequences

In this paper, we derive new general upper bounds on the star discrepancy of $(t,m,s)$ -nets and $(t,s)$ -sequences. These kinds of point sets are among the most widely used in quasi-Monte Carlo methods for numerical integration. By our new results, we improve on previous discrepancy bounds and prove a conjecture stated by the second author in an earlier paper.     

A combinatorial characterization of (t,m,s)-nets in base b

We consider (t,m,s)-nets in base b, which were introduced by Niederreiter in 1987. These nets are highly uniform point distributions in s-dimensional unit cubes and have applications in the theory of numerical integration and pseudorandom number generation. A central question in their study is the determination of the parameter values for which these nets exist. Niederreiter has given several methods for their construction, all of which are based on a general construction principle from his 1987 paper. We define a new family of combinatorial objects, the so-called “generalized orthogonal arrays,” and then discuss a combinatorial characterization of (t.m.s)-nets in base b in terms of these generalized orthogonal arrays. Using this characterization, we describe a new method for constructing (t.m.s)-nets in base b that is not based on the aforementioned construction principle. This method gives rise to some very general conditions on the parameters (involving a link with the theory of orthogonal arrays) that are sufficient to ensure the existence of a (t.m.s)-net in base b. In this way we construct many nets that are new. © 1996 John Wiley & Sons, Inc.     

On the discrepancy of (0,1)-sequences

We give bounds for the L^p-discrepancy, , of the van der Corput sequence in base 2. Further, we give a best possible upper bound for the star discrepancy of (0,1)-sequences and show that this bound is attained for the van der Corput sequence. Finally, we give a (0,1)-sequence with essentially smaller star discrepancy than for the van der Corput sequence.     

On the weighted dyadic diaphony of digital (t,s)-sequences

In this note, we present results on the weighted dyadic diaphony of digital (t, s)-sequences over ℤ₂. These results are closely linked to the worst-case error for quasi-Monte Carlo integration in certain spaces of functions. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A construction of low-discrepancy sequences involving finite-row digital (t,s)-sequences

This paper introduces a construction principle for generating matrices of digital sequences over a finite field $\mathbb{F }_q$ , which is based on sequences of polynomials and their representations in terms of powers of nonconstant polynomials. For the most basic polynomial sequence, $(x^r)_{r\ge 0}$ , the representations in terms of powers of linear polynomials yield, within this construction principle, the Pascal matrices, which consist of binomial coefficients and were earlier introduced by Faure for finite prime fields and by Niederreiter for finite field extensions. Generally, for binomial type sequences of polynomials an interesting relation between the generating matrices is worked out, and further examples of generating matrices are given, which contain combinatorial magnitudes as, e.g., binomial coefficients, Stirling numbers of the first kind, Stirling numbers of the second kind, and Bell numbers. Moreover, within this construction principle, explicit constructions of finite-row generating matrices of digital $(t,s)$ -sequences are presented, which were so far only known for $t$ equal to $0$ .     

Tight upper bounds for the discrepancy of half-spaces

We show that the discrepancy of anyn-point setP in the Euclideand-space with respect to half-spaces is bounded byC _d n ^1/2−1/2d , that is, a mapping χ:P→{−1,1} exists such that, for any half-space γ, γ, |Σ _p∈P⋂γ χ(p)|≤C _d n ^1/2-1/2d . In fact, the result holds for arbitrary set systems as long as theprimal shatter function isO(m ^d ). This matches known lower bounds, improving previous upper bounds by a factor. Part of this research was done at the Third Israeli Computational Geometry Workshop in Ramot and during a visit at Tel Aviv University in December 1993. Also supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167.     

Construction of hjelmslev planes from (t,k)-nets

A (t, k)-net is an abstract generalization of the incidence structures which occur as the point and line neighborhoods of a finite Hjelmslev plane. A (t, k)-net contains ‘substructures’ which are nets of ordert and degreek. Every (t, r) Hjelmslev plane (brieflyH-plane) can be constructed from a suitable collection of (t, r+1)- and (t, r)-nets. A (t, r)H-plane or (t, k)-net is called extremal provided: each two points which are joined by more than two lines are joined by preciselyt lines and dually. IfB is a ‘properly’ extremal (t, r)H-plane (means both 2 andt≠2 occur among the joining numbers), thent is even; andr=2 orr=1+(t/2). All the 3-uniform [J. Combinat. Theory 9, 267–288 (1970, this Zbl.204, 210)] (4, 2)H-planes are examples. Two further examples are constructed in the paper: an (8, 2) translationH-planeC and an (8, 2) projectiveH-planeD, none of whose affineH-planes are translationH-planes. All point neighborhoods fromC andD and all line neighborhoods fromD are isomorphic to a give (8, 3)-netE;E is constructed by considering the subspaces of a 64-point symplectic geometry overZ ₂.E is also used to answer (affirmatively) the question of the existence of proper fairly near affineH-planes [J. Combinat. Theory 16A, 34–50 (1974)].     

Star discrepancy estimates for digital (t, m, 2)-nets and digital (t, 2) -sequences over Z2

Summary We prove upper bounds on the star discrepancy of digital (t, m, 2)-nets and (t, 2)-sequences over Z₂. The main tool is a decomposition lemma for digital (t, m, 2)-nets, which states that every digital (t, m, 2)-net is just the union of 2^tdigitally shifted digital (0, m - t, 2)-nets. Using this result we generalize upper bounds on the star discrepancy of digital (0, m, 2) -nets and (0, 2) -sequences.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

Finite Dimensional Lie Superalgebras W(m,n,t) and S(m,n,t) of Cartan Type

设Ｌ＝Ｗ或Ｓ，Ｆ是特征数大于２的域．本文证明了Ｆ上的有限维单李超代数Ｌ（ｍ，ｎ，ｔ）的自然滤过是不变的．进而得出了Ｌ（ｍ，ｎ，ｔ）与Ｌ（ｍ′，ｎ′，ｔ′）同构的充要条件是ｍ＝ｍ′，ｎ＝ｎ′和ｔｉ＝τ（ｔ′ｉ），ｉ＝１，２，…，ｍ，这里τ是｛１，２，…，ｍ｝的一个置换．     

Improved upper and lower bounds for the spectral radius of digraphs

Let G be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius ρ(G) of G is the largest eigenvalue of its adjacency matrix. In this paper, sharp upper and lower bounds on ρ(G) are given. We show that some known bounds can be obtained from our bounds.