Name
Abstract | ||
|---|---|---|
The Nesetril--Pultr dimension of the Kneser graph is interpreted as the shortest length of strings over an infinite alphabet representing the vertices of the graph so that the absence of coincidences in the codewords of a pair of vertices is equivalent to adjacency, i.e., to the two underlying sets being disjoint. We study analogous but more demanding representations in case the alphabet size may be limited and yet the full intersection has to be determined from the coincidences. Our results introduce a connection between extremal set theory and zero-error problems in multiterminal source coding in the Shannon sense. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S0895480198348343 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
full intersection,alphabet size,infinite alphabet,pultr dimension,shannon sense,shortest length,extremal set theory,kneser graph,demanding representation,compact representations,finite sets,intersection structure,multiterminal source,dimension | Graph theory,Adjacency list,Discrete mathematics,Combinatorics,Finite set,Disjoint sets,Vertex (geometry),Distance,Intersection graph,Kneser graph,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 2 | 0895-4801 |
Citations | PageRank | References |
1 | 0.41 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Körner | 1 | 9 | 2.08 |
| Angelo Monti | 2 | 671 | 46.93 |