On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ℤ ⁿ , the cardinalχ(ℤ ⁿ ) is equal to the minimal cardinality of an essential subset of ℤ ⁿ , i.e., a of a subsetA ⊂ ℤ ⁿ such that, for any coloring of the group ℤ ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(ℤ ⁿ ) < 2n is proved for alln and the relationχ(ℤ ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(ℤ ⁿ ) in ℤ ⁿ is completely described forn ≤ 3. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 341–350, September, 1998.     

Weighted inequalities for fractional type operators with some homogeneous kernels

In this paper, we study integral operators of the form Tαf(x)=∫Rn|x-A1y|-α1 ··· |x-Amy|-αmf(y)dy,where Ai are certain invertible matrices, αi 0, 1 ≤ i ≤ m, α1 + ··· + αm = n-α, 0 ≤α n. For 1/q = 1/p-α/n , we obtain the Lp (Rn, wp)-Lq(Rn, wq) boundedness for weights w in A(p, q) satisfying that there exists c 0 such that w(Aix) ≤ cw(x), a.e. x ∈ Rn , 1 ≤ i ≤ m.Moreover, we obtain theappropriate weighted BMO and weak type estimates for certain weights satisfying the above inequality. We also give a Coifman type estimate for these operators.     

Some intersection theorems

LetL(A) be the set of submatrices of anm×n matrixA. ThenL(A) is a ranked poset with respect to the inclusion, and the poset rank of a submatrix is the sum of the number of rows and columns minus 1, the rank of the empty matrix is zero. We attack the question: What is the maximum number of submatrices such that any two of them have intersection of rank at leastt? We have a solution fort=1,2 using the followoing theorem of independent interest. Letm(n,i,j,k) = max(|F|;|G|), where maximum is taken for all possible pairs of families of subsets of ann-element set such thatF isi-intersecting,G isj-intersecting andF ansd,G are cross-k-intersecting. Then fori≤j≤k, m(n,i,j,k) is attained ifF is a maximali-intersecting family containing subsets of size at leastn/2, andG is a maximal2k?i-intersecting family. Furthermore, we discuss and Erd?s-Ko-Rado-type question forL(A), as well.     

A common property of R(E, F) and B(ℝ n , ℝ m ) and a new method for seeking a path to connect two operators

Given two Banach spaces E, F, let B(E, F) be the set of all bounded linear operators from E into F, and R(E, F) the set of all operators in B(E, F) with finite rank. It is well-known that B(? ⁿ ) is a Banach space as well as an algebra, while B(? ⁿ , ? ^m ) for m ≠ n, is a Banach space but not an algebra; meanwhile, it is clear that R(E, F) is neither a Banach space nor an algebra. However, in this paper, it is proved that all of them have a common property in geometry and topology, i.e., they are all a union of mutual disjoint path-connected and smooth submanifolds (or hypersurfaces). Let Σ _r be the set of all operators of finite rank r in B(E, F) (or B(? ⁿ , ? ^m )). In fact, we have that 1) suppose Σ _r ∈ B(? ⁿ , ? ^m ), and then Σ _r is a smooth and path-connected submanifold of B(? ⁿ , ? ^m ) and dimΣ _r = (n + m)r ? r ², for each r ∈ [0, min{n,m}; if m ≠ n, the same conclusion for Σ _r and its dimension is valid for each r ∈ [0, min{n, m}]; 2) suppose Σ _r ∈ B(E, F), and dimF = ∞, and then Σ _r is a smooth and path-connected submanifold of B(E, F) with the tangent space T _A Σ _r = {B ∈ B(E, F): BN(A) ? R(A)} at each A ∈ Σ _r for 0 ? r ? ∞. The routine methods for seeking a path to connect two operators can hardly apply here. A new method and some fundamental theorems are introduced in this paper, which is development of elementary transformation of matrices in B(? ⁿ ), and more adapted and simple than the elementary transformation method. In addition to tensor analysis and application of Thom’s famous result for transversility, these will benefit the study of infinite geometry.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

