Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

On the eigenvalues of the Sturm-Liouville operator with potentials from Sobolev spaces

We study the asymptotic behavior of the eigenvalues the Sturm-Liouville operator Ly = ?y″ + q(x)y with potentials from the Sobolev space W ₂ ^θ?1 , θ ≥ 0, including the nonclassical case θ ∈ [0, 1) in which the potential is a distribution. The results are obtained in new terms. Let s _2k (q) = λ _k ^1/2 (q) ? k, s _2k?1(q) = μ _k ^1/2 (q) ? k ? 1/2, where {λ _k } ₁ ^∞ and {μ _k } ₁ ^∞ are the sequences of eigenvalues of the operator L generated by the Dirichlet and Dirichlet-Neumann boundary conditions, respectively,. We construct special Hilbert spaces t ₂ ^θ such that the mapping F:W ₂ ^θ?1 →t ₂ ^θ defined by the equality F(q) = {s _n } ₁ ^∞ is well defined for all θ ≥ 0. The main result is as follows: for θ > 0, the mapping F is weakly nonlinear, i.e., can be expressed as F(q) = Uq + Φ(q), where U is the isomorphism of the spaces W ₂ ^θ?1 and t ₂ ^θ , and Φ(q) is a compact mapping. Moreover, we prove the estimate ∥Ф(q)∥_τ ≤ C∥q∥_θ?1, where the exact value of τ = τ(θ) > θ ? 1 is given and the constant C depends only on the radius of the ball ∥q∥_θ? ≤ R, but is independent of the function q varying in this ball.     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

On effective determination of symmetric-square lifts

Let F be the symmetric-square lift with Laplace eigenvalue λ _F (Δ) = 1+4µ². Suppose that |µ| ≤ Λ. We show that F is uniquely determined by the central values of Rankin-Selberg L-functions L(s, F ? h), where h runs over the set of holomorphic Hecke eigen cusp forms of weight κ ≡ 0 (mod 4) with κ?^?+?, t9 = max {4(1+4θ)/(1?18θ), 8(2?9θ)/3(1?18θ)} for any 0 ≤ θ < 1/18 and any ∈ > 0. Here θ is the exponent towards the Ramanujan conjecture for GL₂ Maass forms.     

Eigenfunction expansions for the Schrödinger equation with an inverse-square potential

We consider the one-dimensional Schrödinger equation -f″ + q_κf = Ef on the positive half-axis with the potential q_κ(r) = (κ² - 1/4)r^-2. For each complex number ν, we construct a solution u_ν^κ(E) of this equation that is analytic in κ in a complex neighborhood of the interval (-1, 1) and, in particular, at the “singular” point κ = 0. For -1 < κ < 1 and real ν, the solutions u_ν^κ(E) determine a unitary eigenfunction expansion operator U_κ,ν: L₂(0,∞) → L₂(R, Vκ,ν), where Vκ,ν is a positive measure on R. We show that every self-adjoint realization of the formal differential expression -?_r² + q_κ(r) for the Hamiltonian is diagonalized by the operator U_κ,ν for some ν ∈ R. Using suitable singular Titchmarsh–Weyl m-functions, we explicitly find the measures V_κ,ν and prove their continuity in κ and ν.     

On the shape of the ground state eigenvalue density of a random Hill's equation

Consider the Hill's operator Q = ?d²/dx² + q(x) in which q(x), 0 ≤ x ≤ 1, is a white noise. Denote by f(μ) the probability density function of ?λ₀(q), the negative of the ground state eigenvalue, at μ. We prove the detailed asymptotics as μ → + ∞. This result is based on a precise Laplace analysis of a functional integral representation for f(μ) established by S. Cambronero and H. P. McKean in 5 . © 2005 Wiley Periodicals, Inc.     

Mixing Times of Critical Two‐Dimensional Potts Models

