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     

Large induced forests in sparse graphs

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K₄, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001     

Wetting and nonwetting fluid displacements in porous media

The understanding of simple laminar flow in tubes has often been used to interpret the more complicated flow in porous media. A study of the motion of two immiscible liquids in closed tubes with relatively large diameter (> 0.3 cm i.d), was conducted in order to examine the influence of wetting and nonwetting liquids on the flow behavior. The results indicate that the wetting properties of the fluids with regard to the tube wall have a major efffect on the formation and motion of long bubbles. A physically based model was used to predict the velocity and the conditions for no motion of bubbles and drops in tubes. These results were used to interpret the nature of oil and water flow in porous media. Experiments in which the wetting liquid was displaced by the nonwetting, or vice versa, were conducted by injecting the displacing liquid at a constant flux at the center of a two-dimensional chamber saturated with the displaced liquid. The influence of wetting-nonwetting characteristics on the quantity of liquid displaced, the shape of the interface between the two liquids, and the interpretation of the no motion radius in a closed tube to the case of a porous medium are discussed. It would appear that the no motion radius gives a good indication of the minimum width of a nonwetting penetrating finger and the maximum width of nonwetting ganglia left by drainage.     

Randomized large distortion dimension reduction

Consider a random matrix \(H:{\mathbb {R}}^{n}\longrightarrow {\mathbb {R}}^{m}\) . Let \(D\ge 2\) and let \(\{W_l\}_{l=1}^{p}\) be a set of \(k\) -dimensional affine subspaces of \({\mathbb {R}}^{n}\) . We ask what is the probability that for all \(1\le l\le p\) and \(x,y\in W_l\) , $$\begin{aligned} \Vert x-y\Vert _2\le \Vert Hx-Hy\Vert _2\le D\Vert x-y\Vert _2. \end{aligned}$$ We show that for \(m=O\big (k+\frac{\ln {p}}{\ln {D}}\big )\) and a variety of different classes of random matrices \(H\) , which include the class of Gaussian matrices, existence is assured and the probability is very high. The estimate on \(m\) is tight in terms of \(k,p,D\) .     

Additive Patterns in Multiplicative Subgroups

The study of sum and product problems in finite fields motivates the investigation of additive structures in multiplicative subgroups of such fields. A simple known fact is that any multiplicative subgroup of size at least q ^3/4 in the finite field F _q must contain an additive relation x + y = z. Our main result is that there are infinitely many examples of sum-free multiplicative subgroups of size Ω(p ^1/3) in prime fields F _p . More complicated additive relations are studied as well. One representative result is the fact that the elements of any multiplicative subgroup H of size at least q ^3/4+o(1) of F _q can be arranged in a cyclic permutation so that the sum of any pair of consecutive elements in the permutation belongs to H. The proofs combine combinatorial techniques based on the spectral properties of Cayley sum-graphs with tools from algebraic and analytic number theory.     

Counting sum-free sets in abelian groups

In this paper we study sum-free sets of order m in finite abelian groups. We prove a general theorem about independent sets in 3-uniform hypergraphs, which allows us to deduce structural results in the sparse setting from stability results in the dense setting. As a consequence, we determine the typical structure and asymptotic number of sum-free sets of order m in abelian groups G whose order n is divisible by a prime q with q ≡ 2 (mod 3), for every m ? \(C(q)\sqrt {n\log n} \) , thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sumfree subsets of size m are contained in a maximum-size sum-free subset of G. We also give a completely self-contained proof of this statement for abelian groups of even order, which uses spectral methods and a new bound on the number of independent sets of a fixed size in an (n, d, λ)-graph.