Universally signable graphs

In a graph, a chordless cycle of length greater than three is called a hole. Let be a {0, 1} vector whose entries are in one-to-one correspondence with the holes of a graphG. We characterize graphs for which, for all choices of the vector , we can pick a subsetF of the edge set ofG such that |F H| H (mod 2), for all holesH ofG and |F T| 1 for all trianglesT ofG. We call these graphsuniversally signable. The subsetF of edges is said to be labelledodd. All other edges are said to be labelledeven. Clearly graphs with no holes (triangulated graphs) are universally signable with a labelling of odd on all edges, for all choices of the vector . We give a decomposition theorem which leads to a good characterization of graphs that are universally signable. This is a generalization of a theorem due to Hajnal and Surányi [3] for triangulated graphs.This work was supported in part by NSF grants DMI-9424348 DMS-9509581 and ONR grant N00014-89-J-1063. Ajai Kapoor was also supported by a grant from Gruppo Nazionale Delle Ricerche-CNR. We also acknowledge the support of Laboratoire ARTEMIS, Université Joseph Fourier, Grenoble.     

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.     

Infinite partition regular matrices

We consider infinite matrices with entries from (and only finitely many nonzero entries on any row). A matrixA is partition regular over provided that, whenever the set of positive integers is partitioned into finitely many classes there is a vector with entries in such that all entries ofA lie in the same cell of the partition. We show that, in marked contrast with the situation for finite matrices, there exists a finite partition of no cell of which contains solutions for all partition regular matrices and determine which of our pairs of matrices must always have solutions in the same cell of a partition.     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

‘Outside’ as a primitive notion in constructive projective geometry

In intuitionistic (or constructive) geometry there are positive counterparts, apart and outside, of the relations = and incident. In this paper it is shown that the relation outside suffices to define incident, apart and equality. The equivalence of the new system with Heyting's system is shown and as a simple corollary one obtains duality for intuitionistic projective geometry.     

Local structure of graphs with λ=μ=2,a 2=4

Several properties of graphs with ==2,a ₂=4 are studied. It is proved that such graphs are locally unions of triangles, hexagons or heptagons. As a consequence, a distance regular graph with intersection array (13,10,7;1,2,7) does not exist.     

Investigation of Haar and Franklin series in Hardy spaces

(L ¹,H) (, ) , ; H — . , , L ¹ . [13] , . , , , .     

Transfer Functions of Regular Linear Systems Part III: Inversions and Duality

We study four transformations which lead from one well-posed linear system to another: time-inversion, flow^-inversion, time-flow-inversion and duality. Time-inversion means reversing the direction of time, flow-inversion means interchanging inputs with outputs, while time-flow-inversion means doing both of the inversions mentioned before. A well-posed linear system is time-invertible if and only if its operator semigroup extends to a group. The system is flow-invertible if and only if its input-output map has a bounded inverse on some (hence, on every) finite time interval [0, ] ( > 0). This is true if and only if the transfer function of has a uniformly bounded inverse on some right half-plane. The system is time-flow-invertible if and only if on some (hence, on every) finite time interval [0, ], the combined operator from the initial state and the input function to the final state and the output function is invertible. This is the case, for example, if the system is conservative, since then is unitary. Time-flow-inversion can sometimes, but not always, be reduced to a combination of time- and flow-inversion. We derive a surprising necessary and sufficient condition for to be time-flow-invertible: its system operator must have a uniformly bounded inverse on some left halfplane. Finally, the duality transformation is always possible.We show by some examples that none of these transformations preserves regularity in general. However, the duality transformation does preserve weak regularity. For all the transformed systems mentioned above, we give formulas for their system operators, transfer functions and, in the regular case and under additional assumptions, for their generating operators.     

Weyl's theorem for operator matrices

Weyl's theorem holds for an operator when the complement in the spectrum of the Weyl spectrum coincides with the isolated points of the spectrum which are eigenvalues of finite multiplicity. By comparison Browder's theorem holds for an operator when the complement in the spectrum of the Weyl spectrum coincides with Riesz points. Weyl's theorem and Browder's theorem are liable to fail for 2×2 operator matrices. In this paper we explore how Weyl's theorem and Browder's theorem survive for 2×2 operator matrices on the Hilbert space.Supported in part by BSRI-97-1420 and KOSEF 94-0701-02-01-3.     

Kanten-kritische graphen mit der zusammenhangszahl 2

