Source author record

Marius Tiba

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.FA math.MG math.PR

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A strengthening of Freiman's 3k-4 theorem

In its usual form, Freiman's 3k-4 theorem states that if A and B are subsets of the integers of size k with small sumset (of size close to 2k) then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this by allowing only a bounded number of possible summands from one of the sets. We show that if A and B are subsets of the integers of size k such that for any four-element subset X of B the sumset A+X has size not much more than 2k then already this implies that A and B are very close to arithmetic progressions.

preprint2022arXiv

Large sumsets from medium-sized subsets

The classical Cauchy--Davenport inequality gives a lower bound for the size of the sum of two subsets of ${\mathbb Z}_p$ , where $p$ is a prime. Our main aim in this paper is to prove a considerable strengthening of this inequality, where we take only a small number of points from each of the two subsets when forming the sum. One of our results is that there is an absolute constant $c>0$ such that if $A$ and $B$ are subsets of ${\mathbb Z}_p$ with $|A|=|B|=n\le p/3$ then there are subsets $A'\subset A$ and $B'\subset B$ with $|A'|=|B'|\le c \sqrt{n}$ such that $|A'+B'|\ge 2n-1$ . In fact, we show that one may take any sizes one likes: as long as $c_1$ and $c_2$ satisfy $c_1c_2 \ge cn$ then we may choose $|A'|=c_1$ and $|B'|=c_2$ . We prove related results for general abelian groups.

preprint2022arXiv

Large sumsets from small subsets

In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy--Davenport theorem gives a lower bound on the size of a sumset A+B for subsets of the cyclic group Zp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset C of bounded size such that A+C is large, perhaps even comparable to the size of A+B? In particular, can we get close to the lower bound of the Cauchy--Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself.

preprint2022arXiv

Towards Hadwiger's conjecture via Bourgain Slicing

In 1957, Hadwiger conjectured that every convex body in $\mathbb{R}^d$ can be covered by $2^d$ translates of its interior. For over 60 years, the best known bound was of the form $O(4^d \sqrt{d} \log d)$ , but this was recently improved by a factor of $e^{Ω(\sqrt{d})}$ by Huang, Slomka, Tkocz and Vritsiou. In this note we take another step towards Hadwiger's conjecture by deducing an almost-exponential improvement from the recent breakthrough work of Chen, Klartag and Lehec on Bourgain's slicing problem. More precisely, we prove that, for any convex body $K \subset \mathbb{R}^d$ , $\exp\bigg( - Ω\bigg( \frac{d}{(\log d)^8} \bigg) \bigg) \cdot 4^d$ translates of $\text{int}(K)$ suffice to cover $K$ . We also show that a positive answer to Bourgain's slicing problem would imply an exponential improvement for Hadwiger's conjecture.

preprint2020arXiv

Improved Bound for Tomaszewski's Problem

In 1986, Tomaszewski made the following conjecture. Given $n$ real numbers $a_{1},...,a_{n}$ with $\sum_{i=1}^{n}a_{i}^{2}=1$ , then of the $2^{n}$ signed sums $\pm a_{1} \pm ... \pm a_{n}$ , at least half have absolute value at most $1$ . Hendriks and Van Zuijlen (2020) and Boppana (2020) independently proved that a proportion of at least $0.4276$ of these sums has absolute value at most $1$ . Using different techniques, we improve this bound to $0.46$ .

preprint2020arXiv

Radius, Girth and Minimum Degree

Given a connected graph $G$ on $n$ vertices, with minimum degree $δ\geq 2$ and girth at least $g \geq 4$ , what is the maximum radius $r$ this graph can have? Erdős, Pach, Pollack and Tuza established in the triangle-free case ( $g=4$ ) that $r \leq \frac{n-2}δ+12$ , and noted that up to the value of the additive constant, this is tight. We determine the exact value for the triangle-free case. For higher $g$ little is known. We settle the order of $r$ for $g=6,8,12$ and prove an upper bound to the order for general even $g$ . Finally, we show that proving the corresponding lower bound for general even $g$ is equivalent to the Erdős girth conjecture.

preprint2020arXiv

Sharp Stability of Brunn-Minkowski for Homothetic Regions

We prove a sharp stability result concerning how close homothetic sets attaining near-equality in the Brunn-Minkowski inequality are to being convex. In particular, resolving a conjecture of Figalli and Jerison, we show there are universal constants $C_n,d_n>0$ such that for $A \subset \mathbb{R}^n$ of positive measure, if $|\frac{A+A}{2}\setminus A| \le d_n |A|$ , then $|\operatorname{co}(A)\setminus A| \le C_n |\frac{A+A}{2}\setminus A|$ for $\operatorname{co}(A)$ the convex hull of $A$ .

preprint2019arXiv

Strong Ramsey Games in Unbounded Time

For two graphs $B$ and $H$ the strong Ramsey game $\mathcal{R}(B,H)$ on the board $B$ and with target $H$ is played as follows. Two players alternately claim edges of $B$ . The first player to build a copy of $H$ wins. If none of the players win, the game is declared a draw. A notorious open question of Beck asks whether the first player has a winning strategy in $\mathcal{R}(K_n,K_k)$ in bounded time as $n\rightarrow\infty$ . Surprisingly, in a recent paper Hefetz et al. constructed a $5$ -uniform hypergraph $\mathcal{H}$ for which they proved that the first player does not have a winning strategy in $\mathcal{R}(K_n^{(5)},\mathcal{H})$ in bounded time. They naturally ask whether the same result holds for graphs. In this paper we make further progress in decreasing the rank. In our first result, we construct a graph $G$ (in fact $G=K_6\setminus K_4$ ) and prove that the first player does not have a winning strategy in $\mathcal{R}(K_n \sqcup K_n,G)$ in bounded time. As an application of this result we deduce our second result in which we construct a $4$ -uniform hypergraph $G'$ and prove that the first player does not have a winning strategy in $\mathcal{R}(K_n^{(4)},G')$ in bounded time. This improves the result in the paper above. An equivalent formulation of our first result is that the game $\mathcal{R}(K_ω\sqcup K_ω,G)$ is a draw. Another reason for interest on the board $K_ω\sqcup K_ω$ is a folklore result that the disjoint union of two finite positional games both of which are first player wins is also a first player win. An amusing corollary of our first result is that at least one of the following two natural statements is false: (1) for every graph $H$ , $\mathcal{R}(K_ω,H)$ is a first player win; (2) for every graph $H$ if $\mathcal{R}(K_ω,H)$ is a first player win, then $\mathcal{R}(K_ω\sqcup K_ω,H)$ is also a first player win.

preprint2010arXiv

An algorithm to prescribe the configuration of a finite graph

We provide algorithms involving edge slides, for a connected simple graph to evolve in a finite number of steps to another connected simple graph in a prescribed configuration, and for the regularization of such a graph by the minimization of an appropriate energy functional.

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.

Marius Tiba

Research overview

Is this your work?

9 publications

A strengthening of Freiman's 3k-4 theorem

Large sumsets from medium-sized subsets

Large sumsets from small subsets

Towards Hadwiger's conjecture via Bourgain Slicing

Improved Bound for Tomaszewski's Problem

Radius, Girth and Minimum Degree

Sharp Stability of Brunn-Minkowski for Homothetic Regions

Strong Ramsey Games in Unbounded Time

An algorithm to prescribe the configuration of a finite graph

See the researcher in context

Building this map preview