The fiber dimension of a graph

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

Authors Tobias Windisch

Publication date 13 November 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(2)

• The norm of the saturation of a binomial ideal, with applications to Markov bases
• On the connectivity of fiber graphs

Describes a project that uses

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)