J. Balogh

activity

20032024

most citedBootstrap percolation in three dimensions

105 citations · 718 across the 103 of their papers we have counts for

collaborators

Showing 2017 · math.COShow all

12 papers · 2 filters

math.CO2017★ 7 cited

Closing in on Hill's conjecture

József Balogh, Bernard Lidický, Gelasio Salazar

Borrowing László Székely's lively expression, we show that Hill's conjecture is "asymptotically at least 98.5% true". This long-standing conjecture states that the crossing number…

math.CO2017

Two results about the hypercube

Jozsef Balogh, Tamas Meszaros, Adam Zsolt Wagner

First we consider families in the hypercube $Q_{n}$ with bounded VC dimension. Frankl raised the problem of estimating the number $m (n, k)$ of maximal families of VC dimension $k$ . Al…

math.CO2017★ 5 cited

On the number of linear hypergraphs of large girth

József Balogh, Lina Li

An $r$ -uniform \textit{linear cycle} of length $ℓ$ , denoted by $C_{ℓ}^{r}$ , is an $r$ -graph with edges $e_{1}, \dots, e_{ℓ}$ such that for every $i \in [ℓ - 1]$ , $|e_i\cap e_…

math.CO2017

Tilings in randomly perturbed dense graphs

József Balogh, Andrew Treglown, Adam Zsolt Wagner

A perfect $H$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of a graph $H$ in $G$ that together cover all the vertices in $G$ . In this paper we investigate perfec…

math.CO2017★ 2 cited

Cubic graphs with small independence ratio

József Balogh, Alexandr Kostochka, Xujun Liu

Let $i (r, g)$ denote the infimum of the ratio $\frac{α ( G )}{∣ V ( G ) ∣}$ over the $r$ -regular graphs of girth at least $g$ , where $α (G)$ is the independence number of $G$ , and let $i(r,\…

math.CO2017

Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs

Jozsef Balogh, Theodore Molla

We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed…

math.CO2017★ 10 cited

The number of hypergraphs without linear cycles

József Balogh, Bhargav Narayanan, Jozef Skokan

The $r$ -uniform linear $k$ -cycle $C_{k}^{r}$ is the $r$ -uniform hypergraph on $k (r - 1)$ vertices whose edges are sets of $r$ consecutive vertices in a cyclic ordering of the vertex set…

math.CO2017

Rainbow spanning trees in properly coloured complete graphs

József Balogh, Hong Liu, Richard Montgomery

In this short note, we study pairwise edge-disjoint rainbow spanning trees in properly edge-coloured complete graphs, where a graph is rainbow if its edges have distinct colours. B…

math.CO2017★ 2 cited

Packing chromatic number of subcubic graphs

József Balogh, Alexandr Kostochka, Xujun Liu

A packing $k$ -coloring of a graph $G$ is a partition of $V (G)$ into sets $V_{1}, \dots, V_{k}$ such that for each $1 \leq i \leq k$ the distance between any two distinct $x, y \in V_{i}$ is a…

math.CO2017

Families in posets minimizing the number of comparable pairs

Jozsef Balogh, Sarka Petrickova, Adam Zsolt Wagner

Given a poset $P$ we say a family $F \subseteq P$ is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the…

math.CO2017★ 2 cited

An improved lower bound for Folkman's theorem

József Balogh, Sean Eberhard, Bhargav Narayanan +2

Folkman's Theorem asserts that for each $k \in N$ , there exists a natural number $n = F (k)$ such that whenever the elements of $[n]$ are two-coloured, there exists a set $…

math.CO2017

A general law of large permanent

Jozsef Balogh, Hoi Nguyen

We show that permanents of doubly stochastic matrices with balanced entries are not far away from the minimum $n! / n^{n}$ . As an application, we give a general law of large permanent,…