Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeciding whether there are infinitely many prime graphs with forbidden induced subgraphs
76
0
0.0
(
0
)
Added by
Sang-il Oum
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A homogeneous set of a graph $G$ is a set $X$ of vertices such that $2le lvert Xrvert <lvert V(G)rvert$ and no vertex in $V(G)-X$ has both a neighbor and a non-neighbor in $X$. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.
rate research
Read More
Dirichlets proof of infinitely many primes in arithmetic progressions was published in 1837, introduced L-series for the first time, and it is said to have started rigorous analytic number theory. Dirichlet uses Eulers earlier work on the zeta function and the distribution of primes. He first proves a simpler case before going to full generality. The paper was translated from German by R. Stephan and given a reference section.
We discuss the uniqueness or non-uniqueness problem of the decomposition of the gluon field into the physical and pure-gauge components, which is the basis of the recently proposed two physically inequivalent gauge-invariant decompositions of the nucleon spin. It is crucialy important to recognize the fact that the standard gauge fixing procedure is essentially a process of projecting out the physical components of the massless gauge field. A complexity of the nonabelian gauge theory as compared with the abelian case is that a closed expression for the physical component can be given only with use of the non-local Wilson line, which is generally path-dependent. It is known that, by choosing an infinitely long straight-line path in space and time, the direction of which is characterized by a constant 4-vector $n^mu$, one can cover a class of gauge called the general axial gauge, containing three popular gauges, i.e. the temporal, the light-cone, and the spatial axial gauge. Within this general axial gauge, we have calculated the 1-loop evolution matrix for the quark and gluon longitudinal spins in the nucleon. We found that the final answer is exactly the same independently of the choices of $n^mu$, which amounts to proving the gauge-independence and path-independence simultaneously, although within a restricted class of gauges and paths. By drawing on all of these findings together with well-established knowledge from gauge theories, we argue against the rapidly spreading view in the community that there are infinitely many decompositions of the nucleon spin.
We argue against the rapidly spreading idea of gauge-invariant-extension (GIE) approach in the nucleon spin decomposition problem, which implies the existence of infinitely many gauge-invariant decomposition of the nucleon spin.
A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.
A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvatal conjectured in 2008 that a similar result can be achieved in the broader context of finite metric spaces. This conjecture remains open even for graph metrics. In this article we prove that graphs with no induced house nor induced cycle of length at least~5 verify the desired property. We focus on lines generated by vertices at distance at most 2, define a new notion of ``good pairs that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
