亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Let $N$ be the number of triangles in an Erd\H{o}s-R\'enyi graph $\mathcal{G}(n,p)$ on $n$ vertices with edge density $p=d/n,$ where $d>0$ is a fixed constant. It is well known that $N$ weakly converges to the Poisson distribution with mean ${d^3}/{6}$ as $n\rightarrow \infty$. We address the upper tail problem for $N,$ namely, we investigate how fast $k$ must grow, so that the probability of $\{N\ge k\}$ is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when $k^{1/3} \log k< (\frac{3}{\sqrt{2}})^{2/3} \log n$ (sub-critical regime) as well as pin down the tail behavior when $k^{1/3} \log k> (\frac{3}{\sqrt{2}})^{2/3} \log n$ (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost $k$ vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately $(6k)^{1/3}$. This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades, culminating in (Harel, Moussat, Samotij,'19) which analyzed the problem only in the regime $p\gg \frac{1}{n}.$ The proofs rely on several novel graph theoretical results which could have other applications.

When the regression function belongs to the standard smooth classes consisting of univariate functions with derivatives up to the $(\gamma+1)$th order bounded in absolute values by a common constant everywhere or a.e., it is well known that the minimax optimal rate of convergence in mean squared error (MSE) is $\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$ when $\gamma$ is finite and the sample size $n\rightarrow\infty$. From a nonasymptotic viewpoint that does not take $n$ to infinity, this paper shows that: for the standard H\"older and Sobolev classes, the minimax optimal rate is $\frac{\sigma^{2}\left(\gamma+1\right)}{n}$ ($\succsim\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$) when $\frac{n}{\sigma^{2}}\precsim\left(\gamma+1\right)^{2\gamma+3}$ and $\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$ ($\succsim\frac{\sigma^{2}\left(\gamma+1\right)}{n}$) when $\frac{n}{\sigma^{2}}\succsim\left(\gamma+1\right)^{2\gamma+3}$. To establish these results, we derive upper and lower bounds on the covering and packing numbers for the generalized H\"older class where the absolute value of the $k$th ($k=0,...,\gamma$) derivative is bounded by a parameter $R_{k}$ and the $\gamma$th derivative is $R_{\gamma+1}-$Lipschitz (and also for the generalized ellipsoid class of smooth functions). Our bounds sharpen the classical metric entropy results for the standard classes, and give the general dependence on $\gamma$ and $R_{k}$. By deriving the minimax optimal MSE rates under various (well motivated) $R_{k}$s for the smooth classes with the help of our new entropy bounds, we show several interesting results that cannot be shown with the existing entropy bounds in the literature.

We consider the classical Minimum Crossing Number problem: given an $n$-vertex graph $G$, compute a drawing of $G$ in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on $\Delta$ -- the maximum vertex degree in $G$. The best current approximation algorithm achieves an $O(n^{1/2-\varepsilon}\cdot \text{poly}(\Delta\cdot\log n))$-approximation, for a small fixed constant $\epsilon$, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized $O\left(2^{O((\log n)^{7/8}\log\log n)}\cdot\text{poly}(\Delta)\right )$-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in $n$ approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in $n$). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex $v\in V(G)$, the circular ordering, in which the images of the edges incident to $v$ must enter the image of $v$ in the drawing is fixed as part of the input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation algorithm for Minimum Crossing Number. We introduce several new technical tools, that we hope will be helpful in obtaining better algorithms for the problem in the future.

Meta-elliptical copulas are often proposed to model dependence between the components of a random vector. They are specified by a correlation matrix and a map $g$, called density generator. While the latter correlation matrix can easily be estimated from pseudo-samples of observations, the density generator is harder to estimate, especially when it does not belong to a parametric family. We give sufficient conditions to non-parametrically identify this generator. Several nonparametric estimators of $g$ are then proposed, by M-estimation, simulation-based inference, or by an iterative procedure available in the R package ElliptCopulas. Some simulations illustrate the relevance of the latter method.

A triangle in a hypergraph $\mathcal{H}$ is a set of three distinct edges $e, f, g\in\mathcal{H}$ and three distinct vertices $u, v, w\in V(\mathcal{H})$ such that $\{u, v\}\subseteq e$, $\{v, w\}\subseteq f$, $\{w, u\}\subseteq g$ and $\{u, v, w\}\cap e\cap f\cap g=\emptyset$. Johansson proved in 1996 that $\chi(G)=\mathcal{O}(\Delta/\log\Delta)$ for any triangle-free graph $G$ with maximum degree $\Delta$. Cooper and Mubayi later generalized the Johansson's theorem to all rank $3$ hypergraphs. In this paper we provide a common generalization of both these results for all hypergraphs, showing that if $\mathcal{H}$ is a rank $k$, triangle-free hypergraph, then the list chromatic number \[ \chi_{\ell}(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left( \frac{\Delta_{\ell}}{\log \Delta_{\ell}} \right)^{\frac{1}{\ell-1}} \right\}\right), \] where $\Delta_{\ell}$ is the maximum $\ell$-degree of $\mathcal{H}$. The result is sharp apart from the constant. Moreover, our result implies, generalizes and improves several earlier results on the chromatic number and also independence number of hypergraphs, while its proof is based on a different approach than prior works in hypergraphs (and therefore provides alternative proofs to them). In particular, as an application, we establish a bound on chromatic number of sparse hypergraphs in which each vertex is contained in few triangles, and thus extend results of Alon, Krivelevich and Sudakov, and Cooper and Mubayi from hypergraphs of rank 2 and 3, respectively, to all hypergraphs.

