The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

First order properties of random posets

Let =(n,p) be a binary relation on the set [n]={1, 2, ..., n} such that (i,i) for every i and (i,j) with probability p, independently for each pair i,j [n], where i<j. Define as the transitive closure of and denote poset ([n], ) by R(n, p). We show that for any constant p probability of each first order property of R(n, p) converges as n .     

∑II∑ threshold formulas

A II formula has the form, where eachL is either a variable or a negated variable. In this paper we study the computation of threshold functions by II formulas. By combining the proof of the Fredman-Komlós bound [5, 10] and a counting argument, we show that fork andn large andkn/2, every II formula computing the threshold functionT _k ⁿ has size at least exp . Fork andn large andkn ^2/3, we show that there exist II formulas for computingT _k ⁿ with size at most exp .     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

On the stochastic independence properties of hard-core distributions

A probability measurep on the set of matchings in a graph (or, more generally 2-bounded hypergraph) ishard-core if for some : [0,), the probabilityp(M) ofM is proportional to . We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, withM chosen according to the hard-core distributionp, MP () the matching polytope of , and >0, if the vector ofmarginals, (Pr(AM):A an edge of ), is in (1–) MP (), then the weights (A) are bounded by someA(). This eventually implies, for example, that under the same assumption, with fixed, as the distance betweenA, B tends to infinity.Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]–[13]).Supported in part by NSFThis work forms part of the author's doctoral dissertation [16]; see also [17]. The author gratefully acknowledges NSERC for partial support in the form of a 1967 Science and Engineering Scholarship.     

The Colin de Verdière number and sphere representations of a graph

Colin de Vedière introduced an interesting linear algebraic invariant (G) of graphs. He proved that (G)2 if and only ifG is outerplanar, and (G)3 if and only ifG is planar. We prove that if the complement of a graphG onn nodes is outerplanar, then (G)n–4, and if it is planar, then (G)n–5. We give a full characterization of maximal planar graphs whose complementsG have (G)=n–5. In the opposite direction we show that ifG does not have twin nodes, then (G)n–3 implies that the complement ofG is outerplanar, and (G)n–4 implies that the complement ofG is planar.Our main tools are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks. In particular we show that such sphere representations characterize outerplanar and planar graphs.     

A property of nonlinear elliptic equations when the right-hand side is a measure

LetA(u)=–diva(x, u, Du) be a Leray-Lions operator defined onW ₀ ^1,p () and be a bounded Radon measure. For anyu SOLA (Solution Obtained as Limit of Approximations) ofA(u)= in ,u=0 on , we prove that the truncationsT _k(u) at heightk satisfyA(T _k(u)) A(u) in the weak * topology of measures whenk + .

---

Résumé SoitA(u)=–diva(x, u, Du) un opérateur de Leray-Lions défini surW ₀ ^1,p () et une mesure de Radon bornée. Pour toutu SOLA (Solution Obtenue comme Limite d'Approximations) deA(u)= dans ,u=0 sur , nous démontrons que les troncaturesT _k(u) à la hauteurk vérifientA(T _k(u)) A(u) dans la topologie faible * des mesures quandk + .

     

On computing the number of subgroups of a finite Abelian group

We consider the numberN _A (r) of subgroups of orderp ^r ofA, whereA is a finite Abelianp-group of type =₁,₂,..., _l ()), i.e. the direct sum of cyclic groups of order ⁱⁱ. Formulas for computingN _A (r) are well known. Here we derive a recurrence relation forN _A (r), which enables us to prove a conjecture of P. E. Dyubyuk about congruences betweenN _A (r) and the Gaussian binomial coefficient .     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

Upper bound for transversals of tripartite hypergraphs

We prove 2 7/9v for 3-partite hypergraphs. (This is an improvement of the trivial bound 3v.)     

Smoothness of solutions of a nonlinear ode

Smoothness of aC -functionf is measured by (Carleman) sequence {M _k} ₀ ; we sayfC _M [0, 1] if|f ^(k) (t)|CR ^k M _k,k=0, 1, ... withC, R>0. A typical statement proven in this paper isTHEOREM: Let u, b be two C -functions on [0, 1]such that (a) u=u ²+b, (b) |b ^(k) (t)|CR ^k (k!) , >1,k_–.Then |u^(k)(t)|C₁R^k((k–1)!),k_–.The first author acknowledges the hospitality of Mathematical Research Institute of the Ohio State University during his one month visit there in the spring of 1999     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Black holes on the plane drawn by a Wiener process

Summary We say that the discD()R ², of radius , located around the origin isp-covered in timeT by a Wiener processW(·) if for anyzD() there exists a 0tT such thatW(t) is a point of the disc of radiusp, located aroundz. The supremum of those 's (0) is studied for which,D() isp-covered inT.     

Some properties of the riesz charge associated with a δ-subharmonic function

The first property is a refinement of earlier results of Ch. de la Vallée Poussin, M. Brelot, and A. F. Grishin. Let w=u–v with u, v superharmonic on a suitable harmonic space (for example an open subset of R ⁿ ), and let [w]=[u]–[v] denote the associated Riesz charge. If w0, and if E denotes the set of those points of at which the lim inf of w in thefine topology is 0, then the restriction of [w] to E is 0. Another property states that, if e denotes a polar subset of such that the fine lim inf of |w| at each point of e is finite, then the restriction of [w] to e is 0.     

Über den algorithmischen Nachweis von Ungleichungen I

We shall develop a method to prove inequalities in a unified manner. The idea is as follows: It is quite often possible to find a continuous functional : ⁿ , such that the left- and the right-hand side of a given inequality can be written in the form (u)(v) for suitable points,v=v(u). If one now constructs a map ^{n n} , which is functional increasing (i.e. for each x ⁿ (which is not a fixed point of ) the inequality (x)<((x)) should hold) one specially gets the chain (u)( u))( ²(u))... ⁿ (u)). Under quite general conditions one finds that the sequence { ⁿ (u)} _n converges tov=v(u). As a consequence one obtains the inequality (u)(v).     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

A survey of pseudo (v,k, λ)-designs

This work is an attempt to give a complete survey of all known results about pseudo (v, k, )-designs. In doing this, the author hopes to bring more attention to his conjecture given in Section 6; an affirmative answer to this conjecture would settle completely the existence and construction problem for a pseudo (v, k, )-design in terms of the existence of an appropriate (v, k, )-design.     

Packing directed circuits fractionally

LetG be a digraph, and letk1, such that no fractional packing of directed circuits ofG has value >k, when every vertex is given capacity 1. We prove there is a set ofO (k logk logk) vertices meeting all directed circuits ofG.     

The addition formula for theta functions

Summary In this paper we solve the functional equationx(u + v)(u – v) = f ₁(u)g₁(v) + f₂(u)g₂(v) under the assumption thatx, , f ₁, f₂, g₁, g₂ are complex-valued functions onR ⁿ ,n N arbitrary, and 0 and 0 are continuous. Our main result shows that, apart from degeneracy and some obvious modifications, theta functions of one complex variable are the only continuous solutions of this functional equation.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.