Source author record

Felix Christian Clemen

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

6works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Chasing the Threshold Bias of the 3-AP Game

In a Maker-Breaker game there are two players, Maker and Breaker, where Maker wins if they create a specified structure while Breaker wins if they prevent Maker from winning indefinitely. A $3$ -term arithmetic progression, or $3$ -AP, is a sequence of three distinct integers $a, b, c$ such that $b-a = c-b$ . The $3$ -AP game is a biased Maker-Breaker game played on $[n]$ where every round Breaker selects $q$ unclaimed integers for every Maker's one integer. Maker is trying to select points such that they have a $3$ -AP and Breaker is trying to prevent this. The main question of interest is determining the threshold bias $q^*(n)$ , that is the minimum value of $q=q(n)$ for which Breaker has a winning strategy. Kusch, Rué, Spiegel and Szabó initially asked this question and proved $\sqrt{n/12-1/6}\leq q^*(n)\leq \sqrt{3n}$ . We find new strategies for both Maker and Breaker which improve the existing bounds to $(1+o(1))\sqrt{\frac{n}{5.6}} \leq q^*(n) \leq \sqrt{2n} +O(1).$

preprint2022arXiv

Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions

For every integer $t \ge 0$ , denote by $F_5^t$ the hypergraph on vertex set $\{1,2,\ldots, 5+t\}$ with hyperedges $\{123,124\} \cup \{34k : 5 \le k \le 5+t\}$ . We determine $\mathrm{ex}(n,F_5^t)$ for every $t\ge 0$ and sufficiently large $n$ and characterize the extremal $F_5^t$ -free hypergraphs. In particular, if $n$ satisfies certain divisibility conditions, then the extremal $F_5^t$ -free hypergraphs are exactly the balanced complete tripartite hypergraphs with additional hyperedges inside each of the three parts $(V_1,V_2,V_3)$ in the partition; each part $V_i$ spans a $(|V_i|,3,2,t)$ -design. This generalizes earlier work of Frankl and Füredi on the Turán number of $F_5:=F_5^0$ . Our results extend a theory of Erdős and Simonovits about the extremal constructions for certain fixed graphs. In particular, the hypergraphs $F_5^{6t}$ , for $t\geq 1$ , are the first examples of hypergraphs with exponentially many extremal constructions and positive Turán density.

preprint2022arXiv

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number $m$ of vertices and number $f$ of edges. Extending their notation to $r$ -graphs, we write $(n,e) \to_r (m,f)$ if every $r$ -graph $G$ on $n$ vertices with $e$ edges has an induced subgraph on $m$ vertices and $f$ edges. The \emph{forcing density} of a pair $(m,f)$ is $σ_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .$ In the graph setting it is known that there are infinitely many pairs $(m, f)$ with positive forcing density. Weber asked if there is a pair of positive forcing density for $r\geq 3$ apart from the trivial ones $(m, 0)$ and $(m, \binom{m}{r})$ . Answering her question, we show that $(6,10)$ is such a pair for $r=3$ and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

preprint2021arXiv

Maximum Number of Almost Similar Triangles in the Plane

A triangle $T'$ is $\varepsilon$ -similar to another triangle $T$ if their angles pairwise differ by at most $\varepsilon$ . Given a triangle $T$ , $\varepsilon>0$ and $n\in\mathbb{N}$ , Bárány and Füredi asked to determine the maximum number of triangles $h(n,T,\varepsilon)$ being $\varepsilon$ -similar to $T$ in a planar point set of size $n$ . We show that for almost all triangles $T$ there exists $\varepsilon=\varepsilon(T)>0$ such that $h(n,T,\varepsilon)=n^3/24 (1+o(1))$ . Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof.

preprint2021arXiv

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Turán's famous tetrahedron problem is to compute the Turán density of the tetrahedron $K_4^3$ . This is equivalent to determining the maximum $\ell_1$ -norm of the codegree vector of a $K_4^3$ -free $n$ -vertex $3$ -uniform hypergraph. We introduce a new way for measuring extremality of hypergraphs and determine asymptotically the extremal function of the tetrahedron in our notion. The codegree squared sum, $\text{co}_2(G)$ , of a $3$ -uniform hypergraph $G$ is the sum of codegrees squared $d(x,y)^2$ over all pairs of vertices $xy$ , or in other words, the square of the $\ell_2$ -norm of the codegree vector of the pairs of vertices. We define $\text{exco}_2(n,H)$ to be the maximum $\text{co}_2(G)$ over all $H$ -free $n$ -vertex $3$ -uniform hypergraphs $G$ . We use flag algebra computations to determine asymptotically the codegree squared extremal number for $K_4^3$ and $K_5^3$ and additionally prove stability results. In particular, we prove that the extremal $K_4^3$ -free hypergraphs in $\ell_2$ -norm have approximately the same structure as one of the conjectured extremal hypergraphs for Turán's conjecture. Further, we prove several general properties about $\text{exco}_2(n,H)$ including the existence of a scaled limit, blow-up invariance and a supersaturation result.

preprint2019arXiv

Making $K_{r+1}$ -Free Graphs $r$ -partite

The Erdős-Simonovits stability theorem states that for all ε>0 there exists α>0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - αn^2, then one can remove εn^2 edges from G to obtain an r-partite graph. Füredi gave a short proof that one can choose α=ε. We give a bound for the relationship of αand \varepsilon which is asymptotically sharp as ε\to 0.

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.

Felix Christian Clemen

Research overview

Is this your work?

6 publications

Chasing the Threshold Bias of the 3-AP Game

Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Maximum Number of Almost Similar Triangles in the Plane

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Making $K_{r+1}$ -Free Graphs $r$ -partite

See the researcher in context

Building this map preview

Felix Christian Clemen

Research overview

Is this your work?

6 publications

Chasing the Threshold Bias of the 3-AP Game

Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Maximum Number of Almost Similar Triangles in the Plane

Solving Turán's Tetrahedron Problem for the ℓ2\ell_2ℓ2​-Norm

Making Kr+1K_{r+1}Kr+1​-Free Graphs rrr-partite

See the researcher in context

Building this map preview

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Making $K_{r+1}$ -Free Graphs $r$ -partite