Centerpole sets for colorings of abelian groups

A subset C?G of a group G is called k-centerpole if for each k-coloring of G there is an infinite monochromatic subset G, which is symmetric with respect to a point c??C in the sense that S=cS ^?1 c. By c _k (G) we denote the smallest cardinality c _k (G) of a k-centerpole subset in G. We prove that c _k (G)=c _k (? ^m ) if G is an abelian group of free rank m??k. Also we prove that c ₁(? ⁿ⁺¹)=1, c ₂(? ⁿ⁺²)=3, c ₃(? ⁿ⁺³)=6, 8??c ₄(? ⁿ⁺⁴)??c ₄(?⁴)=12 for all n????, and ${\frac{1}{2}(k^{2}+3k-4)\le c_{k}(\mathbb{Z}^{n})\le2^{k}-1-\max_{s\le k-2}\binom {k-1}{s-1}}$ for all n??k??4.     

On the equivalence of the Euler-Pommier operators in spaces of analytic functions

In the space A (θ) of all one-valued functions f(z) analytic in an arbitrary region G ? ? (0 ∈ G) with the topology of compact convergence, we establish necessary and sufficient conditions for the equivalence of the operators L ₁=α _n z ⁿ Δ ⁿ + ... + α₁ zΔ+α₀ E and L ₂= z ⁿ a _n (z)Δ ⁿ + ... + za ₁(z)Δ+a ₀(z)E, where δ: (Δ?)(z)=(f(z)-?(0))/z is the Pommier operator in A(G), n ∈ ?, α _n ∈ ?, a _k (z) ∈ A(G), 0≤k≤n, and the following condition is satisfied: Σ _j=s ^n?1 α _j+1 ∈ 0, s=0,1,...,n?1. We also prove that the operators z ^s+1Δ+β(z)E, β(z) ∈ A _R , s ∈ ?, and z ^s+1 are equivalent in the spaces A _R, 0?R?-∞, if and only if β(z) = 0.     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.     

Independence,irredundance, degrees and chromatic number in graphs

Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2.     

Generalized n-tuple colorings of a graph: A counterexample to a conjecture of Brigham and Dutton

In their papers (Technical Report CS-TR 50, University of Central Florida, 1980; J. Combin. Theory Ser. B32 (1982), 90–94) Brigham and Dutton introduce the notion of (n : i)-chromatic numbers of a graph, a generalization of Stahl's nth chromatic numbers (J. Combin. Theory Ser. B20, (1976), 185–203). The (n : i)-chromatic number of a graph G, denoted by χ_nⁱ(G), is the smallest integer m such that each vertex of G can be colored with a set of n colors in {1, 2,…, m} in such a way that any two adjacent vertices have exactly i colors in common. Brigham and Dutton conjecture at the end of loc cit that for all integers n and i with 0 ≤ i ≤ n ? 1, and for every graph G, χ_nⁱ⁺¹(G) ≤ χ_nⁱ(G). We prove this conjecture in some special cases and disprove it in the general case.     

The chromatic polynomial of an unlabeled graph

