Felix Christian Clemen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Felix Christian Clemen has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- József Balogh
Department of Mathematics and University of Illinois Urbana-Champaign Urbana IL USA
8 shared publications József Balogh
5 shared publications- Bernard Lidický
Department of Mathematics Iowa State University Ames Iowa USA
4 shared publications - Maria Axenovich
Karlsruhe Institute of Technology, Karlsruhe, Germany
4 shared publications - Adrian Dumitrescu
Algoresearch L.L.C.
3 shared publications - Adam Zsolt Wagner
Mathematical Sciences Department Worcester Polytechnic Institute
2 shared publications
Latest Publications
- Open Access
- 18 July 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (9) , 1-25
On a Traveling Salesman Problem for Points in the Unit Cube
Let X be an n-element point set in the k-dimensional unit cube $$[0,1]^k$$ where $$k \ge 2$$ . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour) $$x_1, x_2, \ldots , x_n$$ through the n points, such that $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ , where $$|x-y|$$ is the Euclidean distance between x and y, and $$c_k$$ is an absolute constant that depends only on k, where $$x_{n+1} \equiv x_1$$ . From the other direction, for every $$k \ge 2$$ and $$n \ge 2$$ , there exist n points in $$[0,1]^k$$ , such that their shortest tour satisfies $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ . For the plane, the best constant is $$c_2=2$$ and this is the only exact value known. Bollobás and Meir showed that one can take $$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ for every $$k \ge 3$$ and conjectured that the best constant is $$c_k = 2^{1/k} \cdot \sqrt{k}$$ , for every $$k \ge 2$$ . Here we significantly improve the upper bound and show that one can take $$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ or $$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ . Our bounds are constructive. We also show that $$c_3 \ge 2^{7/6}$$ , which disproves the conjecture for $$k=3$$ . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed.- 18 July 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (9) , 1-25
Open AccessOn a Traveling Salesman Problem for Points in the Unit Cube
Let X be an n-element point set in the k-dimensional unit cube $$[0,1]^k$$ where $$k \ge 2$$ . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour) $$x_1, x_2, \ldots , x_n$$ through the n points, such that $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ , where $$|x-y|$$ is the Euclidean distance between x and y, and $$c_k$$ is an absolute constant that depends only on k, where $$x_{n+1} \equiv x_1$$ . From the other direction, for every $$k \ge 2$$ and $$n \ge 2$$ , there exist n points in $$[0,1]^k$$ , such that their shortest tour satisfies $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ . For the plane, the best constant is $$c_2=2$$ and this is the only exact value known. Bollobás and Meir showed that one can take $$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ for every $$k \ge 3$$ and conjectured that the best constant is $$c_k = 2^{1/k} \cdot \sqrt{k}$$ , for every $$k \ge 2$$ . Here we significantly improve the upper bound and show that one can take $$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ or $$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ . Our bounds are constructive. We also show that $$c_3 \ge 2^{7/6}$$ , which disproves the conjecture for $$k=3$$ . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. - Open Access
Online Ramsey numbers of ordered paths and cycles
An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $G$ and $H$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $G$ or a blue $H$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $r_o(G,H)$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $r_o(G,P_n)$ for fixed $G$, where $P_n$ is the monotone ordered path. We prove an $O(n \log_2n)$ bound on $r_o(G,P_n)$ for all $G$ and an $O(n)$ bound when $G$ is $3$-ichromatic; we partially classify graphs $G$ with $r_o(G,P_n) = n + O(1)$. Many of these results extend to $r_o(G,C_n)$, where $C_n$ is an ordered cycle obtained from $P_n$ by adding one edge.Open AccessOnline Ramsey numbers of ordered paths and cycles
An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $G$ and $H$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $G$ or a blue $H$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $r_o(G,H)$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $r_o(G,P_n)$ for fixed $G$, where $P_n$ is the monotone ordered path. We prove an $O(n \log_2n)$ bound on $r_o(G,P_n)$ for all $G$ and an $O(n)$ bound when $G$ is $3$-ichromatic; we partially classify graphs $G$ with $r_o(G,P_n) = n + O(1)$. Many of these results extend to $r_o(G,C_n)$, where $C_n$ is an ordered cycle obtained from $P_n$ by adding one edge. - 11 January 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 73 (3) , 764-784
Almost Congruent Triangles
- 11 January 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 73 (3) , 764-784
Almost Congruent Triangles
- Open Access
- 22 December 2023
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 3 (3)
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 forcing density of a pair \((m,f)\) is \[ \sigma_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.Mathematics Subject Classifications: 05C35, 05C65Keywords: Induced hypergraphs, forcing density- 22 December 2023
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 3 (3)
Open AccessUnavoidable 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 forcing density of a pair \((m,f)\) is \[ \sigma_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.Mathematics Subject Classifications: 05C35, 05C65Keywords: Induced hypergraphs, forcing density - Open Access
- 12 December 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (1) , 57-66
Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza
An edge‐coloring of a complete graph with a set of colors is called completely balanced if any vertex is incident to the same number of edges of each color from . Erdős and Tuza asked in 1993 whether for any graph on edges and any completely balanced coloring of any sufficiently large complete graph using colors contains a rainbow copy of . This question was restated by Erdős in his list of “Some of my favourite problems on cycles and colourings.” We answer this question in the negative for most cliques by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph .
- 12 December 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (1) , 57-66
Open AccessRainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza
An edge‐coloring of a complete graph with a set of colors is called completely balanced if any vertex is incident to the same number of edges of each color from . Erdős and Tuza asked in 1993 whether for any graph on edges and any completely balanced coloring of any sufficiently large complete graph using colors contains a rainbow copy of . This question was restated by Erdős in his list of “Some of my favourite problems on cycles and colourings.” We answer this question in the negative for most cliques by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph .
- Open Access
- 14 July 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (3) , P3.17
Balanced Edge-Colorings Avoiding Rainbow Cliques of Size Four
A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete graph on $n=13^k$ vertices, for every positive integer $k$, with no rainbow $K_4$. This solves a problem by Erdős and Tuza.- 14 July 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (3) , P3.17
Open AccessBalanced Edge-Colorings Avoiding Rainbow Cliques of Size Four
A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete graph on $n=13^k$ vertices, for every positive integer $k$, with no rainbow $K_4$. This solves a problem by Erdős and Tuza. - Open Access
A note on balanced edge-colorings avoiding rainbow cliques of size four
A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete graph on $n=13^k$ vertices, for every positive integer $k$, with no rainbow $K_4$. This solves a problem by Erdős and Tuza.Open AccessA note on balanced edge-colorings avoiding rainbow cliques of size four
A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete graph on $n=13^k$ vertices, for every positive integer $k$, with no rainbow $K_4$. This solves a problem by Erdős and Tuza. - Open Access
Almost Congruent Triangles
Almost $50$ years ago Erdős and Purdy asked the following question: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least $\left\lfloor \frac{n}{3} \right\rfloor \cdot \left\lfloor \frac{n+1}{3} \right\rfloor \cdot \left\lfloor \frac{n+2}{3} \right\rfloor$ such approximate copies. In this paper we provide a matching upper bound and thereby answer their question. More generally, for every triangle $T$ we determine the maximum number of approximate congruent triangles to $T$ in a point set of size $n$. Parts of our proof are based on hypergraph Turán theory: for each point set in the plane and a triangle $T$, we construct a $3$-uniform hypergraph $\mathcal{H}=\mathcal{H}(T)$, which contains no hypergraph as a subgraph from a family of forbidden hypergraphs $\mathcal{F}=\mathcal{F}(T)$. Our upper bound on the number of edges of $\mathcal{H}$ will determine the maximum number of triangles that are approximate congruent to $T$.Open AccessAlmost Congruent Triangles
Almost $50$ years ago Erdős and Purdy asked the following question: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least $\left\lfloor \frac{n}{3} \right\rfloor \cdot \left\lfloor \frac{n+1}{3} \right\rfloor \cdot \left\lfloor \frac{n+2}{3} \right\rfloor$ such approximate copies. In this paper we provide a matching upper bound and thereby answer their question. More generally, for every triangle $T$ we determine the maximum number of approximate congruent triangles to $T$ in a point set of size $n$. Parts of our proof are based on hypergraph Turán theory: for each point set in the plane and a triangle $T$, we construct a $3$-uniform hypergraph $\mathcal{H}=\mathcal{H}(T)$, which contains no hypergraph as a subgraph from a family of forbidden hypergraphs $\mathcal{F}=\mathcal{F}(T)$. Our upper bound on the number of edges of $\mathcal{H}$ will determine the maximum number of triangles that are approximate congruent to $T$. - Open Access
The Spectrum of Triangle-free Graphs
Denote by $q_n(G)$ the smallest eigenvalue of the signless Laplacian matrix of an $n$-vertex graph $G$. Brandt conjectured in 1997 that for regular triangle-free graphs $q_n(G) \leq \frac{4n}{25}$. We prove a stronger result: If $G$ is a triangle-free graph then $q_n(G) \leq \frac{15n}{94}< \frac{4n}{25}$. Brandt's conjecture is a subproblem of two famous conjectures of Erd\H{o}s: (1) Sparse-Half-Conjecture: Every $n$-vertex triangle-free graph has a subset of vertices of size $\lceil\frac{n}{2}\rceil$ spanning at most $n^2/50$ edges. (2) Every $n$-vertex triangle-free graph can be made bipartite by removing at most $n^2/25$ edges. In our proof we use linear algebraic methods to upper bound $q_n(G)$ by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.Open AccessThe Spectrum of Triangle-free Graphs
Denote by $q_n(G)$ the smallest eigenvalue of the signless Laplacian matrix of an $n$-vertex graph $G$. Brandt conjectured in 1997 that for regular triangle-free graphs $q_n(G) \leq \frac{4n}{25}$. We prove a stronger result: If $G$ is a triangle-free graph then $q_n(G) \leq \frac{15n}{94}< \frac{4n}{25}$. Brandt's conjecture is a subproblem of two famous conjectures of Erd\H{o}s: (1) Sparse-Half-Conjecture: Every $n$-vertex triangle-free graph has a subset of vertices of size $\lceil\frac{n}{2}\rceil$ spanning at most $n^2/50$ edges. (2) Every $n$-vertex triangle-free graph can be made bipartite by removing at most $n^2/25$ edges. In our proof we use linear algebraic methods to upper bound $q_n(G)$ by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras. - Open Access
Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza
An edge-coloring of a complete graph with a set of colors $C$ is called completely balanced if any vertex is incident to the same number of edges of each color from $C$. Erd\H{o}s and Tuza asked in $1993$ whether for any graph $F$ on $\ell$ edges and any completely balanced coloring of any sufficiently large complete graph using $\ell$ colors contains a rainbow copy of $F$. This question was restated by Erd\H{o}s in his list of ``Some of my favourite problems on cycles and colourings''. We answer this question in the negative for most cliques $F=K_q$ by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph $F$.Open AccessRainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza
An edge-coloring of a complete graph with a set of colors $C$ is called completely balanced if any vertex is incident to the same number of edges of each color from $C$. Erd\H{o}s and Tuza asked in $1993$ whether for any graph $F$ on $\ell$ edges and any completely balanced coloring of any sufficiently large complete graph using $\ell$ colors contains a rainbow copy of $F$. This question was restated by Erd\H{o}s in his list of ``Some of my favourite problems on cycles and colourings''. We answer this question in the negative for most cliques $F=K_q$ by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph $F$.