We study dynamical aspects of the q‐state Potts model on an n × n box at its critical β_c(q). Heat‐bath Glauber dynamics and cluster dynamics such as Swendsen–Wang (that circumvent low‐temperature bottlenecks) are all expected to undergo “critical slowdowns” in the presence of periodic boundary conditions: the inverse spectral gap, which in the subcritical regime is O(1), should at criticality be polynomial in n for 1 < q ≤ 4, and exponential in n for q > 4 in accordance with the predicted discontinuous phase transition. This was confirmed for q = 2 (the Ising model) by the second author and Sly, and for sufficiently large q by Borgs et al. Here we show that the following holds for the critical Potts model on the torus: for q=3, the inverse gap of Glauber dynamics is n^O(1); for q = 4, it is at most n^{O(log n)}; and for every q > 4 in the phase‐coexistence regime, the inverse gaps of both Glauber dynamics and Swendsen‐Wang dynamics are exponential in n. For free or monochromatic boundary conditions and large q, we show that the dynamics at criticality is faster than on the torus (unlike the Ising model where free/periodic boundary conditions induce similar dynamical behavior at all temperatures): the inverse gap of Swendsen‐Wang dynamics is exp(n^o(1)). © 2017 Wiley Periodicals, Inc.     

Certain classes of potentials for p ‐Laplacian to be non‐degenerate

Given a positive integer n and an exponent 1 ≤ α ≤ ∞. We will find explicitly the optimal bound r_n such that if the L^α norm of a potential q (t ) satisfies ‖q ‖equation/tex2gif-inf-2.gif < r_n then the n ^th Dirichlet eigenvalue of the onedimensional p ‐Laplacian with the potential q (t ): (|u ′|^{p –2} u ′)′ + (λ + q (t )) |u |^{p –2}u = 0 (1 < p < ∞) will be positive. Using these bounds, we will construct, for the Dirichlet, the Neumann, the periodic or the antiperiodic boundary conditions, certain classes of potentials q (t ) so that the p ‐Laplacian with the potential q (t ) is non‐degenerate, which means that the above equation with λ = 0 has only the trivial solution verifying the corresponding boundary condition. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Theq-gamma function forx<0

F. H. Jackson defined aq analogue of the gamma function which extends theq-factorial (n!) _q =1(1+q)(1+q+q ²)...(1+q+q ²+...+q ^n–1) to positivex. Askey studied this function and obtained analogues of most of the classical facts about the gamma function, for 0<q<1. He proved an analogue of the Bohr-Mollerup theorem, which states that a logarithmically convex function satisfyingf(1)=1 andf(x+1)=[(q ^x –1)/(q–1)]f(x) is in fact theq-gamma function He also studied the behavior of _q asq changes and showed that asq1^–, theq-gamma function becomes the ordinary gamma function forx>0.I proved many of these results forq>1. The current paper contains a study of the behavior of _q (x) forx<0 and allq>0. In addition to some basic properties of _q , we will study the behavior of the sequence {x _n (q)} of critical points asn orq changes.     

Density theorems and the mean value of arithmetical functions in short intervals

Let Γ=SL₂(?) and let Z_Γ(s) be the Selberg zeta function. Set π_Γ(P)=∑_N(P)≤P1, where P is a primitive hyperbolic class of conjugate elements in Γ and N(P) is the norm of P. It is shown that for P^1/2+θ=Q, 1≤θ≤1/2, we have $\pi _\Gamma \left( {P + Q} \right) - \pi _\Gamma \left( P \right) = \int\limits_P^{P + Q} {\frac{{du}}{{\log u}} + O_ \in \left( {QP^{ - \sigma \left( \theta \right) + \in } } \right),} $ where σ(θ)=θ²/2+O(¸₃), θ→0. Thus, a conjecture of Iwaniec (1984) is proved. Similar asymptotic formulas are obtained for the sums ∑_{Ph(-d)/ $\sqrt d $ and ∑Pr3(n)/ $\sqrt n $ , where h(?d) is the class number of the imaginary quadratic field of discriminant ?d<0 and r3(n) is the number of representations of n by the sum of three squares.}     

