MAJORITY BOOTSTRAP PERCOLATION ON THE HYPERCUBE (2008)
József Balogh, Béla Bollobás, Robert Morris
Abstract. In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected,...
Bootstrap percolation on infinite trees and non-amenable groups (2008)
József Balogh, Yuval Peres, Gábor Pete
Abstract. Bootstrap percolation on an arbitrary graph has a random initial configu-ration, where each vertex is occupied with probability p, independently of each other, and a deterministic spreading...
ABSTRACT Long Monotone Paths in Line Arrangements (2008)
József Balogh, William Steiger
Categories and Subject Descriptors
On Avoider-Enforcer games (2008)
In the Avoider-Enforcer game on the complete graph Kn, the players (Avoider and Enforcer) each take an edge in turn. Enforcer wins the game when he can require Avoider’s graph to have a given...
The penultimate rate of growth for graph properties (2008)
József Balogh, Béla Bollobás, David Weinreich
Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or...
Sizes of induced subgraphs of Ramsey graphs (2008)
Noga Alon, József Balogh, R Kostochka, Wojciech Samotij
An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n...
Hereditary properties of tournaments (2007)
Balogh, József, Bollobás, Béla, Morris, Robert
A collection of unlabelled tournaments P is called a hereditary property if it is closed under isomorphism and under taking induced sub-tournaments. The speed of P is the function n -> |P_n|, where...
Majority bootstrap percolation on the hypercube (2007)
Balogh, József, Bollobás, Béla, Morris, Robert
In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is...
Hereditary properties of combinatorial structures: posets and oriented graphs (2007)
Balogh, József, Bollobás, Béla, Morris, Robert
A hereditary property of combinatorial structures is a collection of structures (e.g. graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g. induced...
Hereditary properties of partitions, ordered graphs and ordered hypergraphs (2007)
Balogh, József, Bollobás, Béla, Morris, Robert
In this paper we use the Klazar-Marcus-Tardos method to prove that if a hereditary property of partitions P has super-exponential speed, then for every k-permutation pi, P contains the partition of...
Hereditary properties of ordered graphs (2007)
Balogh, József, Bollobás, Béla, Morris, Robert
An ordered graph is a graph together with a linear order on its vertices. A hereditary property of ordered graphs is a collection of ordered graphs closed under taking induced ordered subgraphs. If P...
A new short proof of a theorem of Ahlswede and Khachatrian (2007)
Ahlswede and Khachatrian [5] proved the following theorem, which answered a question of Frankl and Füredi [3]. Let 2 ≤ t + 1 ≤ k ≤ 2t + 1 and n ≥ (t + 1)(k − t + 1). Suppose that F is a...
Edit distance and its computation (2007)
In this paper, we provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without...
On the variance of Shannon products of graphs (2007)
We study the combinatorial problem of finding an arrangement of distinct integers into the d-dimensional N-cube so that the maximal variance of the numbers on each ℓ-dimensional section is...
József Balogh, Ryan Martin, András Pluhár
Abstract. A large class of the so-called Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his...
Maria Axenovich, József Balogh
Let ℓ be any positive integer, n be a sufficiently large number, and let G be a graph on n vertices. Define for any k νk(G) = |{|E(H) | : H is an induced subgraph of G on k vertices}|. We show...
On the edge-bandwidth of graph products (2005)
József Balogh, Dhruv Mubayi, András Pluhár
Abstract. The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two dimensional grids and tori, the product of two...
Improved Bounds for the Number of ( (2004)
Balogh, József, Salazar, Gelasio
We use circular sequences to give an improved lower bound on the minimum number of (
Improved Bounds for the Number of ( (2004)
Balogh, József, Salazar, Gelasio
We use circular sequences to give an improved lower bound on the minimum number of (
Improved Bounds for the Number of ( (2004)
Balogh, József, Salazar, Gelasio
We use circular sequences to give an improved lower bound on the minimum number of (
On k-sets, convex quadrilaterals, and the rectilinear crossing number of Kn (2004)
József Balogh, Gelasio Salazar
We use circular sequences to give an improved lower bound on the minimum number of ( ≤ k)– sets in a set of points in general position. We then use this to show that if S is a set of n points in...
The number of edge colorings with no monochromatic cliques (2004)
Noga Alon, József Balogh, Peter Keevash, Benny Sudakov
Let F (n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of Kk. Itisshownthatfor every fixed k...
Long monotone paths in line arrangements (2003)
József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
() N — = #+V ( * () =8-H S () = ()žŸŽi ’=;¡2 ’ ¢ ” £[ ¤ ¥ – œSH( *!Y
Random disease on the square grid (1998)
Abstract. We introduce some generalizations of a nice combinatorial problem, the central notion of which is the so-called Disease Process. Let us color independently each square of an n×n chessboard...
Measures on monotone properties of graphs (1997)
József Balogh, Béla Bollobás, David Weinreich
Abstract. Given a monotone property P of graphs, write P n for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove...