graph-theory   1227
[1807.08178] DP-Colorings of Hypergraphs
Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m2(r) (respectively, m∗2(r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are
c⋅r/logr‾‾‾‾‾‾√⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m∗2(r)⩽C′⋅r4⋅4r,
for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m̃2(r) (respectively, m̃∗2(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m̃2(r)⩽m2(r) and m̃∗2(r)⩽m∗2(r).
While the proof of the bound m∗2(r)=Ω(r−34r) due to Erdős and Lovász also works for m̃∗2(r), we show that the trivial lower bound m̃2(r)⩾2r−1 is asymptotically tight, i.e., m̃2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m̃2(r)⩾2r−1 is not sharp, i.e., m̃2(r)⩾2r−1+1. Whether this result holds for any odd r remains an open problem. Nevertheless, we find it tempting to conjecture that the difference m̃2(r)−2r−1 tends to infinity with r.
set-theory  hypergraphs  graph-theory  graph-coloring  combinatorics  rather-interesting  to-write-about
yesterday by Vaguery
[1806.01378] Strong Pseudo Transitivity and Intersection Graphs
A directed graph G=(V,E) is {\it strongly pseudo transitive} if there is a partition {A,E−A} of E so that graphs G1=(V,A) and G2=(V,E−A) are transitive, and additionally, if ab∈A and bc∈E implies that ac∈E. A strongly pseudo transitive graph G=(V,E) is strongly pseudo transitive of the first type, if ab∈A and bc∈E implies ac∈A. An undirected graph is co-strongly pseudo transitive (co-strongly pseudo transitive of the first type) if its complement has an orientation which is strongly pseudo transitive (co-strongly pseudo transitive of the first type). Our purpose is show that the results in computational geometry \cite{CFP, Lu} and intersection graph theory \cite{Ga2, ES} can be unified and extended, using the notion of strong pseudo transitivity. As a consequence the general algorithmic framework in \cite{Sh} is applicable to solve the maximum independent set in O(n3) time in a variety of problems, thereby, avoiding case by case lengthily arguments for each problem. We show that the intersection graphs of axis parallel rectangles intersecting a diagonal line from bottom, and half segments are co-strongly pseudo transitive. In addition, we show that the class of the interval filament graphs is co-strongly transitive of the first type, and hence the class of polygon circle graphs which is contained in the class of interval filament graphs (but contains the classes of chordal graphs, circular arc, circle, and outer planar graphs), and the class of incomparability graphs are strongly transitive of the first type. For class of chordal graphs we give two different proofs, using two different characterizations, verifying that they are co-strongly transitive of the first type. We present some containment results.
graph-theory  feature-extraction  feature-construction  algorithms  computational-complexity  nudge-targets  consider:feature-discovery
2 days ago by Vaguery
[1706.07900] Tree-Residue Vertex-Breaking: a new tool for proving hardness
In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the $k$ incident edges)?
We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard.
We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.
feature-construction  graph-theory  computational-complexity  rather-interesting  explanation  to-write-about
7 days ago by Vaguery
dash-network - D3 force-layout network diagram for Dash
This repository demonstrates the principles of combining D3 with React, using a D3 force-layout network graph as an example, and was created from the dash-component-boilerplate template. This component allows dynamically changing the nodes and links and their properties, and responding to clicks on individual nodes.
d3  graphs  graph-theory  JS  React  opensource  visualization
5 weeks ago by liqweed
[1810.10577] Cops and Robbers on Toroidal Chess Graphs
We investigate multiple variants of the game Cops and Robbers. Playing it on an n×n toroidal chess graph, the game is varied by defining moves for cops and robbers differently, always mimicking moves of certain chess pieces. In these cases, the cop number is completely determined.
graph-theory  games  rather-interesting  mathematical-recreations  feature-construction  to-write-about  to-simulate  nudge-targets  consider:classification
6 weeks ago by Vaguery
Greater speed in memory-bound graph algorithms with just straight C code – Daniel Lemire's blog
Greater speed in memory-bound graph algorithms with just straight C code - Added May 29, 2018 at 02:28PM
9 weeks ago by xenocid
The chromatic number of the plane, part 2: lower bounds | The Math Less Traveled
The chromatic number of the plane, part 2: lower bounds - Added May 03, 2018 at 02:57PM
9 weeks ago by xenocid
Focus on a Puzzle: There Is No Spoon - Episode 2
Focus on a Puzzle: There Is No Spoon – Episode 2 - Added April 25, 2018 at 02:05PM
9 weeks ago by xenocid
The chromatic number of the plane, part 1 | The Math Less Traveled
The chromatic number of the plane, part 1 - Added April 24, 2018 at 12:32PM
9 weeks ago by xenocid
[1804.03032] k-NN Graph Construction: a Generic Online Approach
Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues arise from many disciplines such as information retrieval, data-mining, machine learning and computer vision. Despite continuous efforts have been taken in the last several decades, these two issues remain challenging. They become more and more imminent given the big data emerges in various fields and has been expanded significantly over the years. In this paper, a simple but effective solution both for k-nearest neighbor search and k-nearest neighbor graph construction is presented. Namely, these two issues are addressed jointly. On one hand, the k-nearest neighbor graph construction is treated as a nearest neighbor search task. Each data sample along with its k-nearest neighbors are joined into the k-nearest neighbor graph by sequentially performing the nearest neighbor search on the graph under construction. On the other hand, the built k-nearest neighbor graph is used to support k-nearest neighbor search. Since the graph is built online, dynamic updating of the graph, which is not desirable from most of the existing solutions, is supported. Moreover, this solution is feasible for various distance measures. Its effectiveness both as a k-nearest neighbor construction and k-nearest neighbor search approach is verified across various datasets in different scales, various dimensions and under different metrics.
graph-theory  algorithms  to-understand  rather-interesting  computational-complexity  data-structures
9 weeks ago by Vaguery
d3-dag - Layout algorithms for visualizing directed acylic graphs
This module implements a data structures for manipulating DAGs that mimics the API of d3-hierarchy as much as possible.
d3  graphs  graph-theory  opensource  visualization  algorithms
september 2018 by liqweed
Unigraph – The world's largest Knowledge Graph
Creating the infrastructure and building the web of interconnected data, a datasource at the time. Innovative approach to big data storage and retrieval combined with the best practices in evolving ontology design power the distributed Knowledge Graph of the future and its real-time data API.
dataset  API  graph-theory  GraphQL  online  service  querying
august 2018 by liqweed
sarah-marie belcastro's personal site
she's a mathematician (topological graph theorist (studies how meshy things act on shapey things)). her site is full of useful information ranging from lists of cool things on the internet to her research papers and dissertation (as you find on these types of sites) to a list of teal-haired female mathematicians to tutorials about graph theory to mathematical knitting
mathematics  blog  graph-theory  topology  teal  art
august 2018 by abstresma
Functional programming with graphs
Functional programming with graphs - Added December 21, 2017 at 02:49PM