We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the classes $\mathrm{TM}_r(d)$ of arbitrary graphs that have tree models of height $d$ and $r$ labels. We show that the graphs of $\mathrm{TM}_r(d)$ are $\mathrm{MSO}$-pseudo-finite relative to the class $\mathrm{TM}^{\text{f}}_r(d)$ of finite graphs of $\mathrm{TM}_r(d)$; that is, that every $\mathrm{MSO}$ sentence true in a graph of $\mathrm{TM}_r(d)$ is also true in a graph of $\mathrm{TM}^{\text{f}}_r(d)$. We also show that $\mathrm{TM}_r(d)$ is closed under ultraproducts and ultraroots. These results have two consequences. The first is that the index of the $\mathrm{MSO}[m]$-equivalence relation on graphs of $\mathrm{TM}_r(d)$ is bounded by a $(d+1)$-fold exponential in $m$. The second is that $\mathrm{TM}_r(d)$ is exactly the class of all graphs that are $\mathrm{MSO}$-pseudo-finite relative to $\mathrm{TM}^{\text{f}}_r(d)$.

We introduce here the model of growing graphs, a model of dynamic networks in which nodes can generate new nodes, thus expanding the network. This motivates the algorithmic problem of constructing a target graph G, starting from a single node. To properly model this, we assume that every node u can generate at most one node v in every round (or time slot). Every newly generated node v can activate edges with other nodes, only at the time of its birth, provided that these nodes are up to a small distance d away from v. We show that the most interesting case is when d=2. As we prove, in order to achieve the construction of a target graph G in a small number of time slots, we might need to pay for auxiliary edges (the "excess edges"), which will be eventually removed. This creates a trade-off between the number of time slots and the number of excess edges required to construct a target graph. In this paper, we deal with the following algorithmic question: Given a target graph G of n nodes, can G be constructed in at most k time slots and with at most \ell excess edges? On the positive side, we provide polynomial-time algorithms that efficiently construct fundamental graph families, such as lines, stars, trees, and planar graphs. In particular, we show that trees can be constructed in a poly-logarithmic number of slots with linearly many excess edges, while planar graphs can be constructed in a logarithmic number of slots with O(n\log n) excess edges. We also give a polynomial-time algorithm for deciding whether a graph can be constructed in \log n slots with \ell = 0 excess edges. On the negative side, we prove that the problem of determining the minimum number of slots required for a graph to be constructed with zero excess edges (i) is NP-complete and (ii) for any \varepsilon>0, cannot be approximated within n^{1-\varepsilon}, unless P=NP.

Scene graphs are powerful representations that encode images into their abstract semantic elements, i.e, objects and their interactions, which facilitates visual comprehension and explainable reasoning. On the other hand, commonsense knowledge graphs are rich repositories that encode how the world is structured, and how general concepts interact. In this paper, we present a unified formulation of these two constructs, where a scene graph is seen as an image-conditioned instantiation of a commonsense knowledge graph. Based on this new perspective, we re-formulate scene graph generation as the inference of a bridge between the scene and commonsense graphs, where each entity or predicate instance in the scene graph has to be linked to its corresponding entity or predicate class in the commonsense graph. To this end, we propose a heterogeneous graph inference framework allowing to exploit the rich structure within the scene and commonsense at the same time. Through extensive experiments, we show the proposed method achieves significant improvement over the state of the art.

Recent years have witnessed the enormous success of low-dimensional vector space representations of knowledge graphs to predict missing facts or find erroneous ones. Currently, however, it is not yet well-understood how ontological knowledge, e.g. given as a set of (existential) rules, can be embedded in a principled way. To address this shortcoming, in this paper we introduce a framework based on convex regions, which can faithfully incorporate ontological knowledge into the vector space embedding. Our technical contribution is two-fold. First, we show that some of the most popular existing embedding approaches are not capable of modelling even very simple types of rules. Second, we show that our framework can represent ontologies that are expressed using so-called quasi-chained existential rules in an exact way, such that any set of facts which is induced using that vector space embedding is logically consistent and deductively closed with respect to the input ontology.

Knowledge Graph Embedding methods aim at representing entities and relations in a knowledge base as points or vectors in a continuous vector space. Several approaches using embeddings have shown promising results on tasks such as link prediction, entity recommendation, question answering, and triplet classification. However, only a few methods can compute low-dimensional embeddings of very large knowledge bases. In this paper, we propose KG2Vec, a novel approach to Knowledge Graph Embedding based on the skip-gram model. Instead of using a predefined scoring function, we learn it relying on Long Short-Term Memories. We evaluated the goodness of our embeddings on knowledge graph completion and show that KG2Vec is comparable to the quality of the scalable state-of-the-art approaches and can process large graphs by parsing more than a hundred million triples in less than 6 hours on common hardware.