Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

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.     

Cycles in <Emphasis Type="Italic">G</Emphasis>-orbits in <Emphasis Type="Italic">G</Emphasis><Superscript><Emphasis Type="Italic">ℂ</Emphasis></Superscript>-flag manifolds

There is a natural duality between orbits of a real form G of a complex semisimple group G on a homogeneous rational manifold Z=G /P and those of the complexification K of any of its maximal compact subgroups K: (,) is a dual pair if is a K-orbit. The cycle space C() is defined to be the connected component containing the identity of the interior of {g:g() is non-empty and compact}. Using methods which were recently developed for the case of open G-orbits, geometric properties of cycles are proved, and it is shown that C() is contained in a domain defined by incidence geometry. In the non-Hermitian case this is a key ingredient for proving that C() is a certain explicitly computable universal domain.Research of the first author partially supported by Schwerpunkt Global methods in complex geometry and SFB-237 of the Deutsche Forschungsgemeinschaft.The second author was supported by a stipend of the Deutsche Akademische Austauschdienst.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

The Domination Parameters of Cubic Graphs

Let ir(G), (G), i(G), ₀(G), (G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In this paper we show that for any nonnegative integers k₁, k₂, k₃, k₄, k₅ there exists a cubic graph G satisfying the following conditions: (G) – ir(G) k₁, i(G) – (G) k₂, ₀(G) – i(G) > k₃, (G) – ₀(G) – k₄, and IR(G) – (G) – k₅. This result settles a problem posed in [9].Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093).Supported by RUTCOR.     

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.     

A commutativity criterion for certain algebras of invariant differential operators on nilpotent homogeneous spaces

Let G be a connected, simply connected real nilpotent Lie group with Lie algebra , H a connected closed subgroup of G with Lie algebra and f a linear form on satisfying f([, ]) = {0} Let _f be the unitary character of H with differential at the origin. Let _f be the unitary representation of G induced from the character _f of H. We consider the algebra (, , f) of differential operators invariant under the action of G on the bundle with basis G/H associated to these data. We show that (, , f) is commutative if and only if _f is of finite multiplicities. This proves a conjecture of Corwin-Greenleaf and Duflo. Mathematics Subject Classification (1991):43A80, 43A85, 22E25, 22E27, 22E30UMR n 7539 du CNRS, Analyse, Géométrie et Applications.UMR n 7586 du CNRS, Théorie des Groupes, Représentations, Applications.     

Volumes des représentations sur un corps local

Let be a locally compact second countable group, F a local field of characteristic zero and G an F-almost-simple F-algebraic group. In this paper we study the space X(,G) of Zariski-dense representations : G = G(F) using the natural morphism of cohomological functors * : H*(G, ·) H*(, ·) (where H denotes the continuous cohomology).First let F be a p-adic field. We completely describe the relations between the geometry and the cohomology of G : using geometric properties of the Bruhat-Tits building of G we construct natural cocycles for any irreducible cohomological representation of G. We then adapt these results to the case where the field F is archimedean.Using these cocycles we obtain a simple cohomological characterization of representations with bounded image.Our main result is then the construction, using the previous cocycles and dynamical properties at infinity of , of cohomological invariants (called volumes) on the space X(,G). These volumes describe how the image () goes to infinity in G. They have coefficients in the natural universal infinite-dimensional representation L(, )$\mathbb{C}$ of .In the case where is a cocompact lattice of SO(n, 1) or SU(n, 1), we use these volumes to produce new non-trivial numerical invariants on X(,G), which refine previously known invariants.

---

Volumes des représentations sur un corps local

     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Characterizing matchings as the intersection of matroids

This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for which the matching independence system is the intersection of two matroids, we study the function (G), which is the minimum number of matroids that need to be intersected in order to obtain the set of matchings on a graph G, and examine the maximal value, (n), for graphs with n vertices. We describe an integer programming formulation for deciding whether (G)k. Using combinatorial arguments, we prove that (n)(log logn). On the other hand, we establish that (n)O(logn/ log logn). Finally, we prove that (n)=4 for n=5,,12, and sketch a proof of (n)=5 for n=13,14,15.An earlier version appears as an extended abstract in the Proceedings of COMB01 [5]. Supported by the Gerhard-Hess-Forschungs-Förderpreis (WE 1462) of the German Science Foundation (DFG) awarded to R. Weismantel.     

On convergence of types and processes in Euclidean space

Let be an Euclidean space; Y _n , Z, U random vectors in ; h _n , g _n affine transformations and let þ be a subgroup of the group G of all the in vertible affine transformations, closed relative to G. Suppose that g_n and where Z is nonsingular. The behaviour of _n = h _n g _n ^–1 as n is discussed first. The results are used then to prove that if for all t(0, ), where h _n þ and Z ₁ is nonsingular and nonsymmetric with respect to þ then H, for all t(0,) and is a continuous homomorphism of the multiplicative group of (0, ) into þ. The explicit forms of the possible are shown.     

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.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

Lévy–Khintchine Formula and Dual Convolution Semigroups Associated with Laguerre and Bessel Functions

