László Lovász

(Almost) Tight Bounds and Existence Theorems for Single-Commodity Confluent Flows (2008)

How deep is the dividing line between discrete and continuous mathematics? Basic structures and methods of both sides of our science are quite different. But on a deeper level, there is a more solid...

Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this paper we study single-commodity confluent flow problems, where we need...

Stopping rule reversal for finite Markov chains (2008)

Andrew Beveridge, László Lovász

Consider a finite irreducible Markov chain with transition matrix M = (pij). Fixing a target distribution τ, we study a family of optimal stopping rules from the singleton distributions to τ. We...

WAITING FOR A BAT TO FLY BY (IN POLYNOMIAL TIME) (2008)

Itai Benjamini, Gady Kozma, László Lovász, Dan Romik

Abstract. We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition...

Published in: Linear Alg. Appl., Vol 226–228, pp. 553–567. The cocycle lattice of binary matroids, II (2008)

László Lovász, Translated (with Additions, Modifications Péter Gács

Abstract: We continue the study initiated in [LS] of the lattice (grid) generated by the incidence vectors of cocycles of a binary matroid and its dual lattice. In [LS], we proved that every...

Contents (2008)

ABSTRACT. Lecture notes for a one-semester graduate course. Part of it is also suitable for an undergraduate course, at a slower pace. Mathematical maturity is the main prerequisite.

Contents Limits of dense graph sequences (2008)

Szemerédi’s Lemma for the analyst (2008)

Contents Discrete Analytic Functions: An (2008)

Szemerédi’s Regularity Lemma is a fundamental tool in graph theory: it has many applications to extremal graph theory, graph property testing, combinatorial number theory, etc. The goal of this...

Christian Borgs, Vera T. Sós, Jennifer Chayes, Balázs Szegedy, László Lovász, Katalin Vesztergombi

Theory (2008)

We define a distance of two graphs that reflects the closeness of both local and global properties. We also define convergence of a sequence of graphs, and show that a graph sequence is convergent if...

Abstract Graph limits and parameter testing (2008)

Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, Katalin Vesztergombi

We define a distance of two graphs that reflects the closeness of both local and global properties. We also define convergence of a sequence of graphs, and show that a graph sequence is convergent if...

Hit-and-Run Mixes Fast (2007)

On the null space of a Colin de Verdière matrix (2007)

It is shown that the "hit-and-run" algorithm for sampling from a convex body K mixes in time O (n 2 R 2 =r 2 ), where R and r are the radii of the inscribed and circumscribed balls of K....

László Lovász, Alexander Schrijver

. Let G = (V; E) be a 3-connected planar graph, with V = f1; : : : ; ng. Let M = (m i;j ) be a symmetric n \Theta n matrix with exactly one negative eigenvalue (of multiplicity 1), such that for i; j...

Hit-and-Run is Fast and Fun 1 (2007)

Simulated Annealing in Convex Bodies (2007)

The hit-and-run algorithm is one of the fastest known methods to generate a random point in a high dimensional convex set. In this paper we study a natural extension of the hit-and-run algorithm to...

And An Volume, László Lovász, Santosh Vempala

this paper, we further improve the running time to O # (n ) (where the asterisk means that we suppress factors that are logarithmic in n). The algorithm uses O # (n) points for its computations, and...

Where to Start a Geometric Random Walk? (2007)

Laszlo Lovasz Santosh, László Lovász, Santosh Vempala

this paper we describe a general condition under which the conductance of hit-and-run can be bounded for arbitrarily small sets. The condition is satisfied by the uniform density over a convex body...

Discrete Localization and Correlation Inequalities for Set Functions (2007)

Laszlo Lovasz Michael, László Lovász, Michael Saks

Three theorems for set functions, closely related to the AhlswedeDaykin 4-function theorem (4FT), are proved. First, the conclusion of the 4FT is generalized to norms other than the L 1 norm....

Simulated Annealing in Convex Bodies and an O*(n^4) Volume Algorithm (2007)

Contents Eigenvalues of graphs (2007)

We present a new algorithm for computing the volume of a convex body in R^n. The main ingredient of the algorithm is a "morphing" technique that can be viewed as a variant of simulated...

Contents (2007)

Background material 1.1 Background from linear algebra 1.1.1 Basic facts about eigenvalues Geometric Graph Theory (2007)

László Lovász, Katalin Vesztergombi

Let A be an n × n real matrix. An eigenvector of A is a vector such that Ax is parallel to x; in other words, Ax = λx for some real or complex number λ. This number λ is called the eigenvalue of...

Reflection positivity, rank connectivity, and homomorphism of graphs (2007)

Michael Freedman, László Lovász, Alexander Schrijver

Abstract. It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection...

Connection matrices (2007)

Contents Fast Mixing in a Markov Chain (2007)

Vesztergombi: Counting graph homomorphism (2006)

Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi

Counting homomorphisms between graphs (often with weights) comes up in a wide variety of areas, including extremal graph theory, properties of graph products, partition functions in statistical...

Local versus global properties of metric spaces (2006)

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala

Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...

Fast algorithms for logconcave functions: sampling, rounding, integration and optimization (2006)

Local versus global properties of metric spaces (2006)

We prove that the hit-and-run random walk is rapidly mixing for an arbitrary logconcave distribution starting from any point in the support. This extends the work of [26], where this was shown for an...

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala

Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...

Contents Counting Graph Homomorphisms (2006)

Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi

Diskrete Mathematik (2005)

Lovász, László

Graph limits and testing hereditary graph properties (2005)

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding (2005)

We show that an important recent result of Alon and Shapira on testing hereditary graph properties can be derived from the existence of a limit object for convergent graph sequences. 1

Kamal Jain, László Lovász, Philip A. Chou

We propose a scheme for building peer-to-peer overlay networks for broadcasting using network coding. The scheme addresses many practical issues such as scalability, robustness, constraints on...

Graph parameters and reflection positivity (2005)

Michael H. Freedman, László Lovász, Alexander Schrijver

We characterize which real-valued (undirected) graph parameters are of the following type, where H is a graph and α: V H → R+ and β: EH → R: fH,α,β(G):= αφ(v)) ( �

Graph parameters and reflection positivity (2005)

Michael H. Freedman, László Lovász, Alexander Schrijver

We characterize which real-valued (undirected) graph parameters are of the following type, where H is a graph and α: V H → R+ and β: EH → R: fH,α,β(G):= αφ(v)) ( �

Graph limits and testing hereditary graph properties (2005)

Convex quadrilaterals and k-sets (2004)

We show that an important recent result of Alon and Shapira on testing hereditary graph properties can be derived from the existence of a limit object for convergent graph sequences. 1

László Lovász, Katalin Vesztergombi, Uli Wagner, Emo Welzl

We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn –...

Hit-and-run from a corner (2004)

Convex quadrilaterals and k-sets (2004)

We show that the hit-and-run random walk mixes rapidly starting from any interior point of a convex body. This is the first random walk known to have this property. In contrast, the ball walk can...

László Lovász, Katalin Vesztergombi, Uli Wagner, Emo Welzl

We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn –...

Almost) tight bounds and existence theorems for confluent flows (2004)

Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta

A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G, we consider the problem of...

Semi-matchings for bipartite graphs and load balancing (2003)

Richard E. Ladner, László Lovász, Tami Tamir D

We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices. We refer to this problem as the optimal semimatching problem; it is a relaxation of...

Semi-matchings for bipartite graphs and load balancing (2003)

Richard E. Ladner, László Lovász, Tami Tamir

Abstract. We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices.We refer to this problem as the semi-matching problem; it is a relaxation...

Semi-Matchings for Bipartite Graphs and Load Balancing (2003)

Richard E. Ladner, Laszlo Lovasz, László Lovász, Tami Tamir

We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices. We refer to this problem as the optimal semi-matching problem; it is a relaxation of...

Contents The Geometry of Logconcave Functions and Sampling Algorithms ∗ (2003)

Approximating Min-sum Set Cover (2003)

Uriel Feige, László Lovász, Prasad Tetali

this paper appeared in the conference proceedings of APPROX 2002

The geometry of logconcave functions and an O∗(n³) sampling algorithm (2003)

Semi-matchings for bipartite graphs and load balancing (2003)

The class of logconcave functions in R^n is a common generalization of Gaussians and of indicator functions of convex sets. Motivated by the problem of sampling from a logconcave density function, we...

Richard E. Ladner, László Lovász, Tami Tamir

We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices. We refer to this problem as the optimal semi-matching problem; it is a relaxation of...

Determining the genus of a map by local observation of a simple random process (2002)

Itai Benjamini, László Lovász

Given a graph embedded in an orientable surface, a process with stationary increments, consisting of random excitations and random node and face balancing, is constructed and analyzed. It is shown...

Approximating min sum set cover (2002)

Uriel Feige, László Lovász, Prasad Tetali

The input to the min sum set cover problem is a collection of n sets that jointly cover m elements. The output is a linear order on the sets, namely, in every time step from 1 to n exactly one set is...

Proving integrality gaps without knowing the linear program (2002)

Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis

Abstract: Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We...

Critical Facets of the Stable Set Polytope (1999)

László Lipták, László Lovász, Paul Erdos

A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an ff-critical graph. We extend several results from the theory of ff-critical graphs to facets. The...

A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs (1998)

László Lovász, Alexander Schrijver

. For any undirected graph G, let ¯(G) be the graph parameter introduced by Colin de Verdi`ere. In this paper we show that ¯(G) 4 if and only if G is linklessly embeddable (in R 3 ). This forms a...

Mixing Times (1998)

The Colin de Verdière graph parameter (1997)

. The critical issue in the complexity of Markov chain sampling techniques has been "mixing time", the number of steps of the chain needed to reach its stationary distribution. It turns out...

László Lovász, Alexander Schrijver, Er Schrijver

. In 1990, Y. Colin de Verdi`ere introduced a new graph parameter ¯(G), based on spectral properties of matrices associated with G. He showed that ¯(G) is monotone under taking minors and that...

Contents (1997)

László Lovász, Er Schrijver

Abstract. In 1990, Y. Colin de Verdière introduced a new graph parameter µ(G), based on spectral properties of matrices associated with G. He showed that µ(G) is monotone under taking minors and...

The rank and size of graphs (1996)

Andrew Kotlov, László Lovász

We show that the number of points with pairwise different sets of neighbors in a graph is O(2 r/2) where r is the rank of the adjacency matrix. We also give an example that achieves this bound. 1

Random Walks And An O*(n 5 ) Volume Algorithm For Convex Bodies (1996)

Ravi Kannan, László Lovász, Miklos Simonovits

Given a high dimensional convex body K ` IR n by a separation oracle, we can approximate its volume with relative error ", using O (n 5 ) oracle calls. Our algorithm also brings the body into...

Topological Methods in Combinatorics (1996)

László Lovász, Simplicial Complexes

s in S, and take the union of these simplices. This set G(K) ae IR n\Gamma1 is called a geometric realization of K. It is clear that all geometric realizations are homeomorphic. Let K 1 and K 2 be...

The Colin de Verdière number and sphere representations of a graph (1996)

Andrew Kotlov, László Lovász, Santosh Vempala

Colin de Verdi`ere introduced an interesting linear algebraic invariant ¯(G) of graphs. He proved that ¯(G) 2 if and only if G is outerplanar, and ¯(G) 3 if and only if G is planar. We prove that...

On conway’s thrackle conjecture (1995)

László Lovász, János Pach, Mario Szegedy

A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to...

Exact mixing in an unknown markov chain (1995)

The Membership Problem in Jump Systems (1995)

We give a simple stopping rule which will stop an unknown, irreducible n-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected...

Isoperimetric Problems for Convex Bodies and a Localization Lemma (1995)

A jump system is a set of lattice points satisfying a certain exchange axiom. This notion was introduced by Bouchet and Cunningham [2], as a common generalization of (among others) the sets of bases...

Ravi Kannan, László Lovász, Miklós Simonovits

. We study the smallest number /(K) such that a given convex body K in IR n can be cut into two parts K 1 and K 2 by a surface with an (n \Gamma 1)-dimensional measure /(K)vol(K 1 ) \Delta vol(K 2...

Exact Mixing in an Unknown Markov Chain (1995)

Mixing of Random Walks and Other Diffusions on a Graph (1995)

We give a simple stopping rule which will stop an unknown, irreducible n-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected...

Semidefinite programs and combinatorial optimization (1995)

We survey results on two diffusion processes on graphs: random walks and chip-firing (closely related to the "abelian sandpile" or "avalanche" model of self-organized criticality...