On deformations of <Emphasis Type="Italic">F</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> in compact Lie groups

We study some properties of the varieties of deformations of free groups in compact Lie groups. In particular, we prove a conjecture of Margulis and Soifer about the density of non-virtually free points in such variety, and a conjecture of Goldman on the ergodicity of the action of Aut(F _n ) on such variety when n ≥ 3. The author was partially supported by NSF grant DMS-0404557, BSF grant 2004010, and the ‘Finite Structures’ Marie Curie Host Fellowship, carried out at the Alfréd Rényi Institute of Mathematics in Budapest.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

State spaces of <Emphasis Type="Italic">JB</Emphasis><Superscript><Emphasis Type="Italic">*</Emphasis></Superscript>-triples<Superscript>*</Superscript>

An atomic decomposition is proved for Banach spaces which satisfy some affine geometric axioms compatible with notions from the quantum mechanical measuring process. This is then applied to yield, under appropriate assumptions, geometric characterizations, up to isometry, of the unit ball of the dual space of a JB^*-triple, and up to complete isometry, of one-sided ideals in C^*-algebras.Mathematics Subject Classification (2000):17C65, 46L07Both authors are supported by NSF grant DMS-0101153     

Property (<Emphasis Type="Italic">T</Emphasis>) and rigidity for actions on Banach spaces

We study property (T) and the fixed-point property for actions on L ^p and other Banach spaces. We show that property (T) holds when L ² is replaced by L ^p (and even a subspace/quotient of L ^p ), and that in fact it is independent of 1≤p<∞. We show that the fixed-point property for L ^p follows from property (T) when 1<p< 2+ε. For simple Lie groups and their lattices, we prove that the fixed-point property for L ^p holds for any 1< p<∞ if and only if the rank is at least two. Finally, we obtain a superrigidity result for actions of irreducible lattices in products of general groups on superreflexive spaces. Bader partially supported by ISF grant 100146; Furman partially supported by NSF grants DMS-0094245 and DMS-0604611; Gelander partially supported by NSF grant DMS-0404557 and BSF grant 2004010; Monod partially supported by FNS (CH) and NSF (US).     

<Emphasis Type="Bold">C</Emphasis><Superscript><Emphasis Type="Bold">1,</Emphasis><Emphasis Type="Italic">α</Emphasis></Superscript> regularity for infinity harmonic functions in two dimensions

We propose a new method for showing C ^{1, α} regularity for solutions of the infinity Laplacian equation and provide full details of the proof in two dimensions. The proof for dimensions n ≥ 3 depends upon some conjectured local gradient estimates for solutions of certain transformed PDE. LCE is supported in part by NSF Grant DMS-0500452. OS was supported in part by the Miller Institute for Basic Research in Science, Berkeley.     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

Dynamical Borel-Cantelli lemmas for gibbs measures

LetT: X→X be a deterministic dynamical system preserving a probability measure μ. A dynamical Borel-Cantelli lemma asserts that for certain sequences of subsetsA _n ⊃ X and μ-almost every pointx∈X the inclusionT ⁿ x∈A _n holds for infinitely manyn. We discuss here systems which are either symbolic (topological) Markov chain or Anosov diffeomorphisms preserving Gibbs measures. We find sufficient conditions on sequences of cylinders and rectangles, respectively, that ensure the dynamical Borel-Cantelli lemma. Partially supported by NSF grant DMS-9732728. Partially supported by NSF grant DMS-9704489.     

Universal non-completely-continuous operators

A bounded linear operator between Banach spaces is calledcompletely continuous if it carries weakly convergent sequences into norm convergent sequences. Isolated is a universal operator for the class of non-completely-continuous operators fromL ₁ into an arbitrary Banach space, namely, the operator fromL ₁ into ⊆_∞ defined byT ₀(f) = (∫r _n f d μ) _n>-0, wherer _n is thenth Rademacher function. It is also shown that there does not exist a universal operator for the class of non-completely-continuous operators between two arbitrary Banach spaces. The proof uses the factorization theorem for weakly compact operators and a Tsirelson-like space. Supported in part by NSF grant DMS-9306460. Participant, NSF Workshop in Linear Analysis & Probability, Texas A&M University (supported in part by NSF grant DMS-9311902). Supported in part by NSF grant DMS-9003550.     

Recognizability of finite simple groups <Emphasis Type="Italic">L</Emphasis><Subscript>4</Subscript>(2<Superscript>m</Superscript>) and <Emphasis Type="Italic">U</Emphasis><Subscript>4</Subscript>(2<Superscript>m</Superscript>) by spectrum

