Source author record

Jozsef Balogh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Tilings in vertex ordered graphs

Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect $H$ -tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect $H$ -tiling problem for all ordered graphs $H$ of interval chromatic number $2$ . Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.

preprint2020arXiv

Counting independent sets in regular hypergraphs

Amongst $d$ -regular $r$ -uniform hypergraphs on $n$ vertices, which ones have the largest number of independent sets? While the analogous problem for graphs (originally raised by Granville) is now well-understood, it is not even clear what the correct general conjecture ought to be; our goal here is propose such a generalisation. Lending credence to our conjecture, we verify it within the class of `quasi-bipartite' hypergraphs (a generalisation of bipartite graphs that seems natural in this context) by adopting the entropic approach of Kahn.

preprint2020arXiv

Families in posets minimizing the number of comparable pairs

Given a poset $P$ we say a family $\mathcal{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 centeredness property if for any $M$ , among all families of size $M$ in $P$ , centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$ . We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbb{F}_q^n$ has the centeredness property. Several open questions are also given.

preprint2016arXiv

Further applications of the Container Method

Recently, Balogh--Morris--Samotij and Saxton--Thomason proved that hypergraphs satisfying some natural conditions have only few independent sets. Their main results already have several applications. However, the methods of proving these theorems are even more far reaching. The general idea is to describe some family of events, whose cardinality a priori could be large, only with a few certificates. Here, we show some applications of the methods, including counting $C_4$ -free graphs, considering the size of a maximum $C_4$ -free subgraph of a random graph and counting metric spaces with a given number of points. Additionally, we discuss some connections with the Szemerédi Regularity Lemma.

preprint2016arXiv

Kleitman's conjecture about families of given size minimizing the number of $k$ -chains

A central theorem in combinatorics is Sperner's Theorem, which determines the maximum size of a family $\mathcal{F}\subseteq \mathcal{P}(n)$ that does not contain a $2$ -chain $F_1\subsetneq F_2$ . Erdős later extended this result and determined the largest family not containing a $k$ -chain $F_1\subsetneq \ldots \subsetneq F_k$ . Erdős and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. This question was resolved for $2$ -chains by Kleitman in $1966$ , who showed that amongst families of size $M$ in $\mathcal{P}(n)$ , the number of $2$ -chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all $k$ , not just $2$ . The best result on this question is due to Das, Gan and Sudakov who showed that Kleitman's conjecture holds for families whose size is at most the size of the $k+1$ middle layers of $\mathcal{P}(n)$ , provided $k\leq n-6$ . Our main result is that for every fixed $k$ and $ε>0$ , if $n$ is sufficiently large then Kleitman's conjecture holds for families of size at most $(1-ε)2^n$ , thereby establishing Kleitman's conjecture asymptotically. Our proof is based on ideas of Kleitman and Das, Gan and Sudakov. Several open problems are also given.

preprint2016arXiv

On the number of union-free families

A family of sets is union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. Kleitman proved that every union-free family has size at most $(1+o(1))\binom{n}{n/2}$ . Later, Burosch--Demetrovics-Katona-Kleitman-Sapozhenko asked for the number $α(n)$ of such families, and they proved that $2^{\binom{n}{n/2}}\leq α(n) \leq 2^{2\sqrt{2}\binom{n}{n/2}(1+o(1))}$ . They conjectured that the constant $2\sqrt{2}$ can be removed in the exponent of the right hand side. We prove their conjecture by formulating a new container-type theorem for rooted hypergraphs.

preprint2015arXiv

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of $2$ -edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every $2$ -edge-colored graph can be partitioned into at most $2α(G)$ monochromatic cycles, where $α(G)$ denotes the independence number of $G$ . Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from $o(|V(G)|)$ vertices, the vertex set of any $2$ -edge-colored graph $G$ with minimum degree at least $(1+\eps){3|V(G)|\over 4}$ can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $\overline{G}$ does not contain a fixed bipartite graph $H$ , we show that in every $2$ -edge-coloring of $G$ , $|V(G)|-c(H)$ vertices can be covered by two vertex disjoint paths of different colors, where $c(H)$ is a constant depending only on $H$ . In particular, we prove that $c(C_4)=1$ , which is best possible.

preprint2012arXiv

On the decay of crossing numbers of sparse graphs

Richter and Thomassen proved that every graph has an edge $e$ such that the crossing number $\ucr(G-e)$ of $G-e$ is at least $(2/5)\ucr(G) - O(1)$. Fox and Cs. Tóth proved that dense graphs have large sets of edges (proportional in the total number of edges) whose removal leaves a graph with crossing number proportional to the crossing number of the original graph; this result was later strenghtened by Černý, Kynčl and G. Tóth. These results make our understanding of the {decay} of crossing numbers in dense graphs essentially complete. In this paper we prove a similar result for large sparse graphs in which the number of edges is not artificially inflated by operations such as edge subdivisions. We also discuss the connection between the decay of crossing numbers and expected crossing numbers, a concept recently introduced by Mohar and Tamon.

preprint2010arXiv

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices $u,v$ in a triple system is the set of vertices $w$ such that $uvw$ is an edge. A triple system $\HH$ is semi-bipartite if its vertex set contains a vertex subset $X$ such that every edge of $\HH$ intersects $X$ in exactly two points. It is easy to see that if $\HH$ is semi-bipartite, then the neighborhood of every pair of vertices in $\HH$ is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets $[n]$ and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd\H os-Kleitman-Rothschild theorem to triple systems. The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.

preprint2010arXiv

Bootstrap percolation in high dimensions

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine the critical probability p_c([n]^d,r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem when r = 2, for all functions n and d satisfying d \gg log n. The bootstrap process has been extensively studied on [n]^d when d is a fixed constant and 2 \leq r \leq d, and in these cases p_c([n]^d,r) has recently been determined up to a factor of 1 + o(1) as n -> infinity. At the other end of the scale, Balogh and Bollobas determined p_c([2]^d,2) up to a constant factor, and Balogh, Bollobas and Morris determined p_c([n]^d,d) asymptotically if d > (log log n)^{2+\eps}, and gave much sharper bounds for the hypercube. Here we prove the following result: let λbe the smallest positive root of the equation \sum_{k=0}^\infty (-1)^k λ^k / (2^{k^2-k} k!) = 0, so λ\approx 1.166. Then (16λ/ d^2) (1 + (log d / \sqrt{d})) 2^{-2\sqrt{d}} < p_c([2]^d,2) < (16λ/ d^2) (1 + (5(log d)^2 / \sqrt{d})) 2^{-2\sqrt{d}} if d is sufficiently large, and moreover we determine a sharp threshold for the critical probability p_c([n]^d,2) for every function n = n(d) with d \gg log n.

preprint2010arXiv

Complete Minors, Independent Sets, and Chordal Graphs

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) >= χ(G). Since χ(G) α(G) >= |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) >= |V(G)|. We show that (2 α(G) - \lceil log_t(t α(G)/2) \rceil) h(G) \geq |V(G)| where t is approximately 6.83. For graphs with α(G) \geq 14, this improves on a recent result of Kawarabayashi and Song who showed (2 α(G) - 2) h(G) >= |V(G)| when α(G) >= 3.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jozsef Balogh

Research overview

Is this your work?

11 publications

Tilings in vertex ordered graphs

Counting independent sets in regular hypergraphs

Families in posets minimizing the number of comparable pairs

Further applications of the Container Method

Kleitman's conjecture about families of given size minimizing the number of $k$ -chains

On the number of union-free families

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

On the decay of crossing numbers of sparse graphs

Almost all triple systems with independent neighborhoods are semi-bipartite

Bootstrap percolation in high dimensions

Complete Minors, Independent Sets, and Chordal Graphs

See the researcher in context

Building this map preview

Jozsef Balogh

Research overview

Is this your work?

11 publications

Tilings in vertex ordered graphs

Counting independent sets in regular hypergraphs

Families in posets minimizing the number of comparable pairs

Further applications of the Container Method

Kleitman's conjecture about families of given size minimizing the number of kkk-chains

On the number of union-free families

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

On the decay of crossing numbers of sparse graphs

Almost all triple systems with independent neighborhoods are semi-bipartite

Bootstrap percolation in high dimensions

Complete Minors, Independent Sets, and Chordal Graphs

See the researcher in context

Building this map preview

Kleitman's conjecture about families of given size minimizing the number of $k$ -chains