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.     

Vertex-Colouring Edge-Weightings

A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted c_v, is . We show that the edges of every graph that does not contain a component isomorphic to K₂ can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, c_u ≠c_v.     

A Lower Bound on the First Spectral Gap of Schrödinger Operators with Kato Class Measures

We study Schr?dinger operators on formally given by , where μ is a positive, compactly supported measure from the Kato class. Under the assumption that a certain condition on the μ-volume of balls is satisfied and that H_μ has at least two eigenvalues below the essential spectrum , we derive a lower bound on the first spectral gap of H_μ. The assumption on the μ-volume of balls is in particular satisfied if μ is of the form , where M is a compact (n-1)-dimensional Lipschitz submanifold of , σ_M the surface measure on M, and . Submitted: May 8, 2008.; Accepted: February 20, 2009.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

On the Similarity of Analytic Matrix Functions

Consider a domain , and two analytic matrix-valued functions functions . Consider also points and positive integers n ₁, n ₂, . . . , n _N . We are interested in the existence of an analytic function such that X(ω) is invertible, and G(ω) coincides with X(ω)F(ω)X(ω)⁻¹ up to order n _j at the point ω _j . We will see that such a function exists provided that F(ω _j ),G(ω _j ) have cyclic vectors, and the characteristic polynomials of F,G coincide up to order n _j at ω _j . This allows one to give a short proof to a result of Huang, Marcantognini and Young concerning spectral interpolation in the unit disk. The author was partially supported by a grant from the National Science Foundation. Received: September 8, 2006. Accepted: January 11, 2007.     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

Polar Graphs and Corresponding Involution Sets, Loops and Steiner Triple Systems

A 1-factorization (or parallelism) of the complete graph with loops is called polar if each 1-factor (parallel class) contains exactly one loop and for any three distinct vertices x₁, x₂, x₃, if {x₁} and {x₂, x₃} belong to a 1-factor then the same holds for any permutation of the set {1, 2, 3}. To a polar graph there corresponds a polar involution set , an idempotent totally symmetric quasigroup (P, *), a commutative, weak inverse property loop (P, + ) of exponent 3 and a Steiner triple system . We have: satisfies the trapezium axiom is self-distributive ⇔ (P, + ) is a Moufang loop is an affine triple system; and: satisfies the quadrangle axiom is a group is an affine space.     

Extremal Problems For Transversals In Graphs With Bounded Degree

We introduce and discuss generalizations of the problem of independent transversals. Given a graph property , we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property . In this paper we study this problem for the following properties : “acyclic”, “H-free”, and “having connected components of order at most r”. We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations on the power of this topological method. We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such that every transversal contains a fixed graph H as a subgraph. Finally, we pose several open questions. * Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich. † Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826.     

Minors in Expanding Graphs

We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every -free graph G with average degree r ( are constants) contains a minor with average degree , for some constant ; (b) Every C_2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree , for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs. Received: March 2008, Accepted: May 2008     

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     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

Sequential Dynamical Systems Over Words

In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v₁, ..., v_n}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w₁, ..., w_k), where w_i is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if w_s, w_r are adjacent in Y. G(w, Y) is acted upon by S_k via and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y). Received September 12, 2004     

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.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425&ndash;434, 1999.     

The Schur–Potapov Algorithm for Sequences of Complex p × q Matrices. I

The main theme of this paper is to characterize distinguished subclasses of the matricial Schur class in terms of Taylor coefficients. Starting point of our investigations is the observation that the Taylor coefficient sequences of functions from are exactly the infinite p  ×  q Schur sequences. We draw our attention mainly to the subclass of which consists of all p ×  q Schur functions for which the corresponding Taylor coefficient sequences are nondegenerate p  ×  q Schur sequences. Using an appropriate adaptation of the Schur–Potapov algorithm for functions belonging to to infinite sequences of complex p  ×  q matrices we obtain an one-to-one correspondence between infinite nondegenerate p  ×  q Schur sequences and the set of all infinite sequences (E_j)_j=0^∞ of strictly contractive complex p  ×  q matrices. Taking into account the construction of this gives us an one-to-one correspondence between and the set of all infinite sequences (E_j)_j=0^∞ of strictly contractive complex p  ×  q matrices. Hereby, (E_j)_{j =0}^∞ is called the sequence of Schur–Potapov parameters (shortly SP-parameters) of f. Communicated by Daniel Alpay. Submitted: August 17, 2006; Accepted: September 13, 2006     

A Class of Integral Operators on the Unit Ball of \mathbb{C}^{n}

For real parameters a, b, c, and t, where c is not a nonpositive integer, we determine exactly when the integral operator

Carleson Measures for Spaces of Dirichlet Type

If 0 < p < ∞ and α > − 1, the space consists of those functions f which are analytic in the unit disc and have the property that f ′ belongs to the weighted Bergman space A_α^p. In 1999, Z. Wu obtained a characterization of the Carleson measures for the spaces for certain values of p and α. In particular, he proved that, for 0 < p ≤ 2, the Carleson measures for the space are precisely the classical Carleson measures. Wu also conjectured that this result remains true for 2 < p < ∞. In this paper we prove that this conjecture is false. Indeed, we prove that if 2 < p < ∞, then there exists g analytic in such that the measure μ_g,p on defined by dμ_g,p (z) = (1 − |z|²)^{p - 1}| g ′ (z)|^p dx dy is not a Carleson measure for but is a classical Carleson measure. We obtain also some sufficient conditions for multipliers of the spaces      

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 product of two von Neumann n-frames, its characteristic, and modular fractal lattices

Let L be a bounded lattice. If for each a₁ < b₁ ∈ L and a₂ < b₂ ∈ L there is a lattice embedding ψ: [a₁, b₁] → [a₂, b₂] with ψ(a₁) = a₂ and ψ(b₁) = b₂, then we say that L is a quasifractal. If ψ can always be chosen to be an isomorphism or, equivalently, if L is isomorphic to each of its nontrivial intervals, then L will be called a fractal lattice. For a ring R with 1 let denote the lattice variety generated by the submodule lattices of R-modules. Varieties of this kind are completely described in [16]. The prime field of characteristic p will be denoted by F_p. Let be a lattice variety generated by a nondistributive modular quasifractal. The main theorem says that is neither too small nor too large in the following sense: there is a unique , a prime number or zero, such that and for any n ≥ 3 and any nontrivial (normalized von Neumann) n-frame of any lattice in , is of characteristic p. We do not know if in general; however we point out that, for any ring R with 1, implies . It will not be hard to show that is Arguesian. The main theorem does have a content, for it has been shown in [2] that each of the is generated by a single fractal lattice L_p; moreover we can stipulate either that L_p is a continuous geometry or that L_p is countable. The proof of the main theorem is based on the following result of the present paper: if is a nontrivial m-frame and is an n-frame of a modular lattice L with m, n ≥ 3 such that and , then these two frames have the same characteristic and, in addition, they determine a nontrivial mn-frame of the same characteristic in a canonical way, which we call the product frame. Presented by E. T. Schmidt.