Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
104
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Here we observe that list coloring in graph theory coincides with the zero-temperature antiferromagnetic Potts model with an external field. We give a list coloring polynomial that equals the partition function in this case. This is analogous to the well-known connection between the chromatic polynomial and the zero-temperature, zero-field, antiferromagnetic Potts model. The subsequent cross fertilization yields immediate results for the Potts model and suggests new research directions in list coloring.
rate research
Read More
Motivated by the ErdH{o}s-Faber-Lovasz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We discuss several conjectures for list edge coloring linear hypergraphs that generalize both EFL and Vizings theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the list edge chromatic number is at most 2 times the maximum degree plus 1. We show that for sufficiently large fixed rank and sufficiently large degree, the conjectures are true.
An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $min{r, deg_G(v) }$ distinct colors in $N_G(v)$. The $r$-dynamic chromatic number $chi_r^d(G)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list $r$-dynamic chromatic number of a graph $G$ is denoted by $ch_r^d(G)$. Loeb et al. $[11]$ showed that $ch_3^d(G)leq 10$ for every planar graph $G$, and there is a planar graph $G$ with $chi_3^d(G)= 7$. In this paper, we study a special class of planar graphs which have better upper bounds of $ch_3^d(G)$. We prove that $ch_3^d(G) leq 6$ if $G$ is a planar graph which is near-triangulation, where a near-triangulation is a planar graph whose bounded faces are all 3-cycles.
The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V-polynomial, which lifts the classical relationship between the Tutte polynomial and the zero field Potts model to encompass external magnetic fields. The V-polynomial generalizes Nobel and Welshs W-polynomial, which extends the Tutte polynomial by incorporating vertex weights and adapting contraction to accommodate them. We prove that the variable field Potts model partition function (with its many specializations) is an evaluation of the V-polynomial, and hence a polynomial with deletion-contraction reduction and Fortuin-Kasteleyn type representation. This unifies an important segment of Potts model theory and brings previously successful combinatorial machinery, including complexity results, to bear on a wider range of statistical mechanics models.
We summarize here the results, most of which are preliminary, of a number of recent observations of the Crab nebula system with the Chandra X-Ray Observatory. We discuss four different topics: (1) The motion on long (> 1yr) time scales of the southern jet. (2) The discovery that pulsar is not at the center of the projected ring on the sky and that the ring may well lie on the axis of symmetry but appears to be displaced at a latitude of about 5 degrees. (Note that this deprojection is by no means unique.) (3) The results and puzzling implications of the Chandra phase-resolved spectroscopy of the pulsar when compared to observations of pulse-phase variations of similar and dissimilar measures in other regions of the spectrum. (4) The search for the X-ray location of the site of the recently-discovered gamma-ray flaring. We also comment briefly on our plan to use the Chandra data we obtained for the previous project to study the nature of the low-energy flux variations recently detected at hard X-ray energies.
For a graph $G=(V,E)$, $kin mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as [ {bf Z}(G;k,w):=sum_{phi:Vto [k]}prod_{substack{uvin E phi(u)=phi(v)}}w, ] where $[k]:={1,ldots,k}$. In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any $Deltain mathbb{N}$ and any $kgeq eDelta+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${bf Z}(G;k,w) eq 0$ for any $win U$ and any graph $G$ of maximum degree at most $Delta$. (Here $e$ denotes the base of the natural logarithm.) For small values of $Delta$ we are able to give better results. As an application of our results we obtain improved bounds on $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$-colourings of graphs of small maximum degree.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
