12
This is not possible in general.
The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $1$ and those between the non-adjacent pairs must be $\sqrt{2}$).
Now consider the complete ...
8
As a first remark, your focus seems to be on hypergraphs but I think that most of the literature about embedding hypergraphs prefers to work with simplicial complexes. A good reference on these questions is this paper by Matousek, Tancer and Wagner.
Does Fáry's Theorem hold in higher dimension?
The answer is no.
There are actually 3 different notions ...
8
Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper:
http://www.cs.uiuc.edu/~jeffe/pubs/crum.html
This already implies that you can encode pretty nasty ...
5
Your construction does not work in general for the value of $k$ given.
Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have
$$
Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),
$$
for $k \ll d$. Of ...
4
Schnyder Theorem states that a graph is planar iff its incidence poset has dimension at most 3. This has been extended by Mendez to arbitrary simplicial complexes (see "Geometric Realization of Simplicial Complexes", Graph Drawing 1999: 323-332). Strangely enough there is a much older paper with a very similar title "The geometric realization of a semi-...
4
This paper by Keith Ball seems to be what you are looking for:
Ball, Keith. "Isometric embedding in $\ell_p$-spaces."
European Journal of Combinatorics 11.4 (1990): 305-311.
Link to the paper here:
https://www.sciencedirect.com/science/article/pii/S019566981380131X
3
Very important property : tree-width duality.
e.g look at :
Tree-width of hyper-graphs and surface duality
by Frederic Mazoit,
The abstract is as follow:
In Graph Minors III, Robertson and Seymour write: "It seems that the
tree- width of a planar graph and the tree-width of its geometric dual
are approximately equal, indeed, we have convinced ...
3
Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.
To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the ...
3
To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine edges are places where multiple cells meet so let's make them vertices as well.
Then, within each page of the book, the dual graph is a forest, with all vertices ...
2
I don't think we can get any property close to dual's properties in planar graphs, e.g Babai show that every graph can be embedded in a book with three pages (see Archdeacon's survey Theorem 5.1), so if $p$ is a duality property for books with three pages then $p$ holds for general graphs.
2
It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they assume $d \le n$, it suffices for $s$ to satisfy $s^2 \cdot d/2≥\ln(20n^2)$, which leads to $s=c\cdot d^{-1/2} \sqrt{\log n}$ for some appropriately chosen ...
1
I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is "Learning a kernel matrix for nonlinear dimensionality reduction" by Weinberger, Sha, and Saul if I am not ...
Only top voted, non community-wiki answers of a minimum length are eligible
