Turánnical hypergraphs

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs G = ([n],E) such that no member of the restriction set \begin{align*}\mathcal {R}\end{align*} = \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced by \begin{align*}\mathcal {R}\end{align*} = {X∈ \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*}: X ∩ [m]≠??}. That is, we determine the maximal number of edges in an n ‐vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r ‐uniform hypergraph \begin{align*}\mathcal R\end{align*} on vertex set [n] is called Turánnical (respectively ε ‐Turánnical), if for any graph G on [n] with more edges than the Turán number t_r(n) (respectively (1 + ε)t_r(n) ), no hyperedge of \begin{align*}\mathcal {R}\end{align*} induces a copy of K_r in G. We determine the thresholds for random r ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐?uczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Convergence analysis of some high–order time accurate schemes for a finite volume method for second order hyperbolic equations on general nonconforming multidimensional spatial meshes

The present work is an extension of our previous work (Bradji, Numer Methods Partial Differ Equations, to appear) which dealt with error analysis of a finite volume scheme of a first convergence order (both in time and space) for second‐order hyperbolic equations on general nonconforming multidimensional spatial meshes introduced recently in (Eymard et al. IMAJ Numer Anal 30(2010), 1009–1043). We aim in this article to get some higher‐order time accurate schemes for a finite volume method for second‐order hyperbolic equations using the same class of spatial generic meshes stated above. We derive a family of finite volume schemes approximating the wave equation, as a model for second‐order hyperbolic equations, in which the discretization in time is performed using a one‐parameter scheme of the Newmark's method. We prove that the error estimate of these finite volume schemes is of order two (or four) in time and it is of optimal order in space. These error estimates are analyzed in several norms which allow us to derive approximations for the exact solution and its first derivatives whose the convergence order is two (or four) in time and it is optimal in space. We prove in particular, when the discrete flux is calculated using a stabilized discrete gradient, that the convergence order is \begin{align*}k^2+h_\mathcal{D}\end{align*} or \begin{align*}k^4+h_\mathcal{D}\end{align*}, where \begin{align*}h_\mathcal{D}\end{align*} (resp. k) is the mesh size of the spatial (resp. time) discretization. These estimates are valid under the regularity assumption \begin{align*}u\in C^4(\lbrack 0,T\rbrack;C^2(\overline{\Omega}))\end{align*}, when the schemes are second‐order accurate in time, and \begin{align*}u\in C^6(\lbrack 0,T\rbrack;C^2(\overline{\Omega}))\end{align*}, when the schemes are four‐order accurate in time for the exact solution u. The proof of these error estimates is based essentially on a comparison between the finite volume approximate solution and an auxiliary finite volume approximation. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Distribution of the number of spanning regular subgraphs in random graphs

In this paper, we examine the moments of the number of d ‐factors in \begin{align*}\mathcal{ G}(n,p)\end{align*} for all p and d satisfying d³ = o(p²n). We also determine the limiting distribution of the number of d ‐factors inside this range with further restriction that \begin{align*}(1-p)\sqrt{dn}\to\infty\end{align*} as n →∞.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with \begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*} and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,…,S_k} of {1,…n} which maximizes \begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \begin{align*}\frac{R(B)^2}{C(B)}\end{align*}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some \begin{align*}v_1,\ldots,v_k\in \mathbb{R}^k\end{align*} then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,…,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,…,A_k} of \begin{align*}\mathbb{R}^{k-1}\end{align*} of the quantity \begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle\end{align*}, where for i∈{1,…,k} the vector \begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*} is the Gaussian moment of A_i, i.e., \begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}. We also show that for every ε > 0, achieving an approximation guarantee of \begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*} is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Local Precise Large and Moderate Deviations for Sums of Independent Random Variables

Let {X, X_k : k ≥ 1} be a sequence of independent and identically distributed random variables with a common distribution F. In this paper, the authors establish some results on the local precise large and moderate deviation probabilities for partial sums S_n =sum from i=1 to n(X_i) in a unified form in which X may be a random variable of an arbitrary type,which state that under some suitable conditions, for some constants T 0, a and τ 1/2and for every fixed γ 0, the relation P(S_n- na ∈(x, x + T ]) ~nF((x + a, x + a + T ]) holds uniformly for all x ≥γn~τ as n→∞, that is, P(Sn- na ∈(x, x + T ]) lim sup- 1 = 0.n→+∞x≥γnτnF((x + a, x + a + T ])The authors also discuss the case where X has an infinite mean.     

Critical behavior in inhomogeneous random graphs

We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k^‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n^2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n^{(τ‐2)/(τ‐1)}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013     

A theoretical analysis of a new finite volume scheme for second order hyperbolic equations on general nonconforming multidimensional spatial meshes

