Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

Fong characters and chains of normal subgroups

In this note, we show that if is a π-partial character of the π-separable group is a chain of normal subgroups of G, and H is a Hall π-subgroup of G, then has a Fong character α Irr(H) such that for every subgroup , every irreducible constituent of α _H∩N is Fong for N. We also show that if is quasi-primitive, then for every normal subgroup M of G the irreducible constituents of are Fong for M. Received: 21 July 2006 Revised: 17 January 2007     

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

The Extremal Function For Noncomplete Minors

  We investigate the maximum number of edges that a graph G can have if it does not contain a given graph H as a minor (subcontraction). Let

The Threshold for the Erdos, Jacobson and Lehel Conjecture to Be True

Let σ（k, n） be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ（k, n） can be realized by a graph containing a clique of k ＋ 1 vertices. Erdos et al. （Graph Theory, 1991, 439-449） conjectured that σ（k, n） = （k - 1）（2n- k） ＋ 2. Li et al. （Science in China, 1998, 510-520） proved that the conjecture is true for k 〉 5 and n ≥ （k2） ＋ 3, and raised the problem of determining the smallest integer N（k） such that the conjecture holds for n ≥ N（k）. They also determined the values of N（k） for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N（k） ≤ （k2） ＋ 3 for k ≥ 8. In this paper, we determine the exact values of σ（k, n） for n ≥ 2k＋3 and k ≥ 6. Therefore, the problem of determining σ（k, n） is completely solved. In addition, we prove as a corollary that N（k） -= [5k-1/2] for k ≥6.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

Jackson＇s Theorem on Bounded Symmetric Domains

Polynomial approximation is studied on bounded symmetric domain Ω in C^n for holomorphic function spaces X such as Bloch-type spaces, Bergman-type spaces, Hardy spaces, Ω algebra and Lipschitz space. We extend the classical Jackson＇s theorem to several complex variables：Eκ（f,X）≤ω（1/k,f,X）, where Eκ（f,X） is the deviation of the best approximation of f ∈X by polynomials of degree at most k with respect to the X-metric and ω（1/k,f,X） is the corresponding modulus of continuity.     

The Cauchy Problem for the Generalized Korteweg-de Vries-Benjamin-Ono Equation with Low Regularity Data

The Cauchy problem of the generalized Korteweg-de Vries-Benjamin-Ono equation is considered, and low regularity and limit behavior of the solutions are obtained. For k = 1, local well- posedness is obtained for data in H^s（R）（s 〉 -3/4）. For k = 2, local result for data in H^S（R）（s 〉1/4） is obtained. For k = 3, local result for data in H^S（R）（s 〉 -1/6） is obtained. Moreover, the solutions of generalized Korteweg-de Vries-Benjamin-Ono equation converge to the solutions of KdV equation if the term of Benjamin-Ono equation tends to zero.     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

The Erdős-Sós Conjecture for Graphs Whose Complements Contain No <Emphasis Type="Italic">C</Emphasis><Subscript>4</Subscript>

Abstract Erdős and Sós conjectured in 1963 (see [1], Problem 12 in 247) that every graph G on n vertices with size contains every tree T of size k. In this paper, we prove the conjecture for graphs whose complements contain no cycles of length 4. Supported by the National Natural Science Foundation of China (No.19971086) and the Doctoral Foundation of Hainan University.     

The normal subgroup structure of the extended Hecke groups

We consider the extended Hecke groups generated by T(z) = −1/z, S(z) = −1/(z + λ) and R(z) = 1/z with λ ≥ 2. In this paper, firstly, we study the fundamental region of the extended Hecke groups . Then, we determine the abstract group structure of the commutator subgroups , the even subgroup , and the power subgroups of the extended Hecke groups . Also, finally, we give some relations between them.     

Semi-Fredholm Spectrum and Weyl＇s Theorem for Operator Matrices

When A ∈ B（H） and B ∈ B（K） are given, we denote by Mc an operator acting on the Hilbert space HΘ K of the form Me = （ A0 CB）. In this paper, first we give the necessary and sufficient condition for Mc to be an upper semi-Fredholm （lower semi-Fredholm, or Fredholm） operator for some C ∈B（K,H）. In addition, let σSF＋（A） = {λ ∈ C ： A-λI is not an upper semi-Fredholm operator} bc the upper semi-Fredholm spectrum of A ∈ B（H） and let σrsF- （A） = {λ∈ C ： A-λI is not a lower semi-Fredholm operator} be the lower semi Fredholm spectrum of A. We show that the passage from σSF±（A） U σSF±（B） to σSF±（Mc） is accomplished by removing certain open subsets of σSF-（A） ∩σSF＋ （B） from the former, that is, there is an equality σSF±（A） ∪σSF± （B） = σSF± （Mc） ∪＆ where L is the union of certain of the holes in σSF±（Mc） which ilappen to be subsets of σSF- （A） A σSF＋ （B）. Weyl＇s theorem and Browder＇s theorem are liable to fail for 2 × 2 operator matrices. In this paper, we also explore how Weyl＇s theorem, Browder＇s theorem, a-Weyl＇s theorem and a-Browder＇s theorem survive for 2 × 2 upper triangular operator matrices on the Hilbert space.     

A Note on Certain Block Spaces on the Unit Sphere

