An Algorithm to Construct <Emphasis Type="BoldItalic">k</Emphasis>-Regular <Emphasis Type="BoldItalic">k</Emphasis>-Connected Graphs with the Maximum <Emphasis Type="BoldItalic">k</Emphasis>-Diameter

 Let f(2m,k) be the Maximum k-diameter of k-regular k-connected graphs on 2m vertices. In this paper we give an algorithm and prove that we can construct k-regular k-connected graphs on 2m vertices with the maximum k-diameter using it. We also prove some known results about f(2m,k) and verify that we can get some unknown values of f(2m,k) by our algorithm. Received: December 1, 2000 Final version received: March 12, 2002 Acknowledgments. We thank the referee for many useful suggestions.     

A Note on Disconnected Weakly k-Homogeneous Graphs

 A graph is weakly k-homogeneous if whenever two induced subgraphs on k vertices are isomorphic, then some automorphism of this graph sends one induced subgraph to the other. In this note, we characterize weakly k-homogeneous graphs with certain given number of isolated vertices and given number of nontrivial components. As byproduct, all disconnected weakly k-homogeneous graphs are determined for k=2 and k=3. Received: October, 2001 Final version received: October 9, 2002 Acknowledgment. The authors wish to thank the referee for his invaluable remarks.     

Simple Constructions of Almost k-wise Independent Random Variables

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/?), where ? is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ? < 1/(k log n)). An additional advantage of our constructions is their simplicity.     

Families of Graphs Closed Under Taking Powers

 This paper gives simple proofs for “G ^k ∈? implies G ^{k +1}∈?” when ? is the family of all interval graphs, all proper interval graphs, all cocomparability graphs, or all m-trapezoid graphs. Received: November 21, 1997 Final version received: October 5, 1998     

Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

Measure-valued limits of interacting particle systems with <Emphasis Type="Italic">k</Emphasis>-nary interactions

 Results on existence, uniqueness, non-explosion and stochastic monotonicity are obtained for one-dimensional Markov processes having non-local pseudo-differential generators with symbols of polynomial growth. It is proven that the processes of this kind can be obtained as the limits of random evolutions of systems of identical indistinguishable particles with k-nary interaction. Received: 24 May 2002 / Revised version: 19 February 2003 / Published online: 12 May 2003 Mathematics Subject Classification (2000): 60K35, 60J75, 60J80 Key words or phrases: Interacting particles – k-nary interaction – Measure-valued processes – One-dimensional Feller processes with polynomially growing symbols – Duality – Stochastic monotonicity – Heat kernel     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

Linear Arboricity and Linear k-Arboricity of Regular Graphs

 We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs. Received: December 21, 1998 Final version received: July 26, 1999     

Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

Longest Cycles in Almost Claw-Free Graphs

Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every 2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li. Received: September 17, 1996 Revised: September 22, 1998     

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

On the Fractional Intersection Number of a Graph

 An intersection representation of a graph G is a function f:V(G)→2^S (where S is any set) with the property that uv∈E(G) if and only if f(u)∩f(v)≠∅. The size of the representation is |S|. The intersection number of G is the smallest size of an intersection representation of G. The intersection number can be expressed as an integer program, and the value of the linear relaxation of that program gives the fractional intersection number. This is in consonance with fractional versions of other graph invariants such as matching number, chromatic number, edge chromatic number, etc.  We examine cases where the fractional and ordinary intersection numbers are the same (interval and chordal graphs), as well as cases where they are wildly different (complete multipartite graphs). We find the fractional intersection number of almost all graphs by considering random graphs. Received: July 1, 1996 Revised: August 11, 1997     

(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. Received: December 16, 1996 / Revised: September 17, 1997     

Edge Maximal Non-Bipartite Graphs Without Odd Cycles of Prescribed Lengths

 Let ?(n;3,5,…,2k+1) denote the class of non-bipartite graphs on n vertices having no odd cycle of length ≤2k+1. We prove that for every G∈?(n;3,5,…,2k+1) and characterize the extremal graphs. We also study the subclass ℋ(n;3,5,…,2k+1) consisting of the hamiltonian members of ?(n;3,5,…, 2k+1). For this subclass the above upper bound holds for odd n. For even n we establish the following sharp upper bound:

Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

Evasion and prediction

 Say that a function π:n ^<ω →n (henceforth called a predictor) k-constantly predicts a real xn ^ω if for almost all intervals I of length k, there is iI such that x(i)=π(x↾i). We study the k-constant prediction number v _n ^const (k), that is, the size of the least family of predictors needed to k-constantly predict all reals, for different values of n and k, and investigate their relationship. Received: 27 June 2001 / Revised version: 10 September 2001 / Published online: 10 October 2002 RID="*" ID="*" Supported by Grant–in–Aid for Scientific Research (C)(2)12640124, Japan Society for the Promotion of Science RID="†" ID="†" Supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 762     

Properties of Edge-Tough Graphs

 In [6] the author defined a new property of graphs namely the edge-toughness. It was proved in [6] that a 2t-tough graph is always t-edge-tough. It is proved in the present paper that this is not true for (2t−ε)-tough graphs if t is a positive integer. A result of Enomoto et al. in [5] implies that every 2-tough graph has a 2-factor. In the present paper it is proved that every 1-edge-tough graph has a 2-factor. This is a sharpening of the previous statement. Received: July 10, 1996 Revised: March 4, 1998     

The speed of biased random walk on percolation clusters

 We consider biased random walk on supercritical percolation clusters in ℤ². We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random walk has speed zero, while if the bias is small enough, the speed of the random walk is positive. Received: 20 November 2002 / Revised version: 17 January 2003 Published online: 15 April 2003 Research supported by Microsoft Research graduate fellowship. Research partially supported by the DFG under grant SPP 1033. Research partially supported by NSF grant #DMS-0104073 and by a Miller Professorship at UC Berkeley. Mathematics Subject Classification (2000): 60K37; 60K35; 60G50 Key words or phrases: Percolation – Random walk     

Vertex Covers by Edge Disjoint Cliques

Dedicated to the memory of Paul Erdős Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying 1.  , for all i = 1, ..., r, 2.  , 3.  , for all , and 4.  each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs. Received October 31, 1999 RID="*" ID="*" Supported in part by NSF grant DMS-9627408. RID="†" ID="†" Supported in part by NSF grant CCR-9530974. RID="‡" ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation. RID="§" ID="§" Supported in part by NSF grant DMS-9970622.     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.