All Questions
Tagged with graph-theory it.information-theory
7 questions with no upvoted or accepted answers
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
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
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
604
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
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
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