首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
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 π :HG. 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 l1 norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}n 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.  相似文献   

2.
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 cv, is . We show that the edges of every graph that does not contain a component isomorphic to K2 can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, cucv.  相似文献   

3.
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.  相似文献   

4.
Let be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets PiPj with ij. This can be thought of as the ‘k-expansion’ of the complete graph Kr: 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 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 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 2p+1. In this paper we also show that when r=2p+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.  相似文献   

5.
Consider a domain , and two analytic matrix-valued functions functions . Consider also points and positive integers n 1, n 2, . . . , n N . We are interested in the existence of an analytic function such that X(ω) is invertible, and G(ω) coincides with X(ω)F(ω)X(ω)−1 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.  相似文献   

6.
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≤ia such that G i is σ-unreal and δ(G i)→c as n→∞ for all 1 ≤ia, 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.  相似文献   

7.
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 x1, x2, x3, if {x1} and {x2, x3} 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.  相似文献   

8.
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.  相似文献   

9.
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 C2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree , for some constant cc(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  相似文献   

10.
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 α HN 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  相似文献   

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

12.
In this paper we prove that if is a set of k positive integers and {A 1, ..., 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.  相似文献   

13.
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 {v1, ..., vn}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w1, ..., wk), where wi 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 ws, wr are adjacent in Y. G(w, Y) is acted upon by Sk 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  相似文献   

14.
Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤kn→∞ we show that is asymptotically equal to (k−1)k−1k2−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.  相似文献   

15.
Given two disjoint subsets T 1 and T 2 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 1 and V 2 such that the graphs induced by V 1 and V 2 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. 1 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.  相似文献   

16.
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 (Ej)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 (Ej)j=0 of strictly contractive complex p  ×  q matrices. Hereby, (Ej)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  相似文献   

17.
For real parameters a, b, c, and t, where c is not a nonpositive integer, we determine exactly when the integral operator
is bounded on where is the open unit ball in and dvt (z)  =  (1  −  |z| 2) t dv (z) with dv being volume measure on The characterization remains the same if we replace (1  −  〈zw 〉) c in the integral kernel above by its modulus |1  −  〈zw〉| c.  相似文献   

18.
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|2)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   相似文献   

19.
  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
We define a parameter γ(H) of the graph H and show that, if H has t vertices, then
where α = 0.319. . . is an explicit constant and o(1) denotes a term tending to zero as t→∞. The extremal graphs are unions of pseudo-random graphs. If H has t1+τ edges then , equality holding for almost all H and for all regular H. We show how γ(H) might be evaluated for other graphs H also, such as complete multi-partite graphs. * Research supported by EPSRC studentship 99801140.  相似文献   

20.
Let L be a bounded lattice. If for each a1 < b1L and a2 < b2L there is a lattice embedding ψ: [a1, b1] → [a2, b2] with ψ(a1) = a2 and ψ(b1) = b2, 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 Fp. 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 Lp; moreover we can stipulate either that Lp is a continuous geometry or that Lp 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.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号