Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
57
0
0.0
(
0
)
Added by
Jess Banks
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove that in sparse ErdH{o}s-R{e}nyi graphs of average degree $d$, the vector chromatic number (the relaxation of chromatic number coming from the Lov`{a}sz theta function) is typically $tfrac{1}{2}sqrt{d} + o_d(1)$. This fits with a long-standing conjecture that various refutation and hypothesis-testing problems concerning $k$-colorings of sparse ErdH{o}s-R{e}nyi graphs become computationally intractable below the `Kesten-Stigum threshold $d_{KS,k} = (k-1)^2$. Along the way, we use the celebrated Ihara-Bass identity and a carefully constructed non-backtracking random walk to prove two deterministic results of independent interest: a lower bound on the vector chromatic number (and thus the chromatic number) using the spectrum of the non-backtracking walk matrix, and an upper bound dependent only on the girth and universal cover. Our upper bound may be equivalently viewed as a generalization of the Alon-Boppana theorem to irregular graphs
rate research
Read More
We derive upper and lower bounds on the degree $d$ for which the Lovasz $vartheta$ function, or equivalently sum-of-squares proofs with degree two, can refute the existence of a $k$-coloring in random regular graphs $G_{n,d}$. We show that this type of refutation fails well above the $k$-colorability transition, and in particular everywhere below the Kesten-Stigum threshold. This is consistent with the conjecture that refuting $k$-colorability, or distinguishing $G_{n,d}$ from the planted coloring model, is hard in this region. Our results also apply to the disassortative case of the stochastic block model, adding evidence to the conjecture that there is a regime where community detection is computationally hard even though it is information-theoretically possible. Using orthogonal polynomials, we also provide explicit upper bounds on $vartheta(overline{G})$ for regular graphs of a given girth, which may be of independent interest.
A wide variety of complex networks (social, biological, information etc.) exhibit local clustering with substantial variation in the clustering coefficient (the probability of neighbors being connected). Existing models of large graphs capture power law degree distributions (Barabasi-Albert) and small-world properties (Watts-Strogatz), but only limited clustering behavior. We introduce a generalization of the classical ErdH{o}s-Renyi model of random graphs which provably achieves a wide range of desired clustering coefficient, triangle-to-edge and four-cycle-to-edge ratios for any given graph size and edge density. Rather than choosing edges independently at random, in the Random Overlapping Communities model, a graph is generated by choosing a set of random, relatively dense subgraphs (communities). We discuss the explanatory power of the model and some of its consequences.
We show that for every prime $d$ and $alphain (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2alpha log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by $(3/sqrt{2})sqrt{d}$, and many eigenvectors fully localized on small sets of size $O(|V|^alpha)$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the scarring phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of ErdH{o}s and Sachs for constructing high girth regular graphs.
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and sufficiently high degree, we prove the NP-completeness of acyclic r-colorings; our method also implies the known analogue for classical colorings. The proofs use high girth graphs with high arboricity and dichromatic numbers. High girth graphs and digraphs with high chromatic and dichromatic numbers have been well studied; we re-derive the results from a general result about relational systems, which also implies the similar fact about high girth and high arboricity used in the proofs. These facts concern graphs and digraphs of high girth and low degree; we contrast them by considering acyclic colorings of tournaments (which have low girth and high degree). We prove that even though acyclic two-colorability of tournaments is known to be NP-complete, random acyclically r-colorable tournaments allow recovering an acyclic r-coloring in deterministic linear time, with high probablity.
Barnette identified two interesting classes of cubic polyhedral graphs for which he conjectured the existence of a Hamiltonian cycle. Goodey proved the conjecture for the intersection of the two classes. We examine these classes from the point of view of distance-two colorings. A distance-two $r$-coloring of a graph $G$ is an assignment of $r$ colors to the vertices of $G$ so that any two vertices at distance at most two have different colors. Note that a cubic graph needs at least four colors. The distance-two four-coloring problem for cubic planar graphs is known to be NP-complete. We claim the problem remains NP-complete for tri-connected bipartite cubic planar graphs, which we call type-one Barnette graphs, since they are the first class identified by Barnette. By contrast, we claim the problem is polynomial for cubic plane graphs with face sizes $3, 4, 5,$ or $6$, which we call type-two Barnette graphs, because of their relation to Barnettes second conjecture. We call Goodey graphs those type-two Barnette graphs all of whose faces have size $4$ or $6$. We fully describe all Goodey graphs that admit a distance-two four-coloring, and characterize the remaining type-two Barnette graphs that admit a distance-two four-coloring according to their face size. For quartic plane graphs, the analogue of type-two Barnette graphs are graphs with face sizes $3$ or $4$. For this class, the distance-two four-coloring problem is also polynomial; in fact, we can again fully describe all colorable instances -- there are exactly two such graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