Infinite families of 2- and 3-designs with parameters v = p + 1, k = (p − 1)/2i + 1, where p odd prime, 2e T (p − 1), e ≥ 2, 1 ≤ i ≤ e

Let p be an odd prime number such that p − 1 = 2^em for some odd m and e ≥ 2. In this article, by using the special linear fractional group PSL(2, p), for each i, 1 ≤ i ≤ e, except particular cases, we construct a 2-design with parameters v = p + 1, k = (p − 1)/2ⁱ + 1 and λ = ((p − 1)/2ⁱ+1)(p − 1)/2 = k(p − 1)/2, and in the case i = e we show that some of these 2-designs are 3-designs. Likewise, by using the linear fractional group PGL(2,p) we construct an infinite family of 3-designs with the same v k and λ = k(k − 2). These supplement a part of [4], in which we gave an infinite family of 3-designs with parameters v = q + 1, k = (q + 1)/2 = (q − 1)/2 + 1 and λ = (q + 1)(q − 3)/8 = k(k − 2)/2, where q is a prime power such that q − 1 = 2m for some odd m and q > 7. Some of the designs given in this article and in [4] fill in a few blanks in the table of Chee, Colbourn, and Kreher [2]. © 1997 John Wiley & Sons, Inc.     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

Oscillation criteria for fourth‐order differential equations with middle term

Oscillation criteria for self‐adjoint fourth‐order differential equations were established for various conditions on the coefficients r(x) > 0, q(x) and p(x). However, most of these results deal with the case when lim_{x → ∞}∫^x₁q(s) ds < +∞. In this note we give a new oscillation criterion in the case when this condition is not fulfilled, in particular when q(x)↗ + ∞ (even with exponential growth).     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Quasirecognition by prime graph of the simple group <Superscript>2</Superscript><Emphasis Type="Italic">F</Emphasis><Subscript>4</Subscript>(<Emphasis Type="Italic">q</Emphasis>)

As the main result, we show that if G is a finite group such that Γ(G) = Γ(² F ₄(q)), where q = 2^2m+1 for some m ≧ 1, then G has a unique nonabelian composition factor isomorphic to ² F ₄(q). We also show that if G is a finite group satisfying |G| =|² F ₄(q)| and Γ(G) = Γ(² F ₄(q)), then G ≅ ² F ₄(q). As a consequence of our result we give a new proof for a conjecture of W. Shi and J. Bi for ² F ₄(q). The third author was supported in part by a grant from IPM (No. 87200022).     

Bipartite anti‐Ramsey numbers of cycles

We determine the maximum number of colors in a coloring of the edges of K_m,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of K_a,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a² ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Operators as spectral integrals of operator-valued functions from the study of multivariate stationary stochastic processes

P. Masani and the author have previously answered the question, “When is an operator on a Hilbert space $\text{H}$ the integral of a complex-valued function with respect to a given spectral (projection-valued) measure?” In this paper answers are given to the question, “When is a linear operator from $\text{H}$^q to $\text{H}$^p the integral of a spectral measure?”; here the values of the integrand are linear operators from the square-summable q-tuples of complex numbers to the square-summable p-tuples of complex numbers, and our spectral measure for $\text{H}$^q is the “inflation” of a spectral measure for $\text{H}$. In the course of this paper, we make available tools for handling the spectral analysis of q-variate weakly stationary processes, 1 ≤ q ≤ ∞, which should enable researchers to deal in the future with the case q = ∞. We show as one application of our theory that if U = ∫(in0, 2π]e^?iθE(dθ) is a unitary operator on $\text{H}$ and if T is a bounded linear operator from $\text{H}$^q to $\text{H}$^q (1 ≤ q ≤ ∞) which is a prediction operator for each stationary process (Uⁿx)_?∞^∞ ?$\text{H}$^q (for each x = (xⁱ)_i^j ∈ $\text{H}$^q, Uⁿx = (Uⁿxⁱ)_i=1^q), then T is a spectral integral, ∫(_0,2π)]Φ(θ) E(dθ), and the Banach norm of T, |T|_B = ess sup |Φ(θ)|_B.