In this work we consider a system of partial differential operators D ₁,D ₂ on K=[0,+[×R, whose eigenfunctions are the functions (x,t), (x,t)K, =((R0)×N)(0×[0,+[), which are related to the Laguerre functions for ((R 0)×N)(0,0) and which are the Bessel functions for (0×[0,+[). We provide K and with a convolution structure. We prove a Lévy–Khintchine formula on K, which permits us to characterize dual convolution semigroups on .     

Isomorphismen von rechtseiträumen

Spaces called rectangular spaces were introduced in [5] as incidence spaces (P,G) whose set of linesG is equipped with an equivalence relation and whose set of point pairs P² is equipped with a congruence relation , such that a number of compatibility conditions are satisfied. In this paper we consider isomorphisms, automorphisms, and motions on the rectangular spaces treated in [5]. By an isomorphism of two rectangular spaces (P,G, , ) and (P,G, , ) we mean a bijection of the point setP onto P which maps parallel lines onto parallel lines and congruent points onto congruent points. In the following, we consider only rectangular spaces of characteristic 2 or of dimension two. According to [5] these spaces can be embedded into euclidean spaces. In case (P,G, , ) is a finite dimensional rectangular space, then every congruence preserving bijection ofP onto P is in fact an isomorphism from (P,G, , ) onto (P,G, , ) (see (2.4)). We then concern ourselves with the extension of isomorphisms. Our most important result is the theorem which states that any isomorphism of two rectangular spaces can be uniquely extended to an isomorphism of the associated euclidean spaces (see (3.2)). As a consequence the automorphisms of a rectangular space (P,G, , ) are precisely the restrictions (onP) of the automorphisms of the associated euclidean space which fixP as a whole (see (3.3)). Finally we consider the motions of a rectangular space (P,G, , ). By a motion of(P. G,, ) we mean a bijection ofP which maps lines onto lines, preserves parallelism and satisfies the condition((x), (y)) (x,y) for allx, y P. We show that every motion of a rectangular space can be extended to a motion of the associated euclidean space (see (4.2)). Thus the motions of a rectangular space (P,G, , ) are seen to be the restrictions of the motions of the associated euclidean space which mapP into itself (see (4.3)). This yields an explicit representation of the motions of any rectangular plane (see (4.4)).

---

---

Herrn Professor Burau zum 85. Geburtstag gewidmet     

Independence in hypergraphs

Suppose an integral function (|A|)q₁ defined on the subsets of edges of a hypergraph (X,u,) satisfies the following two conditions: 1) any set W u such that |A|(|A|) for any AW is matroidally independent; 2) if W is an independent set, then there exists a unique partitionW=T₁+ T₂+...+T_v such that |T ⁱ |=(|T ⁱ |),i1:v, and for any AW, |A|(|A|) there exists a T_i such that AT_i. The form of such a function is found, in terms of parameters of generalized connected components, hypercycles, and hypertrees.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 196–204, 1982.     

Long paths and cycles in tough graphs

For a graphG, letp(G) andc(G) denote the length of a longest path and cycle, respectively. Let (t,n) be the minimum ofp(G), whereG ranges over allt-tough connected graphs onn vertices. Similarly, let (t,n) be the minimum ofc(G), whereG ranges over allt-tough 2-connected graphs onn vertices. It is shown that for fixedt>0 there exist constantsA, B such that (t,n)A·log(n) and (t,n)·log((t,n))B·log(n). Examples are presented showing that fort1 there exist constantsA, B such that (t,n)A·log(n) and (t,n)B· log(n). It is conjectured that (t,n) B·log(n) for some constantB. This conjecture is shown to be valid within the class of 3-connected graphs and, as conjectured in Bondy [1] forl=3, within the class of 2-connectedK _1.l-free graphs, wherel is fixed.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

Convolution Operators with Fractional Measures Associated to Holomorphic Functions

Let be an open set in the complex plane and let be a holomorphic function on . Let K be a compact subset of with nonempty interior such that 0 K. Let be the Borel measure of R ⁴ C ² given by(E = _K E(z, (z))|z|^–2 d(z)where 0 < 2 and d(x ₁ + ix ₂) = dx ₁ dx ₂ denotes the Lebesgue measure on C. Let T be the convolution operator T f = * f. In this paper we characterize the type set E associated to T .     

On the concentration of stresses due to a small elliptic inclusion on the neutral axis of a deep beam under constant bending moment

Zusammenfassung Es wird die Spannungsverteilung untersucht, die sich in einem breiten Balken mit konstanter Höhe unter einem konstanten Biegemoment ausbildet, wenn er eine kleine elliptische Einschliessung mit Zentrum auf der Neutralachse enthält. Insbesondere werden die Fälle eines sehr starren Einschlusses sowie eines elliptischen Loches im Detail diskutiert.

---

Nomenclature x, y Cartesian coordinates - , elliptic coordinates - u, v (u ,u )=components of displacements - , unit elongations in -and -directions - shearing strain - , normal stress components in elliptical coordinates - shearing stress in elliptic coordinates - _x , _y normal stress in Cartesian coordinates - _xy shearing stress in Cartesian coordinates - E Young's modulus for the beam - v Poisson's ratio for the beam - 1/h ₁, 1/h ₂ stretch ratios - e _x + _y dilatation - 2 rotation - M bending moment