Source author record

Igor Balla

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.GT

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Curves on the torus with few intersections

Aougab and Gaster [Math. Proc. Cambridge Philos. Soc. 174 (2023), 569-584] proved that any set of simple closed curves on the torus, where any two are non-homotopic and intersect at most k times, has a maximum size of $k+O(\sqrt{k}\log k)$ . We determine the maximum size of such a set for every k. In particular, the maximum never exceeds k+6, and it does not exceed k+4 when k is large. As this quantity coincides with the maximal number of columns of a generic k-modular matrix with two rows, our result also settles the column number problem, a problem of interest in combinatorial optimization, for such matrices.

preprint2020arXiv

Orthonormal representations of $H$ -free graphs

Let $x_1, \ldots, x_n \in \mathbb{R}^d$ be unit vectors such that among any three there is an orthogonal pair. How large can $n$ be as a function of $d$ , and how large can the length of $x_1 + \ldots + x_n$ be? The answers to these two celebrated questions, asked by Erdős and Lovász, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lovász $\vartheta$ -function and minimum semidefinite rank. In this paper, we study these parameters for general $H$ -free graphs. In particular, we show that for certain bipartite graphs $H$ , there is a connection between the Turán number of $H$ and the maximum of $\vartheta \left( \overline{G} \right)$ over all $H$ -free graphs $G$ .

preprint2016arXiv

Ramsey goodness of bounded degree trees

Given a pair of graphs $G$ and $H$ , the Ramsey number $R(G,H)$ is the smallest $N$ such that every red-blue coloring of the edges of the complete graph $K_N$ contains a red copy of $G$ or a blue copy of $H$ . If a graph $G$ is connected, it is well known and easy to show that $R(G,H) \geq (|G|-1)(χ(H)-1)+σ(H)$ , where $χ(H)$ is the chromatic number of $H$ and $σ(H)$ is the size of the smallest color class in a $χ(H)$ -coloring of $H$ . A graph $G$ is called $H$ -good if $R(G,H)= (|G|-1)(χ(H)-1)+σ(H)$ . The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then. In this paper we show that if $n\geq Ω(|H| \log^4 |H|)$ then every $n$ -vertex bounded degree tree $T$ is $H$ -good. The dependency between $n$ and $|H|$ is tight up to $\log$ factors. This substantially improves a result of Erdős, Faudree, Rousseau, and Schelp from 1985, who proved that $n$ -vertex bounded degree trees are $H$ -good when when $n \geq Ω(|H|^4)$ .

preprint2011arXiv

Minimum density of union-closed families

Let F be a finite union-closed family of sets whose largest set contains n elements. In \cite{Wojcik92}, Wojcik defined the density of F to be the ratio of the average set size of F to n and conjectured that the minimum density over all union-closed families whose largest set contains n elements is (1 + o(1))\log_2(n)/(2n) as n approaches infinity. We use a result of Reimer \cite{Reimer03} to show that the density of F is always at least log_2(n)/(2n), verifying Wojcik's conjecture. As a corollary we show that for n \geq 16, some element must appear in at least \sqrt{(\log_2(n))/n}(|F|/2) sets of F.

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.

Igor Balla

Research overview

Is this your work?

4 publications

Curves on the torus with few intersections

Orthonormal representations of $H$ -free graphs

Ramsey goodness of bounded degree trees

Minimum density of union-closed families

See the researcher in context

Building this map preview

Igor Balla

Research overview

Is this your work?

4 publications

Curves on the torus with few intersections

Orthonormal representations of HHH-free graphs

Ramsey goodness of bounded degree trees

Minimum density of union-closed families

See the researcher in context

Building this map preview

Orthonormal representations of $H$ -free graphs