On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

Some Ramsey-Turán type results for hypergraphs

To everyk-graphG let(G) be the minimal real number such that for every>0 andn>n ₀(,G) everyk-graphH withn vertices and more than (+) ( ) edges contains a copy ofG. The real number (G) is defined in the same way adding the constraint that all independent sets of vertices inH have sizeo(n). Answering a problem of Erds and Sós it is shown that there exist infinitely manyk-graphs with 0<(G)<(G) for everyk3. It is worth noting that we were unable to find a singleG with the above property.This paper was written while the authors were visiting AT&T Bell Laboratories, Murray Hill, NJ 07974.     

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     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.     

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.     

Weight functions on the Kneser graph and the solution of an intersection problem of Sali

LetX, Y be finite sets and suppose thatF is a collection of pairs of sets (F, G),FX,GY satisfying |FF|s, |GG|t and |FF|+|GG|s+t+1 for all (F, G),F, GF. Extending a result of Sali, we determine the maximum ofF.     

On a problem of Erdős and Lovász: Random lines in a projective plane

Letn(k) be the least size of an intersecting family ofk-sets with cover numberk, and let _k denote any projective plane of orderk–1.Theorem There is a constant A such that ifH is a random set ofm Aklogk lines from _k then P_r(H<)0(k).Corollary If there exists a _k thenn(k)=O(klogk). These statements were conjectured by P. Erds and L. Lovász in 1973.Supported in part by NSF-DMS87-83558 and AFOSR grants 89-0066, 89-0512 and 90-0008     

Two Tree-Width-Like Graph Invariants

In this paper we introduce two tree-width-like graph invariants. The first graph invariant, which we denote by ⁼(G), is defined in terms of positive semi-definite matrices and is similar to the graph invariant (G), introduced by Colin de Verdière in [J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph invariant, which we denote by (G), is defined in terms of a certain connected subgraph property and is similar to (G), introduced by van der Holst, Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304, 1995]. We give some theorems on the behaviour of these invariants under certain transformations. We show that ⁼(G)=(G) for any graph G with ⁼(G)4, and we give minimal forbidden minor characterizations for the graphs satisfying ⁼(G)k for k=1,2,3,4.This paper is extracted from two chapters of [7]. This work was done while the author was at the Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

On the commutator subgroup of a nonconnected central group

In this paperG denotes a central topologicalT ₂-group—G/Z(G) compact, whereZ(G) is the center. There are some results concerning compactness of the commutator subgroupG; in general (G)^– is compact ([3]), but not necessarilyG ([7]). If in additionG is a Lie group or ifG is connected,G is compact ([6], [5]). The purpose of this paper is to show, that if the componentG ₀ of the identity is open,G must be compact, and to give an example of a compact group with (G/G ₀) compact, whileG is not compact.Dedicated to Prof. R. Inzinger on his 70th birthday     

Asymptotic analysis of the exponential penalty trajectory in linear programming

We consider the linear program min{cx: Axb} and the associated exponential penalty functionf _r(x) = cx + rexp[(A _ix – b_i)/r]. Forr close to 0, the unconstrained minimizerx(r) off _r admits an asymptotic expansion of the formx(r) = x ^* + rd^* + (r) wherex ^* is a particular optimal solution of the linear program and the error term(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to : the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.Corresponding author. Both authors partially supported by FONDECYT.     

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.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

On the congruence problem in infinite dimensional sesquilinear spaces

If two subspaces V and V of a sesquilinear space E are congruent (i.e., there is an isometry : E E with (V)=V) then their corresponding quadratic lattices V(V, E) and V(V, E) are isomorphic. It is shown that the converse holds for important types of sesquilinear spaces E, provided that dim(E) ₃. However, the converse generally fails if dim(E) ₃.     

On meromorphic solutions of algebraic differential equations in angular domains

We obtain asymptotic estimates of meromorphic solutions to the differential equationP _n (z, , )=P _n–1 (z, , ,..., ^(m) ) in the angular domain P={z: arg z · }. Here P_n(z, w, w) is a polynomial in all variables, and of degree n with respect to w and w; P_n–1(z, w, w, ..., w^(m)) is a polynomial in all variables, and of degree n –1 with respect to w, w, ..., w^(m) In the particular case, when the solutions are entire functions, these estimates are more precise than the known estimates that are obtained by using the method of Wiman-Valiron, which cannot be applied to meromorphic solutions in the domain P.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 4, pp. 514–523, April, 1992.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

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.     

On independent statistical decision problems and products of diffusions

Summary LetZ _t be a null recurrent diffusion on ^p with generatorG=(1/r)·(r ) for smooth positiver. This note constructs an independent recurrent diffusionZ _ton ¹ such that (Z _t, Z_t)is transient in ^p+1. This resolves negatively an old question in simultaneous estimation: Is there an admissible but not Bayes estimator(X) of the mean of a multivariate normal distribution for quadratic loss with the property: for every admissible (X), whereX is normal and independent ofX, (, ) remains admissible in the combined problem obtained by summing the component losses?Work supported by NSF at Mathematical Sciences Research Institute, Berkeley     

Ramsey families which exclude a graph

For graphsA andB the relationA(B) _r ¹ means that for everyr-coloring of the vertices ofA there is a monochromatic copy ofB inA. Forb (G) is the family of graphs which do not embedG. A familyof graphs is Ramsey if for all graphsBthere is a graphAsuch thatA(B) _r ¹ . The only graphsG for which it is not known whether Forb (G) is Ramsey are graphs which have a cutpoint adjacent to every other vertex except one. In this paper we prove for a large subclass of those graphsG, that Forb (G) does not have the Ramsey property.This research has been supported in part by NSERC grant 69-1325.     

Mortality of iterated Gallai graphs

For a finite or infinite graphG, theGallai graph (G) ofG is defined as the graph whose vertex set is the edge setE(G) ofG; two distinct edges ofG are adjacent in (G) if they are incident but do not span a triangle inG. For any positive integert, thetth iterated Gallai graph ^t (G) ofG is defined by ( ^t–1(G)), where ⁰(G):=G. A graph is said to beGallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways.     

Interval stability and interval covering property in finite posets

Given a finite ranked posetP, let (P) be the maximum size of a subset ofP such that no two elements of it belong simultaneously to some interval ofP and let (P) be the minimum number of intervals covering all elements ofP. We say thatP has the strong interval stability property (resp. the strong interval covering property) if for each subposetP induced by consecutive levels ofP, i.e.,P=P _(l)...P _(u), one has (P)=max{|P _(l)|, |P _(u)|} (resp. (P)=max{|P _(l)|, |P _(u)|}).We prove these properties for several classes of posets and discuss some general facts concerning the numbers (P) and (P), e.g., NP-completeness and min-max relations.