János Körner
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
János Körner has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Emanuela Fachini
La Sapienza" University of Rome Italy
10 shared publications - Gábor Simonyi
Department of Computer Science and Information Theory Alfréd Rényi Institute of Mathematics Budapest Hungary
7 shared publications - Gérard Cohen
Télécom ParisTech, department INFRES/MIC2, CNRS, UMR 5441
4 shared publications Emanuela Fachini
3 shared publications- Imre Csiszár
Mathematical Institute of the Hungarian Academy of Sciences
3 shared publications - Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
3 shared publications
Latest Publications
- Open Access
Structured Codes of Graphs
We investigate the maximum size of graph families on a common vertex set of cardinality $n$ such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of $n$ when the prescribed condition is connectivity or $2$-connectivity, Hamiltonicity or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.Open AccessStructured Codes of Graphs
We investigate the maximum size of graph families on a common vertex set of cardinality $n$ such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of $n$ when the prescribed condition is connectivity or $2$-connectivity, Hamiltonicity or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems. - 1 July 2020
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 173
Divergent permutations
- 1 July 2020
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 173
Divergent permutations
- Open Access
Divergent permutations
Two permutations of the natural numbers diverge if the absolute value of the difference of their elements in the same position goes to infinity. We show that there exists an infinite number of pairwise divergent permutations of the naturals. We relate this result to more general questions about the permutation capacity of infinite graphs.
Open AccessDivergent permutations
Two permutations of the natural numbers diverge if the absolute value of the difference of their elements in the same position goes to infinity. We show that there exists an infinite number of pairwise divergent permutations of the naturals. We relate this result to more general questions about the permutation capacity of infinite graphs.
- Open Access
Interlocked permutations
The zero-error capacity of channels with a countably infinite input alphabet formally generalises Shannon's classical problem about the capacity of discrete memoryless channels. We solve the problem for three particular channels. Our results are purely combinatorial and in line with previous work of the third author about permutation capacity.
Open AccessInterlocked permutations
The zero-error capacity of channels with a countably infinite input alphabet formally generalises Shannon's classical problem about the capacity of discrete memoryless channels. We solve the problem for three particular channels. Our results are purely combinatorial and in line with previous work of the third author about permutation capacity.
- 10 November 2017
- Published by Wiley in Journal of Graph Theory
- Vol. 88 (3) , 402-410
Families of locally separated Hamilton paths
We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.
- 10 November 2017
- Published by Wiley in Journal of Graph Theory
- Vol. 88 (3) , 402-410
Families of locally separated Hamilton paths
We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.
- 11 August 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (10) , 6344-6346
Hamilton Paths With Lasting Separation
We determine the asymptotics of the largest cardinality of a set of Hamilton paths in the complete graph with vertex set$[n]$ under the condition that for any two of the paths in the family there is a subpath of length$k$ entirely contained in only one of them and edge-disjoint from the other one.- 11 August 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (10) , 6344-6346
Hamilton Paths With Lasting Separation
We determine the asymptotics of the largest cardinality of a set of Hamilton paths in the complete graph with vertex set$[n]$ under the condition that for any two of the paths in the family there is a subpath of length$k$ entirely contained in only one of them and edge-disjoint from the other one.- Open Access
Hamilton paths with lasting separation
We determine the asymptotics of the largest cardinality of a set of Hamilton paths in the complete graph with vertex set [n] under the condition that for any two of the paths in the family there is a subpath of length k entirely contained in only one of them and edge{disjoint from the other one.
Open AccessHamilton paths with lasting separation
We determine the asymptotics of the largest cardinality of a set of Hamilton paths in the complete graph with vertex set [n] under the condition that for any two of the paths in the family there is a subpath of length k entirely contained in only one of them and edge{disjoint from the other one.
- 26 May 2016
- Published by Wiley in Journal of Graph Theory
- Vol. 85 (1) , 107-114
Path Separation by Short Cycles
- 26 May 2016
- Published by Wiley in Journal of Graph Theory
- Vol. 85 (1) , 107-114
Path Separation by Short Cycles
- Open Access
Path separation by short cycles
Two Hamilton paths in $K_n$ are separated by a cycle of length $k$ if their union contains such a cycle. For small fixed values of $k$ we bound the asymptotics of the maximum cardinality of a family of Hamilton paths in $K_n$ such that any pair of paths in the family is separated by a cycle of length $k.$Open AccessPath separation by short cycles
Two Hamilton paths in $K_n$ are separated by a cycle of length $k$ if their union contains such a cycle. For small fixed values of $k$ we bound the asymptotics of the maximum cardinality of a family of Hamilton paths in $K_n$ such that any pair of paths in the family is separated by a cycle of length $k.$ - 11 November 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (1) , 3-7
Zero-Error Capacity of Binary Channels With Memory
We begin a systematic study of the problem of the zero-error capacity of noisy binary channels with memory and solve some of the non-trivial cases.
- 11 November 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (1) , 3-7
Zero-Error Capacity of Binary Channels With Memory
We begin a systematic study of the problem of the zero-error capacity of noisy binary channels with memory and solve some of the non-trivial cases.