The Erd?s-Ko-Rado properties of various graphs containing singletons

Let G=(V,E) be a graph. For r≥1, let be the family of independent vertex r-sets of G. For v∈V(G), let denote the star. G is said to be r-EKR if there exists v∈V(G) such that for any non-star family A of pair-wise intersecting sets in . If the inequality is strict, then G is strictlyr-EKR.Let Γ be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. Holroyd, Spencer and Talbot proved that, if G∈Γ and 2r is no larger than the number of connected components of G, then G is r-EKR. However, Holroyd and Talbot conjectured that, if G is any graph and 2r is no larger than μ(G), the size of a smallest maximal independent vertex set of G, then G is r-EKR, and strictly so if 2r<μ(G). We show that in fact, if G∈Γ and 2r is no larger than the independence number of G, then G is r-EKR; we do this by proving the result for all graphs that are in a suitable larger set Γ^′?Γ. We also confirm the conjecture for graphs in an even larger set Γ^″?Γ^′.     

On complete subsets of the cyclic group

A subset X of an abelian G is said to be complete if every element of G can be expressed as a nonempty sum of distinct elements from X.Let A⊂Zn be such that all the elements of A are coprime with n. Solving a conjecture of Erd?s and Heilbronn, Olson proved that A is complete if n is a prime and if . Recently Vu proved that there is an absolute constant c, such that for an arbitrary large n, A is complete if , and conjectured that 2 is essentially the right value of c.We show that A is complete if , thus proving the last conjecture.     

On NP-hardness of the clique partition—Independence number gap recognition and related problems

We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than is NP-hard to compute.To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality always holds. Thus, QCP is satisfiable if and only if . Computing the Lovász number ?(G) we can detect QCP unsatisfiability at least when . In the other cases QCP reduces to gap recognition, with one minimum clique partition of G known.     

Rational torus-equivariant stable homotopy I: Calculating groups of stable maps

We construct an abelian category A(G) of sheaves over a category of closed subgroups of the r-torus G and show that it is of finite injective dimension. It can be used as a model for rational G-spectra in the sense that there is a homology theory

     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

The Rokhlin property and the tracial topological rank

Let A be a unital separable simple C∗-algebra  with TR(A)?1 and α be an automorphism. We show that if α satisfies the tracially cyclic Rokhlin property then . We also show that whenever A has a unique tracial state and α^m is uniformly outer for each m(≠0) and α^r is approximately inner for some r>0, α satisfies the tracial cyclic Rokhlin property. By applying the classification theory of nuclear C∗-algebras, we use the above result to prove a conjecture of Kishimoto: if A is a unital simple -algebra of real rank zero and α∈Aut(A) which is approximately inner and if α satisfies some Rokhlin property, then the crossed product is again an -algebra of real rank zero. As a by-product, we find that one can construct a large class of simple C∗-algebras with tracial rank one (and zero) from crossed products.     

Preservers of spectral radius, numerical radius, or spectral norm of the sum on nonnegative matrices

Let be the set of entrywise nonnegative n×n matrices. Denote by r(A) the spectral radius (Perron root) of . Characterization is obtained for maps such that r(f(A)+f(B))=r(A+B) for all . In particular, it is shown that such a map has the form

     

Crossed-products by finite index endomorphisms and KMS states

Given a unital -algebra A, an injective endomorphism preserving the unit, and a conditional expectation E from A to the range of α we consider the crossed-product of A by α relative to the transfer operator L=α⁻¹E. When E is of index-finite type we show that there exists a conditional expectation G from the crossed-product to A which is unique under certain hypothesis. We define a “gauge action” on the crossed-product algebra in terms of a central positive element h and study its KMS states. The main result is: if h>1 and E(ab)=E(ba) for all a,b∈A (e.g. when A is commutative) then the KMS_β states are precisely those of the form ψ=φ°G, where φ is a trace on A satisfying the identity

     

