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.     

Classes of graphs that exclude a tree and a clique and are not vertex ramsey

A class of graphs is vertex Ramsey if for allH there existsG such that for all partitions of the vertices ofG into two parts, one of the parts contains an induced copy ofH. Forb (T,K) is the class of graphs that induce neitherT norK. LetT(k, r) be the tree with radiusr such that each nonleaf is adjacent tok vertices farther from the root than itself. Gyárfás conjectured that for all treesT and cliquesK, there exists an integerb such that for allG in Forb(T,K), the chromatic number ofG is at mostb. Gyárfás' conjecture implies a weaker conjecture of Sauer that for all treesT and cliquesK, Forb(T,K) is not vertex Ramsey. We use techniques developed for attacking Gyárfás' conjecture to prove that for allq, r and sufficiently largek, Forb(T(k,r),K _q ) is not vertex Ramsey.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

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.     

On the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

Polynomially convex orbits of compact lie groups

LetV be a finite dimensional complex linear space and letG be a compact subgroup of GL(V). We prove that an orbitG, V, is polynomially convex if and only ifG is closed andG is the real form ofG . For every orbitG which is not polynomially convex we construct an analytic annulus or strip inG with the boundary inG. It is also proved that the group of holomorphic automorphisms ofG which commute withG acts transitively on the set of polynomially convexG-orbits. Further, an analog of the Kempf-Ness criterion is obtained and homogeneous spaces of compact Lie groups which admit only polynomially convex equivariant embeddings are characterized.Supported by Federal program Integratsiya, no. 586.Supported by INTAS grant 97/10170.     

A mixed version of Menger's theorem

An(a, b)-n-fan means a union ofn internally disjoint paths. Menger's theorem states that a graphG has an(a, b)-n-fan if and only ifG isn-connected betweena andb. We show thatG contains edge-disjoint(a, b)-n-fans if and only if for anyk withk0min{n–1, |V(G)|–2} and for any subsetX ofV(G)-{a, b} with cardinalityk, G-X is (n-k)-edge-connected betweena andb.     

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.     

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 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.     

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.     

Complete lattices of subgroups in compact groups

Summary LetG be a compact group and a sublattice of the lattice of all closed subgroups ofG. In Proposition 1 it is shown that is a complete lattice if it is a closed subset of the spaceG ^c of all closed non empty subsets ofG. In general the converse of this fact is not true (Example 3), but the following result can be obtained (Theorem 5): If is complete and if each element of is normalized by the connected component of the identity ofG, then is a closed, totally disconnected subset ofG ^c. We mention the following corollary: IfG is totally disconnected or abelian, then is complete if and only if it is a closed subset ofG ^c.While writing this paper the author was a fellow of the National Research Council (A 7171).     

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.     

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.     

Projective plane and Möbius band obstructions

LetS be a compact surface with possibly non-empty boundary S and letG be a graph. LetK be a subgraph ofG embedded inS such that SK. Anembedding extension ofK toG is an embedding ofG inS which coincides onK with the given embedding ofK. Minimal obstructions for the existence of embedding extensions are classified in cases whenS is the projective plane or the Möbius band (for several canonical choices ofK). Linear time algorithms are presented that either find an embedding extension, or return a nice obstruction for the existence of extensions.Supported in part by the Ministry of Science and Technology of Slovenia, Research Project P1-0210-101-94.     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Conservative weightings and ear-decompositions of graphs

A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |CJ||C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality of a joint ofG. Namely, =(+|V|–1)/2 where denotes the minimum number of edges whose contraction leaves a factor-critical graph.To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.     

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.     

On a Test Statistic for Linear Trend

Let {W(s)} _s 0 be a standard Wiener process. The supremum of the squared Euclidian norm Y (t)², of the R²-valued process Y(t)=(1/t W(t), {12/t ³ int_{0 t} s dW (s)– {3/t} W(t)), t [, 1], is the asymptotic, large sample distribution, of a test statistic for a change point detection problem, of appearance of linear trend. We determine the asymptotic behavior P {sup _t [, 1] Y(t)² > u as u , of this statistic, for a fixed (0,1), and for a moving = (u) 0 at a suitable rate as u . The statistical interest of our results lie in their use as approximate test levels.     

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.