**graph-theory**1227

[1807.08178] DP-Colorings of Hypergraphs

yesterday by Vaguery

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
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.

yesterday by Vaguery

[1806.01378] Strong Pseudo Transitivity and Intersection Graphs

2 days ago by Vaguery

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

7 days ago by Vaguery

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
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.

7 days ago by Vaguery

dash-network - D3 force-layout network diagram for Dash

5 weeks ago by liqweed

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

6 weeks ago by Vaguery

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

9 weeks ago by xenocid

Greater speed in memory-bound graph algorithms with just straight C code - Added May 29, 2018 at 02:28PM

algorithms
graph-theory
read2of
9 weeks ago by xenocid

The chromatic number of the plane, part 2: lower bounds | The Math Less Traveled

9 weeks ago by xenocid

The chromatic number of the plane, part 2: lower bounds - Added May 03, 2018 at 02:57PM

graph-theory
math
read2of
9 weeks ago by xenocid

Focus on a Puzzle: There Is No Spoon - Episode 2

9 weeks ago by xenocid

Focus on a Puzzle: There Is No Spoon – Episode 2 - Added April 25, 2018 at 02:05PM

algorithms
graph-theory
programming-practice
puzzle
read2of
9 weeks ago by xenocid

The chromatic number of the plane, part 1 | The Math Less Traveled

9 weeks ago by xenocid

The chromatic number of the plane, part 1 - Added April 24, 2018 at 12:32PM

graph-theory
math
read2of
9 weeks ago by xenocid

[1804.03032] k-NN Graph Construction: a Generic Online Approach

9 weeks ago by Vaguery

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

september 2018 by liqweed

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

august 2018 by liqweed

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

John Williamson on Twitter: "First 1e6 integers, represented as binary vectors indicating their prime factors, and laid out using the sparse matrix support in @leland_mcinnes's UMAP dimensionality reduction algorithm. This is from a 1000000x78628 (!) bina

mathematics number-theory visualization rather-interesting graph-theory graph-layout dimension-reduction to-write-about

august 2018 by Vaguery

mathematics number-theory visualization rather-interesting graph-theory graph-layout dimension-reduction to-write-about

august 2018 by Vaguery

sarah-marie belcastro's personal site

august 2018 by abstresma

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

july 2018 by xenocid

Functional programming with graphs - Added December 21, 2017 at 02:49PM

functional-programming
graph-theory
read2of
july 2018 by xenocid

**related tags**

Copy this bookmark: