Alfred Renyi Institute of Mathematics

Budapest, Hungary

Alfred Renyi Institute of Mathematics

Budapest, Hungary
Time filter
Source Type

FUREDI Z.,Alfred Renyi Institute of Mathematics | MALEKI Z.,Isfahan University of Technology
Combinatorics Probability and Computing | Year: 2017

We give an asymptotic formula for the minimum number of edges contained in triangles among graphs with n vertices and e edges. Our main tool is a generalization of Zykov's symmetrization method that can be applied to several graphs simultaneously. Copyright © Cambridge University Press 2017

Cibulka J.,Charles University | Kync J.,Charles University | Kync J.,Alfred Renyi Institute of Mathematics
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | Year: 2017

A binary matrix is a matrix with entries from the set f0; 1g. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries. If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k × k matrix with exactly one 1-entry in every row and one 1-entry in every column. The Furedi{Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant cP such that for every n 2 N, every n × n binary matrix A with at least cP n 1-entries contains P. We show that cP ≤ 2O(k2=3log7=3k=(loglogk)1=3) asymptotically almost surely for a random k-permutation matrix P. We also show that cP ≤ 2(4+o(1))k for every k- permutation matrix P, improving the constant in the exponent of a recent upper bound on cP by Fox. We also consider a higher-dimensional generalization of the Stanley{Wilf conjecture about the number of d- dimensional n-permutation matrices avoiding a fin-O(k)xed d- dimensional k-permutation matrix, and prove almost matching upper and lower bounds of the form (2-k)o(n)(n!)d-1-1=(d-1) and n-O(k)k(n). (n!)d-1-1=(d-1), respectively. Copyright © by SIAM.

Kantor I.,Charles University | Patkos B.,Alfred Renyi Institute of Mathematics
Discrete and Computational Geometry | Year: 2013

A well-known theorem of de Bruijn and Erdo{double acute}s states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of n points in the plane with the L1 metric, provided that no two points share their x- or y-coordinate. In this case, either there is a line that contains all n points, or X induces at least n distinct lines. If points of X are allowed to share their coordinates, then either there is a line that contains all n points, or X induces at least n/37 distinct lines. © 2013 Springer Science+Business Media New York.

Wang L.,ETH Zurich | Liu Y.-H.,ETH Zurich | Iazzi M.,ETH Zurich | Troyer M.,ETH Zurich | Harcos G.,Alfred Renyi Institute of Mathematics
Physical Review Letters | Year: 2015

We present a guiding principle for designing fermionic Hamiltonians and quantum Monte Carlo (QMC) methods that are free from the infamous sign problem by exploiting the Lie groups and Lie algebras that appear naturally in the Monte Carlo weight of fermionic QMC simulations. Specifically, rigorous mathematical constraints on the determinants involving matrices that lie in the split orthogonal group provide a guideline for sign-free simulations of fermionic models on bipartite lattices. This guiding principle not only unifies the recent solutions of the sign problem based on the continuous-time quantum Monte Carlo methods and the Majorana representation, but also suggests new efficient algorithms to simulate physical systems that were previously prohibitive because of the sign problem. © 2015 American Physical Society.

Merai L.,Alfred Renyi Institute of Mathematics
Fundamenta Informaticae | Year: 2012

In the paper the pseudorandomness of binary sequences defined over elliptic curves is studied and both the well-distribution and correlation measures are estimated. The paper is based on the Kohel-Shparlinski bound and the Erdös-Turán-Koksma inequality.

Petz D.,Alfred Renyi Institute of Mathematics
Entropy | Year: 2010

Csiszár's f-divergence of two probability distributions was extended to the quantum case by the author in 1985. In the quantum setting, positive semidefinite matrices are in the place of probability distributions and the quantum generalization is called quasi-entropy, which is related to some other important concepts as covariance, quadratic costs, Fisher information, Cramér-Rao inequality and uncertainty relation. It is remarkable that in the quantum case theoretically there are several Fisher information and variances. Fisher information are obtained as the Hessian of a quasi-entropy. A conjecture about the scalar curvature of a Fisher information geometry is explained. The described subjects are overviewed in details in the matrix setting. The von Neumann algebra approach is also discussed for uncertainty relation. © 2010 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland.

Keszegh B.,Alfred Renyi Institute of Mathematics | Palvolgyi D.,Eötvös Loránd University
Discrete and Computational Geometry | Year: 2012

We prove that octants are cover-decomposable; i. e., any 12-fold covering of any subset of the space with a finite number of translates of a given octant can be decomposed into two coverings. As a corollary, we obtain that any 12-fold covering of any subset of the plane with a finite number of homothetic copies of a given triangle can be decomposed into two coverings. We also show that any 12-fold covering of the whole plane with the translates of a given open triangle can be decomposed into two coverings. However, we exhibit an indecomposable 3-fold covering with translates of a given triangle. © 2011 Springer Science+Business Media, LLC.

Petz D.,Alfred Renyi Institute of Mathematics
Journal of Mathematical Physics | Year: 2010

This paper is an overview of the concept of complementarity, the relation to state estimation, to Connes-Størmer conditional (or relative) entropy to uncertainty relation. Complementary Abelian and noncommutative subalgebras are analyzed. All the known results about complementary decompositions are described and several open questions are included. The paper contains only few proofs, typically references are given. © 2010 American Institute of Physics.

Furedi Z.,Alfred Renyi Institute of Mathematics
Journal of Combinatorial Theory. Series B | Year: 2015

Let Tn,p denote the complete p-partite graph of order n having the maximum number of edges. The following sharpening of Turán's theorem is proved. Every Kp+1-free graph with n vertices and e(Tn,p)-t edges contains a p-partite subgraph with at least e(Tn,p)-2t edges. As a corollary of this result we present a concise, contemporary proof (i.e., one applying the Removal Lemma, a corollary of Szemerédi's regularity lemma) for the classical stability result of Simonovits [25]. © 2015 Elsevier Inc.

Csikvari P.,Eötvös Loránd University | Csikvari P.,Alfred Renyi Institute of Mathematics
Combinatorics Probability and Computing | Year: 2013

One can define the independence polynomial of a graph G as follows. Let ik(G) denote the number of independent sets of size k of G, where i0(G)=1. Then the independence polynomial of G is I(G,x)=σn k=0 n(-1)k i k (G)xk. In this paper we give a new proof of the fact that the root of I(G,x) having the smallest modulus is unique and is real. Copyright © 2012 Cambridge University Press.

Loading Alfred Renyi Institute of Mathematics collaborators
Loading Alfred Renyi Institute of Mathematics collaborators