We consider the wave equation, on a multidimensional spatial domain. The discretization of the spatial domain is performed using a general class of nonconforming meshes which has been recently studied for stationary anisotropic heterogeneous diffusion problems, see Eymard et al. (IMAJ Numer Anal 30 (2010), 1009–1043). The discretization in time is performed using a uniform mesh. We derive a new implicit finite volume scheme approximating the wave equation and we prove error estimates of the finite volume approximate solution in several norms which allow us to derive error estimates for the approximations of the exact solution and its first derivatives. We prove in particular, when the discrete flux is calculated using a stabilized discrete gradient, the convergence order is \begin{align*} h_\mathcal{D}\end{align*} (resp. k) is the mesh size of the spatial (resp. time) discretization. This estimate is valid under the regularity assumption \begin{align*}u\in C^3(\lbrack 0,T\rbrack;C^2(\overline{\Omega}))\end{align*} for the exact solution u. The proof of these error estimates is based essentially on a comparison between the finite volume approximate solution and an auxiliary finite volume approximation. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.

Consider the random graph on n vertices 1,…,n. Each vertex i is assigned a type x_i with x₁,…,x_n being independent identically distributed as a nonnegative random variable X. We assume that EX³< ∞. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability \begin{align*}\min \{1, \frac{x_ix_j}{n}\left(1+\frac{a}{n^{1/3}} \right) \}\end{align*}. We study the critical phase, which is known to take place when EX² = 1. We prove that normalized by n^‐2/3the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient \begin{align*}\sqrt{{\textbf{ E}}X{\textbf{ E}}X^3}\end{align*}and drift \begin{align*}a-\frac{{\textbf{ E}}X^3}{{\textbf{ E}}X}s\end{align*}. In particular, we conclude that the size of the largest connected component is of order n^2/3. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486–539, 2013     

Approximate Controllability of Nonlinear Delay Integro Differential Evolution Equations with Random Impulses

The basic concept of this research is to analyse the approximate controllability (AC) of a nonlinear delay integrodifferential evolution system (NDIDES) with random impulse of the type \begin{align*}&z''(\zeta)=\mathfrak{A}(\zeta)z(\zeta)+(\mathfrak{B}x)(\zeta)+\int_{0}^{\zeta}\mathcal{H}(\zeta, s,z(\beta(s))), \ \sigma_{q} <\zeta < \sigma_{q+1}, \ \zeta\in [\zeta_{0}, \mathcal{T}], \\ &z(\sigma_{q})=a_{q}(\tau_{q})z(\sigma^{-}_{q}), ~~q = 1,2,\ldots,\\ &z_{\zeta_{0}}=\upsilon,\end{align*} by assuming that the linear system is approximately controllable. The existence and uniqueness of the mild solution to above system have been determined by using the Banach contraction principle and trajectory accessible sets. We generalize the results for NDIDES with and without fixed-type impulsive moments.     

SIR epidemics on random graphs with a fixed degree sequence

Let Δ > 1 be a fixed positive integer. For \begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} let G_z be chosen uniformly at random from the collection of graphs on ∥z∥₁n vertices that have z_in vertices of degree i for i = 1,…,Δ. We determine the likely evolution in continuous time of the SIR model for the spread of an infectious disease on G_z, starting from a single infected node. Either the disease halts after infecting only a small number of nodes, or an epidemic spreads to infect a linear number of nodes. Conditioning on the event that more than a small number of nodes are infected, the epidemic is likely to follow a trajectory given by the solution of an associated system of ordinary differential equations. These results also give the likely number of nodes infected during the course of the epidemic and the likely length in time of the epidemic. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A Self‐Dual Polar Factorization for Vector Fields

We show that any nondegenerate vector field u in \begin{align*}L^{\infty}(\Omega, \mathbb{R}^N)\end{align*}, where Ω is a bounded domain in \begin{align*}\mathbb{R}^N\end{align*}, can be written as \begin{align*}u(x)= \nabla_1 H(S(x), x)\quad {\text for a.e.\ x \in \Omega}\end{align*}}, where S is a measure‐preserving point transformation on Ω such that \begin{align*}S^2=I\end{align*} a.e. (an involution), and \begin{align*}H: \mathbb{R}^N \times \mathbb{R}^N \to \mathbb{R}\end{align*} is a globally Lipschitz antisymmetric convex‐concave Hamiltonian. Moreover, u is a monotone map if and only if S can be taken to be the identity, which suggests that our result is a self‐dual version of Brenier's polar decomposition for the vector field as \begin{align*}u(x)=\nabla \phi (S(x))\end{align*}, where ? is convex and S is a measure‐preserving transformation. We also describe how our polar decomposition can be reformulated as a (self‐dual) mass transport problem. © 2012 Wiley Periodicals, Inc.     

