List Ramsey numbers

We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For $?$‐uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well known that the Ramsey number is superexponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques.     

Wiener Chaos Approach to Optimal Prediction

The chaos expansion of a general non-linear function of a Gaussian stationary increment process conditioned on its past realizations is derived. This work combines the Wiener chaos expansion approach to study the dynamics of a stochastic system with the classical problem of the prediction of a Gaussian process based on a realization of its past. This is done by considering special bases for the Gaussian space 𝒢 generated by the process, which allows us to obtain an orthogonal basis for the Fock space of 𝒢 such that each basis element is either measurable or independent with respect to the given samples. This allows us to easily derive the chaos expansion of a random variable conditioned on part of the sample path. We provide a general method for the construction of such basis when the underlying process is Gaussian with stationary increment. We evaluate the basis elements in the case of the fractional Brownian motion, which leads to a prediction formula for this process.     

Poisson approximation for non-backtracking random walks

Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun’s sieve with some extensions of the ideas in [3]. Let N _t denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, N _t /n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then N _t /n is typically 1+o(1)/et! niformly on all t ≤ (1 − o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.     

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

Tracing a single user

Let g(n,r) be the maximum possible cardinality of a family of subsets of {1,2,…,n} so that given a union of at most r members of , one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that , thus solving a problem of Csűrös and Ruszinkó.     

A hybrid biocathode: surface display of O2-reducing enzymes for microbial fuel cell applications

Laccase and bilirubin oxidase were successfully displayed on the surface of yeast cells. Subsequently, these modified yeast cells were used in the cathode compartment of a microbial fuel cell. The performance of the fuel cells is compared.     

On the Complexity of Arrangements of Circles in the Plane

Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement). Received June 26, 2000, and in revised form January 30, 2001. Online publication October 5, 2001.