All Questions
Tagged with it.information-theory graph-theory
24 questions
15
votes
7
answers
3k
views
Compressing Graphs (Kolmogorov complexity of graphs)
What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
user3409
10
votes
1
answer
421
views
How sensitive are Neural Networks to weight change?
Let's consider the space of feedforward neural networks with a given structure: $L$ layers, $m$ neurons per layer, ReLu activation, input dimension $d$, output dimension $k$.
Which means I'm ...
- 899
9
votes
2
answers
9k
views
If graph is tree what can be said about its adjacency matrix ?
Question If graph is tree what can be said about its adjacency matrix ? And vice versa ?
Especially I am interested in case when graph is bipartite graph.
Such graphs are related to error-...
- 24.9k
9
votes
1
answer
1k
views
Lovasz theta function and independence number of product of simple odd-cycles
Lovasz theta function $\vartheta(G)$ of a graph $G$ provides an upper bound for the independence number of a graph, $\alpha(G)$ and $\Theta(G) = \lim_{k\rightarrow \infty}\sqrt[k]{\alpha(G^{k})}$. ...
- 13.9k
9
votes
0
answers
245
views
De Bruijn sequence inside De Bruijn sequence
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...
- 12.3k
8
votes
1
answer
1k
views
When the Lovász theta-function saturates its upper bound
The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $...
user3409
7
votes
3
answers
330
views
Quantifying the noninvertibility of a function
Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
- 19.7k
5
votes
1
answer
613
views
Lovász theta and circulant graphs
Let $\theta(G)$ denote the Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be the Lovász upper bound for $\theta(G)$.
Let $C_{2n+1}$ denote the cycle graph with $2n+1$ nodes.
We know the ...
- 13.9k
4
votes
2
answers
2k
views
Simple uses for the Entropy bound on the volume of a Hamming ball
I'm a teaching assistant in an introductory course of Information Theory. I intend to prove the following well-known fact that easily proven using elementary information theoretic consideration:
$\...
- 337
3
votes
1
answer
376
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
3
votes
1
answer
186
views
Capacity of Cycle Graphs
Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.
It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite ...
- 13.9k
3
votes
0
answers
115
views
Maximum number of $4$-cycles
Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
- 13.9k
2
votes
2
answers
390
views
Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?
Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}).
Where number of variables is bigger than equations - so we have many solutions $x$.
Question How to estimate ...
- 24.9k
2
votes
1
answer
160
views
Do product distributions (or graph products) eventually cluster as more products are taken?
Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
2
votes
0
answers
72
views
How effective is using local property to test Shannon capacity?
A key tool in graph theory is the laplacian which is a local property. We can form a semidefinite programming and get an upper bound for Shannon capacity using laplacian.
Shannon capacity is ...
- 13.9k
2
votes
0
answers
240
views
Is there an universal (dis)similarity measure between two structures?
I'm always wondering is there an universal (dis)similarity measure
between two structures (let's say between two undirected simple
graphs)? I mean, not "the measure with universal parameter that we
...
- 345
2
votes
0
answers
605
views
Adjacency matrices of graphs as parity check matrices of error correcting codes
Consider bipartite graph.
Consider its adjacency matrix.
It will have a form
0 A^t
A 0
Take matrix $A$.
Consider the null-space $L$ of $A$ over $F_2^N$.
Question Can we say something about the $...
- 24.9k
1
vote
1
answer
247
views
Uniquely describing a graph
According to answers here https://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its ...
user76479
1
vote
2
answers
537
views
Is this general form of Lovasz theta function of circulant graphs?
Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by:
$\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?
...
- 13.9k
1
vote
1
answer
82
views
Channel Capacity & Dependency Graph
A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$.
Assume the ...
- 115
1
vote
0
answers
86
views
Min-sum belief propagation not working on a chain model with equal unary potentials
Given is a chain factor graph as presented in the image below with the following properties:
Each node can take values 0 or 1
All unary potentials are equal (e.g. $U(a)=0$) for every node $a$
All ...
0
votes
2
answers
251
views
Form of the Shannon capacity for Heptagon?
Is the $0$-error capacity of $7$-cycle:
$(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?
- 13.9k
0
votes
1
answer
413
views
Is there any relationship between a tree(graph theory) and semi-metric?
suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
- 243
0
votes
0
answers
120
views
Is there an existing problem related to inferring a hidden node in a graph from its neighbors
My original question was a bit too ambiguous, so I updated it as follows:
Consider a graph $G=(V,E)$. A vertex in $G$ is chosen uniformly at random; then a neighbor $x$ of $v$ is chosen uniformly at ...
- 109