graph-theory   1227

« earlier    

[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
algorithms  graph-theory  read2of 
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
graph-theory  math  read2of 
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
algorithms  graph-theory  programming-practice  puzzle  read2of 
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
graph-theory  math  read2of 
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
functional-programming  graph-theory  read2of 
july 2018 by xenocid

« earlier    

related tags

`  agent-based  ai  algebra  algo  algorithm  algorithms-explained  algorithms  anomaly-detection  api  approximation  art  article  aubrey-de-grey  aubrey_de_grey  automata  benchmark  big-data  biology  blog  book  books  boolean-networks  brain-scan  brueckner-networks  cellular-automata  chip-firing  chromatic  classification  clojure  clustering  code  cog-psych  cohesion  collective-intelligence  colors  combinatorics  commercial  complex-systems  complexology  composition-decomposition  compsci  computational-complexity  computational-geometry  computerscience  consider:classification  consider:feature-discovery  consider:find-shape-for-points  consider:inverse-problem  consider:looking-to-see  consider:mathematical-recreation  consider:out-of-box  consider:performance-measures  consider:rediscovery  consider:representation  consider:simulation  constraint-satisfaction  continued-fractions  d3.js  d3  d3js  data-structures  database  databases  dataset  db  detail-architecture  dev  dimension-reduction  discussion  distance-measures  distance  distributed  diversity  dynamical-systems  ecology  eden  emergence  enumeration  esoteric  evolution  evopsych  experimental-design  explanation  feature-construction  feature-extraction  food-webs  fractals  functional-programming  futurology  game-theory  game  games  giants  graph-coloring  graph-database  graph-layout  graph-partitioning  graph-search  graph  graphdb  graphics  graphql  graphs  graphtheory  hacker-news  haskell  heuristics  horse-races  hypergraphs  ideas  inference  insight  inspiration  intelligence  interactive  interview  intro  introduction  js  json  learning  library  looking-to-see  math  mathematical-recreations  mathematics  matrices  metrics  model  models  mooc  neo4j  network-models  network-structure  network-theory  neuro-nitgrit  neuro  nitty-gritty  nonlinear-dynamics  nudge-targets  number-theory  number  online  opensource  operations-research  optimization  path  pattern-formation  pdf  performance-measure  performance  philosophy  phylogenetics  plane-geometry  planning  probability-theory  programming-practice  programming  proof  psych-architecture  psychology  purdy-pitchers  puzzle  querying  random-walks  rather-interesting  react  read2of  reading  recursion  reduction  reference  representation  research  rewriting-systems  rigidity  robustness  ruby  sandpiles  serialization  service  set-theory  sorting  spark  specification  speculation  stamp-collecting  standards  statistics  streaming  strings  structure  study  symmetry  systematic-ad-hoc  teal  theoretical-biology  tiling  to-cartoon-about  to-read  to-simulate  to-understand  to-w  to-write-about  to-write  topology  tutorial  tutorials  visualization  whole-partial-many  wiki 

Copy this bookmark:



description:


tags: