Almost Covers Of 2-Arc Transitive Graphs

Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case K _v+1 is covered by results of Gardiner and Praeger. We consider here the general case where K _v+1, and prove that, for some even integer n 4, is a near n-gonal graph with respect to a certain G-orbit on n-cycles of . Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .)     

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.     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.     

Imperfect and Nonideal Clutters: A Common Approach

We prove three theorems. First, Lovászs theorem about minimal imperfect clutters, including also Padbergs corollaries. Second, Lehmans result on minimal nonideal clutters. Third, a common generalization of these two. The endeavor of working out a common denominator for Lovászs and Lehmans theorems leads, besides the common generalization, to a better understanding and simple polyhedral proofs of both.* Visiting of the French Ministry of Research and Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April 1996.     

Local Tree-Width,Excluded Minors,and Approximation Algorithms

The local tree-width of a graph G=(V,E) is the function ltw^G : that associates with every r the maximal tree-width of an r-neighborhood in G. Our main grapht heoretic result is a decomposition theorem for graphs with excluded minors, which says that such graphs can be decomposed into trees of graphs of almost bounded local tree-width.As an application of this theorem, we show that a number of combinatorial optimization problems, suchas Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.     

Transposition generation of alternating permutations

A permutation _{1 2}... _n is alternating if ₁< ₂> ₃< ₄.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.     

Sharp parameter ranges in the uniform anti-maximum principle for second-order ordinary differential operators

We consider the equation (pu)-qu+wu = f in (0,1) subject to homogenous boundary conditions at x = 0 and x = 1, e.g., u(0) = u(1) = 0. Let ₁ be the first eigenvalue of the corresponding Sturm-Liouville problem. If f 0 but 0 then it is known that there exists > 0 (independent on f) such that for (₁, ₁ + ] any solution u must be negative. This so-called uniform anti-maximum principle (UAMP) goes back to Clément, Peletier [4]. In this paper we establish the sharp values of for which (UAMP) holds. The same phenomenon, including sharp values of , can be shown for the radially symmetric p-Laplacian on balls and annuli in ⁿ provided 1 n < p. The results are illustrated by explicitly computed examples.     

On equivalence of rearrangements of the Haar system in dyadic Hardy and BMO spaces

H={h ₁,I } — , . : , I ¦(I)¦=¦I¦, ¦I¦ — I. H H ={h _(I),I} . , , . L ^p .

---

---

Dedicated to Professor B. Szökefalvi-Nagy on his 75th birthday

---

This research was supported in part by MTA-NSF Grants INT-8400708 and 8620153.     

On convergence of function series

, a _n f _n (x) . .     

Thep-adic differential-integral type operator

, p- , , , , , , . —p- - — , . , , .. , .     

Spectral pairs in cartesian coordinates

Let ^d have finite positive Lebesgue measure, and let () be the corresponding Hilbert space of -functions on . We shall consider the exponential functionse on given bye (x)=e ^i2·x . If these functions form an orthogonal basis for (), when ranges over some subset in ^d , then we say that (, ) is a spectral pair, and that is a spectrum. We conjecture that (, ) is a spectral pair if and only if the translates of some set by the vectors of tile ^d. In the special case of =I^d, the d-dimensional unit cube, we prove this conjecture, with =I^d, for d3, describing all the tilings by I^d, and for all d when is a discrete periodic set. In an appendix we generalize the notion of spectral pair to measures on a locally compact abelian group and its dual.Acknowledgements and Notes, Work supported by the National Science Foundation.Dedicated to the memory of Irving E. Segal     

Rate of approximation by rectangular partial sums of double orthogonal series

( ) . .

---

---

Dedicated to Professor K. Tandori on his seventieth birthday

---

This research was supported in part by Grant # K41 100 of the Joint Fund of the Government of Ukraine and the International Science Foundation.     

Оъ одной Задаче из Теории Процессов Размножения и Гибели

. [4].      

Fast-decaying potentials on the finite-gap background and the\bar \partial - problem on the Riemann surfaces

The direct and the inverse scattering problems for the heat-conductivity operator are studied for the following class of potentials:u(x,y)=u _o (x,y)+u ₁(x,y), whereu _o (x,y) is a nonsingular real finite-gap potential andu ₁(x,y) decays sufficiently fast asx ²+y². We show that the scattering data for such potentials is the data on the Riemann surface corresponding to the potentialu _o (x,y). The scattering data corresponding to real potentials is characterized and it is proved that the inverse problem corresponding to such data has a unique nonsingular solution without the small norm assumption. Analogs of these results for the fixed negative energy scattering problem for the two-dimensional time-independent Schrödinger operator are obtained.L. D. Landau Institute for Theoretical Physics, Kosygina 2, GSP-1, Moscow 177940, Russia. E-mail: pgg@cpd.landau.free.net. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 99, No. 2, pp. 300–308, May, 1994.     

On contiguity of probability measures corresponding to semimartingales

, (ⁿ), - (P ⁿ ), P ⁿ (A ⁿ )>0P ⁿ (A ⁿ )0,n. [15] - , . , P ⁿ P ⁿ T ⁿ T ⁿ .     

On an application of infinitely divisible distributions to quadrature problems

— - , .     

On power series with positive coefficients

M. . , . , ^p () (). , , .     

Balanced Incomplete Block Designs with Block Size 7

The object of this paper is the construction of balanced incomplete block designs with k=7. This paper continues the work begun by Hanani, who solved the construction problem for designs with a block size of 7, and with =6, 7, 21 and 42. The construction problem is solved here for designs with > 2 except for v=253, = 4,5 ; also for = 2, the number of unconstructed designs is reduced to 9 (1 nonexistent, 8 unknown).     

On graphs that can be oriented as diagrams of ordered sets

We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each 1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called -good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers , especially for x ₂. There exist graphs that satisfy these inequalities for =2 but are not covering graphs. We show also that x ₂ cannot be bounded by a function of x=x ₁. A construction of Neetil and Rödl is used to show that x ₂ is not bounded by a function of the girth.     

Some remarks on the approximation in the strong sense

. , , , , . , . , , .

---

---

On the 70th birthday of Professor S. M. Nikol'skii