It is proved that finite simple groups L₄(2^m), m ⩾ 2, and U₄(2^m), m ⩾ 2, are, up to isomorphism, recognized by spectra, i.e., sets of their element orders, in the class of finite groups. As a consequence the question on recognizability by spectrum is settled for all finite simple groups without elements of order 8. Supported by RFBR (grant Nos. 05-01-00797 and 06-01-39001), by SB RAS (Complex Integration project No. 1.2), and by the Ministry of Education of China (Project for Retaining Foreign Expert). Supported by NSF of Chongqing (CSTC: 2005BB8096). __________ Translated from Algebra i Logika, Vol. 47, No. 1, pp. 83–93, January–February, 2008.     

Central Value Of Automorphic <Emphasis Type="Italic">L</Emphasis>-Functions

We prove a generalization to the totally real field case of the Waldspurger’s formula relating the Fourier coefficient of a half integral weight form and the central value of the L-function of an integral weight form. Our proof is based on a new interpretation of Waldspurger’s formula as a combination of two ingredients – an equality between global distributions, and a dichotomy result for theta correspondence. As applications we generalize the Kohnen–Zagier formula for holomorphic forms and prove the equivalence of the Ramanujan conjecture for half integral weight forms and a case of the Lindel?f hypothesis for integral weight forms. We also study the Kohnen space in the adelic setting. The first author was partially supported by NSF grant DMS-0070762. The second author was partially supported by NSF grant DMS-0355285. Received: July 2005 Accepted: August 2005     

Double Dirichlet series and the <Emphasis Type="Italic">n</Emphasis>-th order twists of Hecke <Emphasis Type="Italic">L</Emphasis>-series

Let n3 be a fixed integer and let F be a global field containing the n-th roots of unity. In this paper we study the collective behavior of the n-th order twists of a fixed Hecke L-series for F. To do so, we introduce a double Dirichlet series in two complex variables (s, w) which is a weighted sum of the twists, and obtain its meromorphic continuation. We also study related sums of n-th order Gauss sums. These objects together satisfy a nonabelian group of functional equations in (s, w) of order 32. Mathematics Subject Classification (1991):11R42, 11F66, 11F70, 11M41, 11R47.Research supported in part by NSF grants DMS-9970118 (Friedberg), DMS-0088921 (Hoffstein), and DMS-9700542 (Lieman), and by NSA grant MDA 904-03-1-0012 (Friedberg).     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Pfaffian graphs, <Emphasis Type="Italic">T</Emphasis>-joins and crossing numbers

We characterize Pfaffian graphs in terms of their drawings in the plane. We generalize the techniques used in the proof of this characterization, and prove a theorem about the numbers of crossings in T-joins in different drawings of a fixed graph. As a corollary we give a new proof of a theorem of Kleitman on the parity of crossings in drawings of K _2j+1 and K _2j+1,2k+1. Partially supported by NSF grants DMS-0200595 and DMS-0701033.     

An Algorithm for Corona Solutions on <Emphasis Type="Italic">H</Emphasis><Superscript>∞</Superscript> (<Emphasis Type="Italic">D</Emphasis>)

We give an algorithm to find corona solutions in H ^∞ (D) for polynomial input data. Partially supported by NSF Grant DMS-0400307.     

PSPACE complexity of modal logic <Emphasis Type="Italic">K D</Emphasis>45<Subscript>n</Subscript>

We study sequent calculus for multi-modal logic K D45_n and its complexity. We introduce a loop-check free sequent calculus. Loop-check is eliminated by using the marked modal operator □_i^•, which is used as an alternative to sequents with histories ([8], [3], [5]). All inference rules are invertible or semi-invertible. To get this, we use or branches beside common and branches. We prove the equivalence between known sequent calculus and our newly introduced efficient sequent calculus. We concentrate on the complexity analysis of the introduced sequent calculus for multi-modal logic K D45_n. We prove that the space complexity of the given calculus is polynomial (O(l ³)). We show the maximum height of the constructed derivation tree that leads to the reduction of the time and space complexity. We present a decision algorithm for multi-modal logic K D45_n and some nontrivial examples to improve the introduced loop-check free sequent calculus.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Averaging Special Values of Dirichlet <Emphasis Type="Italic">L</Emphasis>-Series

In this paper we derive estimates for weighted averages of the special values of Dirichlet L-series which generalize similar estimates of David and Pappalardi [1]. The author is partially supported by NSF grant DMS-0090117. 2000 Mathematics Subject Classification: Primary–11M06; Secondary–11G05     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.