Giant components in Kronecker graphs

Let \begin{align*}n\in\mathbb{N}\end{align*}, 0 <α,β,γ< 1. Define the random Kronecker graph K(n,α,γ,β) to be the graph with vertex set \begin{align*}\mathbb{Z}_2^n\end{align*}, where the probability that u is adjacent to v is given by p_u,v =α ^{u ? v} γ^{( 1‐u )?( 1‐v )}β^{n‐ u ? v ‐( 1‐u )?( 1‐v )}. This model has been shown to obey several useful properties of real‐world networks. We establish the asymptotic size of the giant component in the random Kronecker graph.© 2011 Wiley Periodicals, Inc. Random Struct. Alg.,2011     

Local superconvergence of the derivative for tensor‐product block FEM

In this article, we shall discuss local superconvergence of the derivative for tensor‐product block finite elements over uniform partition for three‐dimensional Poisson's equation on the basis of Liu and Zhu (Numer Methods Partial Differential Eq 25 (2009) 999–1008). Assume that odd m ≥ 3, x₀ is an inner locally symmetric point of uniform rectangular partition \begin{align*}\mathcal{T}_{h}\end{align*} and ρ(x₀,?Ω) means the distance between x₀ and boundary ?Ω. Combining the symmetry technique (Wahlbin, Springer, 1995; Schatz, Sloan, and Wahlbin, SIAM J Numer Anal 33 (1996), 505–521; Schatz, Math Comput 67 (1998), 877–899) with weak estimates for tensor‐product block finite elements of degree m ≥ 3 [see Liu and Zhu, Numer Methods Partial Differential Eq 25 (2009) 999–1008] and the finite element theory of Green function in ??³ presented in this article, we propose the \begin{align*}O(h^{m+3}|\ln h|^{\frac{4}{3}}+h^{2m+2}|\ln h|^{\frac{4}{3}}\rho(x_{0},\partial\Omega)^{-m})\end{align*} convergence of the derivatives for tensor‐product block finite elements of degree m ≥ 3 on x₀. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 457–475, 2012     

Crossing numbers of imbalanced graphs

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4n edges is at least constant times e³/n². Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d₁?d₂?···?d_n, then the crossing number satisfies \begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*} with \begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}, and that this bound is tight apart from the values of the constants c₁, c₂>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010     

A Note on Randomly Weighted Sums of Dependent Subexponential Random Variables

The author obtains that the asymptotic relations■hold as x→∞,where the random weightsθ_1,···,θ_(n )are bounded away both from 0 and from∞with no dependency assumptions,independent of the primary random variables X_1,···,X_(n )which have a certain kind of dependence structure and follow non-identically subexponential distributions.In particular,the asymptotic relations remain true whenX_1,···,X_(n )jointly follow a pairwise Sarmanov distribution.     

The Nonexistence of the Solutions for the Non-Newtonian Filtration Equation with Absorption

The paper proves the nonexistence of the solution for the following Cauchy problem\begin{align*}\begin{cases}u_{t} ={\rm div}\left(\left|\nabla u^{m} \right|^{p-2} \nabla u^{m} \right)-\lambda \; u^{q},&\qquad \left(x,t\right)\in S_{T} ={\mathbb{R}}^N \times \left(0,T\right), \\u\left(x,\; 0\right)=\delta \left(x\right), &\qquad x\in {\mathbb{R}}^,\end{cases}\end{align*}under some conditions on \textit{m,p,q},$\lambda$, where $\delta $ is Dirac function.     

New Class of Kirchhoff Type Equations with Kelvin-Voigt Damping and General Nonlinearity: Local Existence and Blow-up in Solutions

In this paper, we consider a class of Kirchhoff equation, in the presence of a Kelvin-Voigt type damping and a source term of general nonlinearity forms. Where the studied equation is given as follows\begin{equation*}u_{tt} -\mathcal{K}\left( \mathcal{N}u(t)\right)\left[ \Delta_{p(x)}u +\Delta_{r(x)}u_{t}\right]=\mathcal{F}(x, t, u).\end{equation*}Here, $\mathcal{K}\left( \mathcal{N}u(t)\right)$ is a Kirchhoff function, $\Delta_{r(x)}u_{t}$ represent a Kelvin-Voigt strong damping term, and $\mathcal{F}(x, t, u)$ is a source term. According to an appropriate assumption, we obtain the local existence of the weak solutions by applying the Galerkin's approximation method. Furthermore, we prove a non-global existence result for certain solutions with negative/positive initial energy. More precisely, our aim is to find a sufficient conditions for $p(x), q(x), r(x), \mathcal{F}(x,t,u)$ and the initial data for which the blow-up occurs.