A set of vertices of a graph G represents G if each edge of G is incident with at least one vertex of . A graph G is said to be edge-critical if the minimal number of vertices necessary to represent G decreases if any edge of G is omitted. Plummer [5] has given a method to construct an infinite family of edge-critical graphs with connectivity number 2. We use this method to construct a more extensive class of edge-critical graphs with connectivity number 2 and show that all edge-critical graphs with this connectivity number (K₂) can be constructed from smaller edge-critical graphs. Finally we give examples of edge-critical graphs not constructable from smaller ones by this method.     

On cubature formulas on the basis of lattices

Q (.. , L). Q . P(S_r(2)) — 2 (S _r(2) (r — ). , M(P(S _r(m=sup{t(·)t(·)₁:t P(S _r(2)),t 0}. , /4+(1)M(P(S _r(2)))/r ²15/17+(1)(r+). (Q), Q L.     

Identities of an algebra of triangular matrices

This paper deals with the ideals of identities of certain associative algebras over a field F of characteristic zero. An algebra W of matrices of the form ,,,M, where and , are F-algebras with unity and M is a (,)-bimodule, is considered. Under certain natural restrictions on M one obtains the equality of ideals of identities T(W)=T()T(), if [[x₁,x₂], x₃[x₄,x₅]]T().Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 7–27, 1982.     

The quality of the Diophantine approximations found by the Jacobi-Perron algorithm and related algorithms

Given a vector of real numbers=(₁,... _d ) ^d , the Jacobi-Perron algorithm and related algorithms, such as Brun's algorithm and Selmer's algorithm, produce a sequence of (d+1)×(d+1) convergent matrices {C⁽ⁿ⁾():n1} whose rows provide Diophantine approximations to . Such algorithms are specified by two mapsT:[0, 1] ^d [0, 1] ^d and A:[0,1] ^d GL(d+1,), which compute convergent matrices C⁽ⁿ⁾())...A(T())A(). The quality of the Diophantine approximations these algorithms find can be measured in two ways. The best approximation exponent is the upper bound of those values of for which there is some row of the convergent matrices such that for infinitely many values ofn that row of C⁽ⁿ⁾() has . The uniform approximation exponent is the upper bound of those values of such that for all sufficiently large values ofn and all rows of C⁽ⁿ⁾⁽⁾ one has . The paper applies Oseledec's multiplicative ergodic theorem to show that for a large class of such algorithms and take constant values and on a set of Lebesgue measure one. It establishes the formula where are the two largest Lyapunov exponents attached by Oseledec's multiplicative ergodic theorem to the skew-product (T, A,d), whered is aT-invariant measure, absolutely continuous with respect to Lebesgue measure. We conjecture that holds for a large class of such algorithms. These results apply to thed-dimensional Jacobi-Perron algorithm and Selmer's algorithm. We show that; experimental evidence of Baldwin (1992) indicates (nonrigorously) that. We conjecture that holds for alld2.     

Converse results on equiconvergence of interpolating polynomials

, n- n- 1 , . , , ( « ») f .     

On the angular derivative and univalence

f . , , — , A f f(). , , f() 0 . , , ,A , f . , f() - f() . , , . (1976) ( ¦f(z)¦<1) . . (1969) ( ).     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

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.     

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.     

OnK 4-free subgraphs of random graphs

For 0<1 and graphsG andH, writeGH if any -proportion of the edges ofG spans at least one copy ofH inG. As customary, writeK ^r for the complete graph onr vertices. We show that for every fixed real >0 there exists a constantC=C() such that almost every random graphG _n,p withp=p(n)Cn ^–2/5 satisfiesG _{n,p 2/3+} K ⁴. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerningH-free subgraphs of random graphs in the spirit of the Erds-Stone theorem are discussed.The first author was partially supported by FAPESP (Proc. 93/0603-1) and by CNPq (Proc. 300334/93-1 and ProTeM-CC-II Project ProComb). Part of this work was done while the second author was visiting the University of São Paulo, supported by FAPESP (Proc. 94/4276-8). The third author was partially supported by the NSF grant DMS-9401559.     

Subgroups of the full linear group over a semilocal ring

Let be a semilocal ring (a factor ring with respect to the Jacobson-Artin radical) for which the residue field C/m of its center C with respect to each maximal idealmC contains no fewer than seven elements. The structure of subgroups H in the full linear group GL(n, ) containing the group of diagonal matrices is considered. The main theorem: for any subgroup H there is a uniquely determined D-net of ideals such that G()HN(), whereN() is the normalizer of the D-net subgroup . A transparent classification of subgroups GL(n, ) normalizable by diagonal matrices is thus obtained. Further, the factor groupN()/G() is studied.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 75, pp. 32–34, 1978.