We investigate the chromatic polynomial χ(G, λ) of an unlabeled graph G. It is shown that $\text{χ(G, λ) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{χ(g, π, λ)}$, where g is any labeled version of G, A(g) is the automorphism group of g and χ(g, π, λ) is the chromatic polynomial for colorings of g fixed by π. The above expression shows that χ(G, λ) is a rational polynomial of degree n = |V(G)| with leading coefficient $\text{1}\text{|A(g)|}$. Though χ(G, λ) does not satisfy chromatic reduction, each polynomial χ(g, π, λ) does, thus yielding a simple method for computing χ(G, λ). We also show that the number N(G) of acyclic orientations of G is related to the argument λ = ?1 by the formula $\text{N(G) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{(?1)}{}^{\mathrm{s(\pi )}}\text{χ(g, π, ?1)}$, where s(π) is the number of cycles of π. This information is used to derive Robinson's (“Combinatorial Mathematics V” (Proc. 5th Austral. Conf. 1976), Lecture Notes in Math. Vol. 622, pp. 28–43, Springer-Verlag, New York/Berlin, 1977) cycle index sum equations for counting unlabeled acyclic digraphs.     

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

On Maillet determinant

For a positive integer m, let $\text{A = {1 ≤ a <}\text{m}\text{2}\text{| (a, m) = 1}}$ and let n = |A|. For an integer x, let R(x) be the least positive residue of x modulo m and if (x, m) = 1, let x′ be the inverse of x modulo m. If m is odd, then |R(ab′)|_a,b∈A = ?2^1?n(∏_χ(Σ_{a = 1}^{m ? 1}aχ(a))), where χ runs over all the odd Dirichlet characters modulo m.     

Shrinkage of de Morgan formulae under restriction

It is shown that a random restriction leaving only a fraction ? of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O(E^(5?√2)/2) = O(?^1.63). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long-standing result of O(?^1.5) by Subbotovskaya and a recent improvement to O(?^(21?√73)/8) = O(?^1.55) by Nisan and Impagliazzo. The New exponent yields an increased lower bound of n^{(7?√3)/2?o(1)} = Ω(n^2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Large induced forests in sparse graphs

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K₄, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001     

Path Partitions and Pn-free Sets

The detour order τ(G) of a graph G is the order of a longest path of G. A partition (A, B) of V is called an (a, b)-partition of G if τ(G[A]) ≤ a and τ(G[B]) ≤ b. The Path Partition Conjecture is the following:For any graph G, with detour order τ(G) = a + b, there exists an (a, b)-partition of G.We introduce and examine a conjecture which is possibly stronger: If M is a maximum P_n+1-free set of vertices of G, with n < τ(G), then τ(G − M) ≤ τ(G)− n.     

Phragmén-Lindelöf conditions for graph varieties

For P_m ∈ ?[z₁, …, z_n], homogeneous of degree m we investigate when the graph of P_m in ?ⁿ⁺¹ satisfies the Phragmén-Lindelöf condition PL(?ⁿ⁺¹, log), or equivalently, when the operator $i{\partial \over \partial_{x_{n+1}}}+P_{m}(D)$ admits a continuous solution operator on C^∞(?ⁿ⁺¹). This is shown to happen if the varieties V_+- ? {z ∈ ?ⁿ: P_m(z) = ±1} satisfy the following Phragmén-Lindelöf condition (SPL): There exists A ≥ 1 such that each plurisubharmonic function u on V_+- satisfying u(z) ≤ ¦z¦+ o(¦z¦) on V_+- and u(x) ≤ 0 on V_+- ∩ ?ⁿ also satisfies u(z) A¦ Im z¦ on V_+-. Necessary as well as sufficient conditions for V_+- to satisfy (SPL) are derived and several examples are given.     

Reduced Weyl asymptotics for pseudodifferential operators on bounded domains I. The finite group case

Let G⊂O(n) be a compact group of isometries acting on n-dimensional Euclidean space Rn, and X a bounded domain in Rn which is transformed into itself under the action of G. Consider a symmetric, classical pseudodifferential operator A₀ in L²(Rn) with G-invariant Weyl symbol, and assume that it is semi-bounded from below. We show that the spectrum of the Friedrichs extension A of the operator is discrete, and derive asymptotics for the number Nχ(λ) of eigenvalues of A less or equal λ and with eigenfunctions in the χ-isotypic component of L²(X) as λ→∞, giving also an estimate for the remainder term in case that G is a finite group. In particular, we show that the multiplicity of each unitary irreducible representation in L²(X) is asymptotically proportional to its dimension.