Weak hypergraph regularity and linear hypergraphs

We consider conditions which allow the embedding of linear hypergraphs of fixed size. In particular, we prove that any k-uniform hypergraph H of positive uniform density contains all linear k-uniform hypergraphs of a given size. More precisely, we show that for all integers l >= k >= 2 and every d > 0 there exists Q > 0 for which the following holds: if His a sufficiently large k-uniform hypergraph with the property that the density of H induced on every vertex subset of size on is at least d, then H contains every linear k-uniform hypergraph F with l vertices. The main ingredient in the proof of this result is a counting lemma for linear hypergraphs, which establishes that the straightforward extension of graph epsilon-regularity to hypergraphs suffices for counting linear hypergraphs. We also consider some related problems. (C) 2009 Elsevier Inc. All rights reserved.

A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemeredi Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. (C) 2011 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

The 3-colored Ramsey number of even cycles

Denote by R(L, L, L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdos conjectured that when L is the cycle C(n) on n vertices, R(C(n), C(n), C(n)) = 4n - 3 for every odd n > 3. Luczak proved that if n is odd, then R(C(n), C(n), C(n)) = 4n + o(n), as n -> infinity, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdos conjecture for all sufficiently large values of n. Figaj and Luczak determined an asymptotic result for the `complementary` case where the cycles are even: they showed that for even n, we have R(C(n), C(n), C(n)) = 2n + o(n), as n -> infinity. In this paper, we prove that there exists n I such that for every even n >= n(1), R(C(n), C(n), C(n)) = 2n. (C) 2009 Elsevier Inc. All rights reserved.

Weak quasi-randomness for uniform hypergraphs

We study quasi-random properties of k-uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung-Graham-Wilson theorem for quasi-random graphs. Moreover, let K(k) be the complete graph on k vertices and M(k) the line graph of the graph of the k-dimensional hypercube. We will show that the pair of graphs (K(k),M(k)) has the property that if the number of copies of both K(k) and M(k) in another graph G are as expected in the random graph of density d, then G is quasi-random (in the sense of the Chung-Graham-Wilson theorem) with density close to d. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 1-38, 2012

GEVREY SOLVABILITY AND GEVREY REGULARITY IN DIFFERENTIAL COMPLEXES ASSOCIATED TO LOCALLY INTEGRABLE STRUCTURES

In this work we study some properties of the differential complex associated to a locally integrable (involutive) structure acting on forms with Gevrey coefficients. Among other results we prove that, for such complexes, Gevrey solvability follows from smooth solvability under the sole assumption of a regularity condition. As a consequence we obtain the proof of the Gevrey solvability for a first order linear PDE with real-analytic coefficients satisfying the Nirenberg-Treves condition (P).

On the loss of regularity for a class of weakly hyperbolic operators

In this paper we determine bounds for the optimal loss of regularity in the Sobolev scale for a class of weakly hyperbolic operators. (C) 2009 Elsevier Inc. All rights reserved.

A Poincare-Birkhoff-Witt commutator lemma for U-q[gl(m vertical bar n)]

We present and prove in detail a Poincare-Birkhoff-Witt commutator lemma for the quantum superalgebra U-q[gl(m\n)]. (C) 2003 American Institute of Physics.

Green's relations, regularity and abundancy for semigroups of quasi-onto transformations

Let V be an infinite-dimensional vector space and for every infinite cardinal n such that n≤dimV, let AE(V,n) denote the semigroup of all linear transformations of V whose defect is less than n. In 2009, Mendes-Gonçalves and Sullivan studied the ideal structure of AE(V,n). Here, we consider a similarly-defined semigroup AE(X,q) of transformations defined on an infinite set X. Quite surprisingly, the results obtained for sets differ substantially from the results obtained in the linear setting.

Regularity and mass conservation for discrete coagulation-fragmentation equations with diffusion

We present a new a-priori estimate for discrete coagulation fragmentation systems with size-dependent diffusion within a bounded, regular domain confined by homogeneous Neumann boundary conditions. Following from a duality argument, this a-priori estimate provides a global L2 bound on the mass density and was previously used, for instance, in the context of reaction-diffusion equations. In this paper we demonstrate two lines of applications for such an estimate: On the one hand, it enables to simplify parts of the known existence theory and allows to show existence of solutions for generalised models involving collision-induced, quadratic fragmentation terms for which the previous existence theory seems difficult to apply. On the other hand and most prominently, it proves mass conservation (and thus the absence of gelation) for almost all the coagulation coefficients for which mass conservation is known to hold true in the space homogeneous case.

Prescription footwear for severe injuries of foot and ankle: effect on regularity and symmetry of the gait assessed by trunk accelerometry.

After foot and/or ankle fracture, the restoration of optimal gait symmetry is one of the criteria of recovery. Orthotic insoles and orthopaedic shoes improve gait symmetry and regularity by controlling joint motion and improving alignment. The aim of the present study was to assess the effect of prescription footwear on gait quality by using accelerometers attached to the lower back. Sixteen adult patients with persistent disability after ankle and/or foot fractures performed two 30-s walking trials with and without prescription footwear (insoles and stabilizing shoes). Sixteen control subjects were also tested for comparison. The autocorrelation function was computed from the acceleration signal and the first two dominant periods were assessed (d1 and d2). Two parameters were used: (1) Stride Regularity (SR) which expresses the similarity between strides over time (d2), and (2) Stride Symmetry (SS) a ratio (d1/d2) which expresses the left/right similarity of gait independently of repeatability in the successive movements of each limb. In control subjects, SR and SS were 0.86+/-0.05 (correlation coefficient) and 81+/-10%, respectively. In the patient group, the effect of footwear was significant (SR: 0.88+/-0.06 vs. 0.90+/-0.05, SS: 38+/-23% vs. 46+/-27%). Pain was also significantly reduced (-34%). By using a rapid and low-cost method, we objectively quantified gait quality improvement after footwear intervention, concomitant to pain reduction. Substantial inter-patient variability in the footwear outcome was observed. In conclusion, we believe that trunk accelerometry can be a useful tool in the field of gait rehabilitation.

On the existence of doubling measures with certain regularity properties

Given a compact pseudo-metric space, we associate to it upper and lower dimensions, depending only on the pseudo-metric. Then we construct a doubling measure for which the measure of a dilated ball is closely related to these dimensions.

Regularity and counterfactuality in Hume's treatment of causation

Of the several theories of causation current in our days, Hume is said to be the inspiration of two of the most influential and accepted: the regularity theory, first clearly formulated by Thomas Brown in 1822, and the counterfactual theory, proposed by David Lewis in 1973. After a brief outline of the comparative merits and difficulties of these two views, I proceed to examine whether Hume's own treatment of causation actually corresponds to any of them. I will show that his first definition of cause, coupled with his rules by which to judge about causes and effects, contains elements that, properly developed, allow us to address successfully some traditional difficulties of the regularity view of causation, without resorting to the conceptual resources employed in the counterfactual approach. Therefore, we can properly classify Hume as an advocate of the conception of causation as regularity, noting however that his primary goal in his research and definitions of the concept was to provide not so much an analysis of causation as such, but of causation as we apprehend it, in the form of our ability to make causal inferences and refine them to reach the more sophisticated causal reasonings that are required in the theoretical and practical issues of life.

Steady periodic water waves with constant vorticity: regularity and local bifurcation

This paper studies periodic traveling gravity waves at the free surface of water in a flow of constant vorticity over a flat bed. Using conformal mappings the free-boundary problem is transformed into a quasilinear pseudodifferential equation for a periodic function of one variable. The new formulation leads to a regularity result and, by use of bifurcation theory, to the existence of waves of small amplitude even in the presence of stagnation points in the flow.