اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe number of triangles is more when they have no common vertex
71
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
By the theorem of Mantel $[5]$ it is known that a graph with $n$ vertices and $lfloor frac{n^{2}}{4} rfloor+1$ edges must contain a triangle. A theorem of ErdH{o}s gives a strengthening: there are not only one, but at least $lfloorfrac{n}{2}rfloor$ triangles. We give a further improvement: if there is no vertex contained by all triangles then there are at least $n-2$ of them. There are some natural generalizations when $(a)$ complete graphs are considered (rather than triangles), $(b)$ the graph has $t$ extra edges (not only one) or $(c)$ it is supposed that there are no $s$ vertices such that every triangle contains one of them. We were not able to prove these generalizations, they are posed as conjectures.
قيم البحث
اقرأ أيضاً
Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{lfloor n^2/4rfloor}$ for $n geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n geq 8$.
We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{lfloor n^2/4rfloor}$ such orientations.
Pathological science occurs when well-intentioned scientists spend extended time and resources studying a phenomena that isnt real. Researchers who get caught up in pathological science are usually following the scientific method and performing caref
ul experiments, but they get tricked by nature. The study of water has had several protracted episodes of pathological science, a few of which are still ongoing. We discuss four areas of pathological water science -polywater, the Mpemba effect, Pollacks fourth phase of water, and the effects of static magnetic fields on water. Some common water-specific issues emerge such as the contamination and confounding of experiments with dissolved solutes and nanobubbles. General issues also emerge such as imprecision in defining what is being studied, bias towards confirmation rather than falsification, and poor standards for reproducibility. We hope this work helps researchers avoid wasting valuable time and resources pursuing pathological science.
We study whether one can write a Matrix Product Density Operator (MPDO) as the Gibbs state of a quasi-local parent Hamiltonian. We conjecture this is the case for generic MPDO and give supporting evidences. To investigate the locality of the parent H
amiltonian, we take the approach of checking whether the quantum conditional mutual information decays exponentially. The MPDO we consider are constructed from a chain of 1-input/2-output (`Y-shaped) completely-positive maps, i.e. the MPDO have a local purification. We derive an upper bound on the conditional mutual information for bistochastic channels and strictly positive channels, and show that it decays exponentially if the correctable algebra of the channel is trivial. We also introduce a conjecture on a quantum data processing inequality that implies the exponential decay of the conditional mutual information for every Y-shaped channel with trivial correctable algebra. We additionally investigate a close but nonequivalent cousin: MPDO measured in a local basis. We provide sufficient conditions for the exponential decay of the conditional mutual information of the measured states, and numerically confirmed they are generically true for certain random MPDO.
Given an acyclic digraph $D$, the competition graph of $D$, denoted by $C(D)$, is the simple graph having vertex set $V(D)$ and edge set ${uv mid (u, w), (v, w) in A(D) text{ for some } w in V(D) }$. The phylogeny graph of an acyclic digraph $D$, den
oted by $P(D)$, is the graph with the vertex set $V(D)$ and the edge set $E(U(D)) cup E(C(D))$ where $U(D)$ denotes the underlying graph of $D$. The notion of phylogeny graphs was introduced by Roberts and Sheng~cite{roberts1997phylogeny} as a variant of competition graph. Moral graphs having arisen from studying Bayesian networks are the same as phylogeny graphs. In this paper, we integrate the existing theorems computing phylogeny numbers of connected graph with a small number of triangles into one proposition: for a graph $G$ containing at most two triangle, $ |E(G)|-|V(G)|-2t(G)+d(G)+1 le p(G) le |E(G)|-|V(G)|-t(G)+1 $ where $t(G)$ and $d(G)$ denote the number of triangles and the number of diamond in $G$, respectively. Then we show that these inequalities hold for graphs with many triangles. In the process of showing it, we derive a useful theorem which plays a key role in deducing various meaningful results including a theorem that answers a question given by Wu~{it et al.}~cite{Wu2019}.
In an edge-colored graph $(G,c)$, let $d^c(v)$ denote the number of colors on the edges incident with a vertex $v$ of $G$ and $delta^c(G)$ denote the minimum value of $d^c(v)$ over all vertices $vin V(G)$. A cycle of $(G,c)$ is called proper if any t
wo adjacent edges of the cycle have distinct colors. An edge-colored graph $(G,c)$ on $ngeq 3$ vertices is called properly vertex-pancyclic if each vertex of $(G,c)$ is contained in a proper cycle of length $ell$ for every $ell$ with $3 le ell le n$. Fujita and Magnant conjectured that every edge-colored complete graph on $ngeq 3$ vertices with $delta^c(G)geq frac{n+1}{2}$ is properly vertex-pancyclic. Chen, Huang and Yuan partially solve this conjecture by adding an extra condition that $(G,c)$ does not contain any monochromatic triangle. In this paper, we show that this conjecture is true if the edge-colored complete graph contain no joint monochromatic triangles.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
