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

A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. A full house is a graph composed by a vertex adjacent to both ends of an edge in $K_4$ . Let $H$ be the complement of a cycle on 7 vertices. Chudnovsky et al [6] proved that every (odd hole, $K_4$)-free graph is 4-colorable and is 3-colorable if it does not has $H$ as an induced subgraph. In this paper, we use the proving technique of Chudnovsky et al to generalize this conclusion to (odd hole, full house)-free graphs, and prove that for (odd hole, full house)-free graph $G$, $\chi(G)\le \omega(G)+1$, and the equality holds if and only if $\omega(G)=3$ and $G$ has $H$ as an induced subgraph.

In 1971, Tutte wrote in an article that "it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian". Motivated by this remark, Horton constructed a counterexample on 96 vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts -- even if they have girth 6 -- it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs. In 1969, Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette's conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes closed under taking induced subgraphs in which this condition is also sufficient, which we call $(tw,\omega)$-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $(tw,\omega)$-bounded. Our results yield an infinite family of $\chi$-bounded induced-minor-closed graph classes and imply that the class of $1$-perfectly orientable graphs is $(tw,\omega)$-bounded, leading to linear-time algorithms for $k$-coloring $1$-perfectly orientable graphs for every fixed~$k$. This answers a question of Bre\v sar, Hartinger, Kos, and Milani{\v c} from 2018 and one of Beisegel, Chudnovsky, Gurvich, Milani{\v c}, and Servatius from 2019, respectively. We also reveal some further algorithmic implications of $(tw,\omega)$-boundedness related to list $k$-coloring and clique problems. In addition, we propose a question about the complexity of the maximum weight independent set problem in $(tw,\omega)$-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor.

Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on $n$ vertices and $m$ edges. In the first (edge-independent) model, a random hypergraph $H_1$ is constructed by fixing a parameter $p$ and allowing each of the $n$ vertices to join each of the $m$ edges independently with probability $p$. In the parameter range in which $pn \rightarrow \infty$ and $pm \rightarrow \infty$, we show that with high probability (w.h.p.) $H_1$ has discrepancy at least $\Omega(2^{-n/m} \sqrt{pn})$ when $m = O(n)$, and at least $\Omega(\sqrt{pn \log\gamma })$ when $m \gg n$, where $\gamma = \min\{ m/n, pn\}$. In the second (edge-dependent) model, $d$ is fixed and each vertex of $H_2$ independently joins exactly $d$ edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with $p=d/m$. Namely, for $d \rightarrow \infty$ and $dn/m \rightarrow \infty$, we prove that w.h.p. $H_{2}$ has discrepancy at least $\Omega(2^{-n/m} \sqrt{dn/m})$ when $m = O(n)$, and at least $\Omega(\sqrt{(dn/m) \log\gamma})$ when $m \gg n$, where $\gamma =\min\{m/n, dn/m\}$. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when $p=d/m$), in the dense regime of $m \gg n$. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that w.h.p. $H_{1}$ and $H_{2}$ each have discrepancy $O( \sqrt{dn/m} \log(m/n))$, provided $d \rightarrow \infty$, $d n/m \rightarrow \infty$ and $m \gg n$. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from $\Theta(\sqrt{d})$ to $o(\sqrt{d})$ as $m$ varies from $m=\Theta(n)$ to $m \gg n$.

We construct and analyze a CutFEM discretization for the Stokes problem based on the Scott-Vogelius pair. The discrete piecewise polynomial spaces are defined on macro-element triangulations which are not fitted to the smooth physical domain. Boundary conditions are imposed via penalization through the help of a Nitsche-type discretization, whereas stability with respect to small and anisotropic cuts of the bulk elements is ensured by adding local ghost penalty stabilization terms. We show stability of the scheme as well as a divergence--free property of the discrete velocity outside an $O(h)$ neighborhood of the boundary. To mitigate the error caused by the violation of the divergence-free condition, we introduce local grad-div stabilization. The error analysis shows that the grad-div parameter can scale like $O(h^{-1})$, allowing a rather heavy penalty for the violation of mass conservation, while still ensuring optimal order error estimates.

Manifold learning techniques for nonlinear dimension reduction assume that high-dimensional feature vectors lie on a low-dimensional manifold, then attempt to exploit manifold structure to obtain useful low-dimensional Euclidean representations of the data. Isomap, a seminal manifold learning technique, is an elegant synthesis of two simple ideas: the approximation of Riemannian distances with shortest path distances on a graph that localizes manifold structure, and the approximation of shortest path distances with Euclidean distances by multidimensional scaling. We revisit the rationale for Isomap, clarifying what Isomap does and what it does not. In particular, we explore the widespread perception that Isomap should only be used when the manifold is parametrized by a convex region of Euclidean space. We argue that this perception is based on an extremely narrow interpretation of manifold learning as parametrization recovery, and we submit that Isomap is better understood as constructing Euclidean representations of geodesic structure. We reconsider a well-known example that was previously interpreted as evidence of Isomap's limitations, and we re-examine the original analysis of Isomap's convergence properties, concluding that convexity is not required for shortest path distances to converge to Riemannian distances.

Can every connected graph burn in $\lceil \sqrt{n} \rceil $ steps? While this conjecture remains open, we prove that it is asymptotically true when the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. In fact, we prove that the conjecture for graphs of bounded growth boils down to a finite number of cases. Through an improved (but still weaker) bound for all trees, we argue that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best lower bound was $23$.

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs~$G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i, -i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert > 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model.

In order to facilitate the accesses of general users to knowledge graphs, an increasing effort is being exerted to construct graph-structured queries of given natural language questions. At the core of the construction is to deduce the structure of the target query and determine the vertices/edges which constitute the query. Existing query construction methods rely on question understanding and conventional graph-based algorithms which lead to inefficient and degraded performances facing complex natural language questions over knowledge graphs with large scales. In this paper, we focus on this problem and propose a novel framework standing on recent knowledge graph embedding techniques. Our framework first encodes the underlying knowledge graph into a low-dimensional embedding space by leveraging generalized local knowledge graphs. Given a natural language question, the learned embedding representations of the knowledge graph are utilized to compute the query structure and assemble vertices/edges into the target query. Extensive experiments were conducted on the benchmark dataset, and the results demonstrate that our framework outperforms state-of-the-art baseline models regarding effectiveness and efficiency.

This paper focuses on the discrimination capacity of aggregation functions: these are the permutation invariant functions used by graph neural networks to combine the features of nodes. Realizing that the most powerful aggregation functions suffer from a dimensionality curse, we consider a restricted setting. In particular, we show that the standard sum and a novel histogram-based function have the capacity to discriminate between any fixed number of inputs chosen by an adversary. Based on our insights, we design a graph neural network aiming, not to maximize discrimination capacity, but to learn discriminative graph representations that generalize well. Our empirical evaluation provides evidence that our choices can yield benefits to the problem of structural graph classification.