(DFS)-spaces of holomorphic functions invariant under differentiation

Let be a bounded convex domain, A^−∞(G) be the (DFS)-space of all holomorphic functions of polynomial growth on G and A^∞(G) be the Fréchet space of C^∞-functions on closure of G which are holomorphic on G. With the help of the Laplace transform we describe the strong dual of A^−∞(G) and prove that A^−∞(G) is the unique (DFS)-space H such that the space A^∞(G) is contained in H, H is embedded continuously in A^−∞(G) and H is invariant under differentiation.     

Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and f_s(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients f_s(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before.     

Operator space structure and amenability for Figà-Talamanca-Herz algebras

Column and row operator spaces—which we denote by COL and ROW, respectively—over arbitrary Banach spaces were introduced by the first-named author; for Hilbert spaces, these definitions coincide with the usual ones. Given a locally compact group G and p,p′∈(1,∞) with , we use the operator space structure on to equip the Figà-Talamanca-Herz algebra A_p(G) with an operator space structure, turning it into a quantized Banach algebra. Moreover, we show that, for p?q?2 or 2?q?p and amenable G, the canonical inclusion A_q(G)⊂A_p(G) is completely bounded (with cb-norm at most , where is Grothendieck's constant). As an application, we show that G is amenable if and only if A_p(G) is operator amenable for all—and equivalently for one—p∈(1,∞); this extends a theorem by Ruan.     

A spectral condition for odd cycles in graphs

Let G be a graph of sufficiently large order n, and let the largest eigenvalue μ(G) of its adjacency matrix satisfies . Then G contains a cycle of length t for every t?n/320This condition is sharp: the complete bipartite graph T₂(n) with parts of size ⌊n/2⌋ and ⌈n/2⌉ contains no odd cycles and its largest eigenvalue is equal to .This condition is stable: if μ(G) is close to and G fails to contain a cycle of length t for some t?n/321, then G resembles T₂(n).     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

A result on the total colouring of powers of cycles

The total chromatic number χ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that for every simple graph G, χ_T(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.     

A local criterion for Weyl modules for groups of type A

Let G be a universal Chevalley group over an algebraically closed field and U⁻ be the subalgebra of generated by all divided powers X_α,m with α<0. We conjecture an algorithm to determine if , where F∈U⁻, ω is a dominant weight and is a highest weight vector of the Weyl module Δ(ω). This algorithm does not use bases of Δ(ω) and is similar to the algorithm for irreducible modules that involves stepwise raising the vector under investigation. For an arbitrary G, this conjecture is proved in one direction and for G of type A in both.     

Fractional weak discrepancy and interval orders

The fractional weak discrepancywd_F(P) of a poset P=(V,?) was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227-2235] as the minimum nonnegative k for which there exists a function satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51-63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291-302] on the range of the wd_F function for semiorders (interval orders with no induced ) to interval orders with no , where n≥3. In particular, we prove that the range for such posets P is the set of rationals that can be written as r/s, where 0≤s−1≤r<(n−2)s. If wd_F(P)=r/s and P has an optimal forcing cycle C with and , then r≤(n−2)(s−1). Moreover when s≥2, for each r satisfying s−1≤r≤(n−2)(s−1) there is an interval order having such an optimal forcing cycle and containing no.     

Extension of Fourier algebra homomorphisms to duals of algebras of uniformly continuous functionals

For a locally compact group G, let XG be one of the following introverted subspaces of VN(G): , the C^∗-algebra of uniformly continuous functionals on A(G); , the space of weakly almost periodic functionals on A(G); or , the C^∗-algebra generated by the left regular representation on the measure algebra of G. We discuss the extension of homomorphisms of (reduced) Fourier-Stieltjes algebras on G and H to cb-norm preserving, weak^∗-weak^∗-continuous homomorphisms of into , where (XG,XH) is one of the pairs , , or . When G is amenable, these extensions are characterized in terms of piecewise affine maps.