In this note, we clarify a relation between block spaces and the Hardy space. We obtain Bq^0.v belong to H^1（S^n-1）＋L（ln＋L）^1＋v（s^n-1）,v〉-1,q〉1,Furthermore,if v≥ 0, q 〉 1. we verify that block spaces Rq^0.v（S^n-1）are proper subspaces of H1 （S^n- 1）,     

Distribution of lattice orbits on homogeneous varieties

Given a lattice Γ in a locally compact group G and a closed subgroup H of G, one has a natural action of Γ on the homogeneous space V = H\ G. For an increasing family of finite subsets {Γ _T : T > 0}, a dense orbit υ· Γ, υ∈V and compactly supported function φ on V, we consider the sums . Understanding the asymptotic behavior of S _φ,υ (T) is a delicate problem which has only been considered for certain very special choices of H,G and {Γ _T }. We develop a general abstract approach to the problem, and apply it to the case when G is a Lie group and either H or G is semisimple. When G is a group of matrices equipped with a norm, we have where G _T = {g ∈G: ||g|| < T} and Γ _T = G _T ∩ Γ. We also show that the asymptotics of S _{φ, υ} (T) is governed by where ν is an explicit limiting density depending on the choice of υ and || · ||. Submitted: March 2005 Revision: April 2006 Accepted: June 2006     

The Asymptotics of the Two-Dimensional Wave Equation for a General Multi-Connected Vibrating Membrane with Piecewise Smooth Robin Boundary Conditions

The asymptotic expansion for small |t| of the trace of the wave kernel ∧↑μ(t) =∑v=1^∞exp(-it μv^1/2), where i= √-1 and {μv}v=1^∞ are the eigenvalues of the negative Laplacian -△=-∑β=1^2(δ/δx^β)^2 in the (x^1, x^2)-plane, is studied for a multi-connected vibrating membrane Ω in R^2 surrounded by simply connected bounded domains Ωj with smooth boundaries δΩj(j=1,...,n), where a finite number of piecewise smooth Robin boundary conditions on the piecewise smooth components Гi(i=1 κj-1,...,κj) of the boundaries δΩj are considered, such that δΩj=∪i=1 κj-1^κj Гi and κ0=0. The basic problem is to extract information on the geometry of Ω using the wave equation approach. Some geometric quantities of Ω (e.g. the area of Ω, the total lengths of its boundary, the curvature of its boundary, the number of the holes of Ω, etc.) are determined from the asymptotic expansion of the trace of the wave kernel ∧↑μ(t) for small |t|.     

The Number Of Orientations Having No Fixed Tournament

Let T be a fixed tournament on k vertices. Let D(n,T ) denote the maximum number of orientations of an n-vertex graph that have no copy of T. We prove that for all sufficiently (very) large n, where t_k−1(n) is the maximum possible number of edges of a graphon n vertices with no K_k, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity lemma and therefore show that in these cases already holds for (relatively) small values of n. * Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Ergodic Retraction Theorem and Weak Convergence Theorem for Reversible Semigroups of Non-Lipschitzian Mappings

Let G be a semitopological semigroup. Let C be a closed convex subset of a uniformly convex Banaeh space E with a Frechet differentiable norm, and T = {Tt ： t ∈ G} be a continuous representation of G as nearly asymptotically nonexpansive type mappings of C into itself such that the common fixed point set F（T） of T in C is nonempty. It is shown that if G is right reversible, then for each almost-orbit u（.） of T, ∩s∈G ^-CO{u（t） ： t ≥ s} ∩ F（T） consists of at most one point. Furthermore, ∩s∈G ^-CO{Ttx ： t ≥ s} ∩ F（T） is nonempty for each x ∈ C if and only if there exists a nonlinear ergodic retraction P of C onto F（T） such that PTs - TsP = P for all s ∈ G and Px ∈^-CO{Ttx ： s ∈ G} for each x ∈ C. This result is applied to study the problem of weak convergence of the net {u（t） ： t ∈ G} to a common fixed point of T.     

On the geometry of metric measure spaces

We introduce and analyze lower (Ricci) curvature bounds  ⩾ K for metric measure spaces . Our definition is based on convexity properties of the relative entropy regarded as a function on the L ₂-Wasserstein space of probability measures on the metric space . Among others, we show that  ⩾ K implies estimates for the volume growth of concentric balls. For Riemannian manifolds,  ⩾ K if and only if  ⩾ K for all . The crucial point is that our lower curvature bounds are stable under an appropriate notion of D-convergence of metric measure spaces. We define a complete and separable length metric D on the family of all isomorphism classes of normalized metric measure spaces. The metric D has a natural interpretation, based on the concept of optimal mass transportation. We also prove that the family of normalized metric measure spaces with doubling constant ⩽ C is closed under D-convergence. Moreover, the family of normalized metric measure spaces with doubling constant ⩽ C and diameter ⩽ L is compact under D-convergence.     

Lifting Unitary Elements with Application to Approximately Inner Automorphisms

Let A be a separable unital nuclear simple C＊-algebra with torsion K0 （A）, free K1 （A） and with the UCT. Let T ： A→M（K）/K be a unital homomorphism. We prove that every unitary element in the commutant of T（A） is an exponent, thus it is liftable. We also prove that each automorphism α on E with α ∈ Aut0（A） is approximately inner, where E is a unital essential extension of A by K and α is the automorphism on A induced by α.