Source author record

Béla Csaba

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A discrepancy version of the Hajnal-Szemerédi theorem

A perfect $K_r$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$ . The famous Hajnal--Szemerédi theorem determines the minimum degree threshold for forcing a perfect $K_r$ -tiling in a graph $G$ . The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $\{-1,1\}$ , and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$ ). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$ -tiling of high discrepancy.

preprint2020arXiv

On the discrepancies of graphs

In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph $G$ , $\{-1, 1\}$ labels are assigned to the edges, and we consider a family $\mathcal{S}_G$ of (spanning) subgraphs of certain types, among others spanning trees, Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of $\mathcal{S}_G$ , for every labeling.

preprint2016arXiv

On the path separation number of graphs

A path separator of a graph $G$ is a set of paths $\mathcal{P}=\{P_1,\ldots,P_t\}$ such that for every pair of edges $e,f\in E(G)$ , there exist paths $P_e,P_f\in\mathcal{P}$ such that $e\in E(P_e)$ , $f\not\in E(P_e)$ , $e\not\in E(P_f)$ and $f\in E(P_f)$ . The path separation number of $G$ , denoted ${\rm psn}(G)$ , is the smallest number of paths in a path separator. We shall estimate the path separation number of several graph families, including complete graphs, random graph, the hypercube, and discuss general graphs as well.

preprint2014arXiv

Proof of the $1$ -factorization and Hamilton Decomposition Conjectures

In this paper we prove the following results (via a unified approach) for all sufficiently large $n$ : (i) [ $1$ -factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceil n/4\rceil -1$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $χ'(G)=D$ . (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on $n$ vertices with minimum degree $δ\ge n/2$ . Then $G$ contains at least ${\rm reg}_{\rm even}(n,δ)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here $\text{reg}_{\text{even}}(n,δ)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $δ$ . (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case $δ= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.

preprint2014arXiv

Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case

In a sequence of four papers, we prove the following results (via a unified approach) for all sufficiently large $n$ : (i) [1-factorization conjecture] Suppose that $n$ is even and $D \geq 2\lceil n/4\rceil -1$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $χ'(G)=D$ . (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on $n$ vertices with minimum degree $δ\ge n/2$ . Then $G$ contains at least ${\rm reg}_{\rm even}(n,δ)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here ${\rm reg}_{\rm even}(n,δ)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $δ$ . According to Dirac, (i) was first raised in the 1950s. (ii) and the special case $δ= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible. In the current paper, we prove the above results for the case when $G$ is close to a complete balanced bipartite graph.

preprint2014arXiv

Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions

In a sequence of four papers, we prove the following results (via a unified approach) for all sufficiently large $n$ : (i) [1-factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceil n/4\rceil -1$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $χ'(G)=D$ . (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor$ . Then every $D$ -regular graph $G$ on $n$ vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) We prove an optimal result on the number of edge-disjoint Hamilton cycles in a graph of given minimum degree. According to Dirac, (i) was first raised in the 1950s. (ii) and (iii) answer questions of Nash-Williams from 1970. The above bounds are best possible. In the current paper, we show the following: suppose that $G$ is close to a complete balanced bipartite graph or to the union of two cliques of equal size. If we are given a suitable set of path systems which cover a set of `exceptional' vertices and edges of $G$ , then we can extend these path systems into an approximate decomposition of $G$ into Hamilton cycles (or perfect matchings if appropriate).

preprint2013arXiv

Optimal Random Matchings, Tours, and Spanning Trees in Hierarchically Separated Trees

We derive tight bounds on the expected weights of several combinatorial optimization problems for random point sets of size $n$ distributed among the leaves of a balanced hierarchically separated tree. We consider {\it monochromatic} and {\it bichromatic} versions of the minimum matching, minimum spanning tree, and traveling salesman problems. We also present tight concentration results for the monochromatic problems.

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.

Béla Csaba

Research overview

Is this your work?

7 publications

A discrepancy version of the Hajnal-Szemerédi theorem

On the discrepancies of graphs

On the path separation number of graphs

Proof of the $1$ -factorization and Hamilton Decomposition Conjectures

Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case

Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions

Optimal Random Matchings, Tours, and Spanning Trees in Hierarchically Separated Trees

See the researcher in context

Building this map preview

Béla Csaba

Research overview

Is this your work?

7 publications

A discrepancy version of the Hajnal-Szemerédi theorem

On the discrepancies of graphs

On the path separation number of graphs

Proof of the 111-factorization and Hamilton Decomposition Conjectures

Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case

Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions

Optimal Random Matchings, Tours, and Spanning Trees in Hierarchically Separated Trees

See the researcher in context

Building this map preview

Proof of the $1$ -factorization and Hamilton Decomposition Conjectures