The fiber dimension of a graph

DOI10.1016/J.DISC.2018.09.021zbMATH Open1400.05161arXiv1601.04527OpenAlexW2962682564MaRDI QIDQ1618232FDOQ1618232

Authors: Tobias Windisch 

Publication date: 13 November 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Graphs on integer points of polytopes whose edges come from a set of allowed differences are studied. It is shown that any simple graph can be embedded in that way. The minimal dimension of such a representation is the fiber dimension of the given graph. The fiber dimension is determined for various classes of graphs and an upper bound in terms of the chromatic number is stated.

Full work available at URL: https://arxiv.org/abs/1601.04527

Recommendations

• On the dimension of a graph
• Embeddings of graphs in Euclidean spaces
• The dimension of a graph
• The dimension of a graph
• The Fibonacci dimension of a graph

zbMATH Keywords

lattice polytopesgraph embeddinggraph dimensionMarkov basesfiber graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• The on-line encyclopedia of integer sequences
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Lectures on algebraic statistics
• Lattice polytopes with distinct pair-sums
• Lattice 3-polytopes with few lattice points
• Bounds for Lattice Polytopes Containing a Fixed Number of Interior Points in a Sublattice
• Lectures on Polytopes
• Title not available (Why is that?)
• Every planar map is four colorable. I: Discharging
• Expander graphs and their applications
• On the foundations of linear and integer linear programming I
• Algebraic and geometric ideas in the theory of discrete optimization
• A polynomial oracle-time algorithm for convex integer minimization
• Algebraic algorithms for sampling from conditional distributions
• The Fibonacci dimension of a graph
• Realizability of graphs and linkages
• On the dimension of a graph
• Title not available (Why is that?)
• Running Markov chain without Markov basis
• On the Volume of Lattice Polyhedra
• Enumerating lattice 3-polytopes
• The lattice dimension of a graph
• Lattice embeddings of trees
• The strong isometric dimension of finite reflexive graphs
• On the Euclidean dimension of a wheel
• Embeddings of graphs
• On the counting function of primitive sets of integers.
• On connectivity of fibers with positive marginals in multiple logistic regression
• On the connectivity of fiber graphs
• On a Problem of Erdos Concerning Primitive Sequences
• Primitive sequences whose elements have no large prime factors

Cited In (1)

• The norm of the saturation of a binomial ideal, with applications to Markov bases

Uses Software

• OEIS

This page was built for publication: The fiber dimension of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1618232)