Geometrical embeddings of graphs

Discrete MathematicsPublished 1 January 1989

Jan Reiterman, V. Rödl, E. Šinˇajová

DOI10.1016/0012-365x(89)90142-8

Source URL

Citations37

SJR quartileQ1

SJR score0.88

SNIP1.18

TL;DR

Abstract

The scalar product dimension d(G) of a graph G is defined to be the minimum number m such that the vertices x of G can be represented by vectors x¯∈ RM with the property that xy is an edge of G iffx¯y¯⩾ t for some real threshold t. Graphs G with d(G) = 1 are characterized and d(G) is determined for a variety of graphs. The dimension is compared with the (related and well-known) threshold dimension. Two other variants (spherical and distance dimensions) are considered. Upper bounds for graphs with small maximum degree (or with small maximum degree of the complement) are established.

Keywords

Computer ScienceMathematics

Annals of discrete mathematicsAlgorithmic Graph Theory and Perfect Graphs

3,787 Citations2004

IEEE Transactions on Information TheoryOn the Shannon capacity of a graph

1,658 Citations1979László Lovász

It is proved that the Shannon zero-error capacity of the pentagon is \sqrt{5} and a well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases.

Annals of discrete mathematicsAggregation of Inequalities in Integer Programming

453 Citations1977Václav Chvátal, Peter L. Hammer

An algorithm for answering the question whether there is a single linear inequality in O(m$n^2) steps whose zero-one solutions are precisely the zero- one solutions ofunderset\tilde to A, A to x, and e to e.

SIAM Journal on Algebraic and Discrete MethodsThe Complexity of the Partial Order Dimension Problem

404 Citations1982Mihalis Yannakakis

Journal of Computer and System SciencesProbabilistic communication complexity

125 Citations1986Ramamohan Paturi, Janoš Šimon

The logarithmic lower bound on communication complexity is applied to obtain an Ω(n log n) bound on the time of 1-tape unbounded error probabilistic Turing machines, believed to be the first nontrivial lower bound obtained for such machines.

Geometrical realization of set systems and probabilistic communication complexity

105 Citations1985Noga Alon, Péter Frankl +1 more

It is shown that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon.

MathematikaOn the dimension of a graph

98 Citations1965P. Erdös, Frank Harary +1 more

Discrete Applied MathematicsSpace graphs and sphericity

51 Citations1984Hiroshi Maehara

The sphericity of a graph G is defined to be the minimum number n such that G is isomorphic to a space graph in n-space.

Probabilistic Communication Complexity

28 Citations2005Ramamohan Paturi, Janoš Šimon

This work proves that a certain language requires /spl Omega/(nlogn) time to be recognized by a 1-tape (unbounded error) probabilistic Turing machine, and believes that this is the first nontrivial lower bound on the time required by unrestricted probabilism Turing machines.

European Journal of CombinatoricsEmbedding the n-cube in Lower Dimensions

9 Citations1986Péter Frankl, Hiroshi Maehara

It is proved that (1 + o(1)) n /log 2 n m ( n ) 2 3+o(1) n / log 2 n holds.