Search

Given a finite set satisfying condition $\mathcal{A}$, the subset selection problem asks, how large of a subset satisfying condition $\mathcal{B}$ can we find? We make progress on three instances of subset selection problems in planar point sets. Let $n,s\in\mathbb{N}$ with $n\geq s$, and let $P\subseteq\mathbb{R}^2$ be a set of $n$ points, where at most $s$ points lie on the same line. Firstly, we select a general position subset of $P$, i.e., a subset containing no $3$ points on the same line. This problem was proposed by Erd\H{o}s under the regime when $s$ is a constant. For $s$ being non-constant, we give new lower and upper bounds on the maximum size of such a subset. In particular, we show that in the worst case such a set can have size at most $O(n/s)$ when $n^{1/3}\leq s\leq n$ and $O(n^{5/6+o(1)}/\sqrt{s})$ when $3\leq s\leq n^{1/3}$. Secondly, we select a monotone general position subset of $P$, that is, a subset in general position where the points are ordered from left to right and their $y$-coordinates are either non-decreasing or non-increasing. We present bounds on the maximum size of such a subset. In particular, when $s=\Theta(\sqrt{n})$, our upper and lower bounds differ only by a logarithmic factor. Lastly, we select a subset of $P$ with pairwise distinct slopes. This problem was initially studied by Erd\H{o}s, Graham, Ruzsa, and Taylor on the grid. We show that for $s=O(\sqrt{n})$ such a subset of size $\Omega((n/\log{s})^{1/3})$ can always be found in $P$. When $s=\Theta(\sqrt{n})$, this matches a lower bound given by Zhang on the grid. As for the upper bound, we show that in the worst case such a subset has size at most $O(\sqrt{n})$ for $2\leq s\leq n^{3/8}$ and $O((n/s)^{4/5})$ for $n^{3/8}\leq s=O(\sqrt{n})$. The proofs use a wide range of tools such as incidence geometry, probabilistic methods, the hypergraph container method, and additive combinatorics., Comment: 19 pages, 4 figures, comments are welcome

Many problems in extremal combinatorics can be reduced to determining the independence number of a specific auxiliary hypergraph. We present two such problems, one from discrete geometry and one from hypergraph Tur\'an theory. Using results on hypergraph colorings by Cooper-Mubayi and Li-Postle, we demonstrate that for those two problems the trivial lower bound on the independence number can be improved upon: Erd\H{o}s, Graham, Ruzsa and Taylor asked to determine the largest size, denoted by $g(n)$, of a subset $P$ of the grid $[n]^2$ such that every pair of points in $P$ span a different slope. Improving on a lower bound by Zhang from 1993, we show that $$g(n)=\Omega \left( \frac{n^{2/3} (\log \log n)^{1/3} }{ \log^{1/3}n} \right).$$ Let $H^r_3$ denote an $r$-graph with $r+1$ vertices and $3$ edges. Recently, Sidorenko proved the following lower bounds for the Tur\'an density of this $r$-graph: $\pi(H^r_3)\geq r^{-2}$ for every $r$, and $\pi(H^r_3)\geq (1.7215 - o(1)) r^{-2}$. We present an improved asymptotic bound: $\pi(H^r_3)=\Omega\left(r^{-2} \log^{1/2} r \right).$

The billiard table is modeled as an $n$-dimensional box $[0,a_1]\times [0,a_2]\times \ldots \times [0,a_n] \subset \mathbb{R}^n$, with each side having real-valued lengths $a_i$ that are pairwise commensurable. A ball is launched from the origin in direction $d=(1,1,\ldots,1)$. The ball is reflected if it hits the boundary of the billiard table. It comes to a halt when reaching a corner. We show that the number of intersections of the billiard curve at any given point on the table is either $0$ or a power of $2$. To prove this, we use algebraic and number theoretic tools to establish a bijection between the number of intersections of the billiard curve and the number of satisfying assignments of a specific constraint satisfaction problem.

Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$ where $k \geq 2$. According to an old result of Bollob\'as and Meir (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} \leq 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 \geq 2$ and $n \geq 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{\'a}s and Meir showed that one can take $c_k = 9 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \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 \geq 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\'as--Meir conjecture is proposed.

Almost $50$ years ago Erd\H{o}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\'an 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$.

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\H{o}s and Tuza., Comment: 2 pages

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.

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$., Comment: 8 pages

Erd\H{o}s, F\"uredi, Rothschild and S\'os 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 $$ \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.

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\"uredi on the Tur\'an number of $F_5:=F_5^0$. Our results extend a theory of Erd\H{o}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\'an density.

Artificial intelligence (AI), machine learning, and deep learning (DL) methods are becoming increasingly important in the field of biomedical image analysis. However, to exploit the full potential of such methods, a representative number of experimentally acquired images containing a significant number of manually annotated objects is needed as training data. Here we introduce SYNTA (synthetic data) as a novel approach for the generation of synthetic, photo-realistic, and highly complex biomedical images as training data for DL systems. We show the versatility of our approach in the context of muscle fiber and connective tissue analysis in histological sections. We demonstrate that it is possible to perform robust and expert-level segmentation tasks on previously unseen real-world data, without the need for manual annotations using synthetic training data alone. Being a fully parametric technique, our approach poses an interpretable and controllable alternative to Generative Adversarial Networks (GANs) and has the potential to significantly accelerate quantitative image analysis in a variety of biomedical applications in microscopy and beyond.

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.

We will state 10 problems, and solve some of them, for partitions in triangle-free graphs related to Erd\H{o}s' Sparse Half Conjecture. Among others we prove the following variant of it: For every sufficiently large even integer $n$ the following holds. Every triangle-free graph on $n$ vertices has a partition $V(G)=A\cup B$ with $|A|=|B|=n/2$ such that $e(G[A])+e(G[B])\leq n^2/16$. This result is sharp since the complete bipartite graph with class sizes $3n/4$ and $n/4$ achieves equality, when $n$ is a multiple of 4. Additionally, we discuss similar problems for $K_4$-free graphs.

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\'e, Spiegel and Szab\'o 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). \]

Tur\'an's famous tetrahedron problem is to compute the Tur\'an 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\'an'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., Comment: 23 pages

There are various different notions measuring extremality of hypergraphs. In this survey we compare the recently introduced notion of the codegree squared extremal function with the Tur\'an function, the minimum codegree threshold and the uniform Tur\'an density. The codegree squared sum $\textrm{co}_2(G)$ of a $3$-uniform hypergraph $G$ is defined to be the sum of codegrees squared $d(x,y)^2$ over all pairs of vertices $x,y$. In other words, this is the square of the $\ell_2$-norm of the codegree vector. We are interested in how large $\textrm{co}_2(G)$ can be if we require $G$ to be $H$-free for some $3$-uniform hypergraph $H$. This maximum value of $\textrm{co}_2(G)$ over all $H$-free $n$-vertex $3$-uniform hypergraphs $G$ is called the codegree squared extremal function, which we denote by $\textrm{exco}_2(n,H)$. We systemically study the extremal codegree squared sum of various $3$-uniform hypergraphs using various proof techniques. Some of our proofs rely on the flag algebra method while others use more classical tools such as the stability method. In particular, we (asymptotically) determine the codegree squared extremal numbers of matchings, stars, paths, cycles, and $F_5$, the $5$-vertex hypergraph with edge set $\{123,124,345\}$. Additionally, our paper has a survey format, as we state several conjectures and give an overview of Tur\'an densities, minimum codegree thresholds and codegree squared extremal numbers of popular hypergraphs. We intend to update the arXiv version of this paper regularly., Comment: comments are welcome

One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back to the work of Erd\H{o}s, Kleitman and Rothschild, who showed that the number of $K_r$-free graphs on $n$ vertices is $2^{\text{ex}(n,K_r)+o(n^2)}$. Their work was later extended to forbidding graphs as induced subgraphs by Pr\"omel and Steger. Here, we consider one of the most basic counting problems for $3$-graphs. Let $E_1$ be the $3$-graph with $4$ vertices and $1$ edge. What is the number of induced $\{K_4^3,E_1\}$-free $3$-graphs on $n$ vertices? We show that the number of such $3$-graphs is of order $n^{\Theta(n^2)}$. More generally, we determine asymptotically the number of induced $\mathcal{F}$-free $3$-graphs on $n$ vertices for all families $\mathcal{F}$ of $3$-graphs on $4$ vertices. We also provide upper bounds on the number of $r$-graphs on $n$ vertices which do not induce $i \in L$ edges on any set of $k$ vertices, where $L \subseteq \big \{0,1,\ldots,\binom{k}{r} \big\}$ is a list which does not contain $3$ consecutive integers in its complement. Our bounds are best possible up to a constant multiplicative factor in the exponent when $k = r+1$. The main tool behind our proof is counting the solutions of a constraint satisfaction problem., Comment: 18 pages

A well-known conjecture by Erd\H{o}s states that every triangle-free graph on $n$ vertices can be made bipartite by removing at most $n^2/25$ edges. This conjecture was known for graphs with edge density at least $0.4$ and edge density at most $0.172$. Here, we will extend the edge density for which this conjecture is true; we prove the conjecture for graphs with edge density at most $0.2486$ and for graphs with edge density at least $0.3197$. Further, we prove that every triangle-free graph can be made bipartite by removing at most $n^2/23.5$ edges improving the previously best bound of $n^2/18$., Comment: This is an extended abstract submitted to EUROCOMB 2021. Comments are welcome

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\'ar\'any and F\"uredi 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\'an problems, we use flag algebras and stability techniques for the proof., Comment: 20 pages

The Erd\H{o}s-Szekeres Theorem stated in terms of graphs says that any red-blue coloring of the edges of the ordered complete graph $K_{rs+1}$ contains a red copy of the monotone increasing path with $r$ edges or a blue copy of the monotone increasing path with $s$ edges. Although $rs + 1$ is the minimum number of vertices needed for this result, not all edges of $K_{rs+1}$ are necessary. We characterize the subgraphs of $K_{rs+1}$ with this coloring property as follows: they are exactly the subgraphs that contain all the edges of a graph we call the circus tent graph $CT(r,s)$. Additionally, we use similar proof techniques to improve upon some of the bounds on the online ordered size Ramsey number of a path given by P\'erez-Gim\'enez, Pralat, and West., Comment: 16 pages

A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masa\v{r}\'ik and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\varepsilon$-flexible for list size $5$., Comment: 18 pages, 4 figures

Mantel's theorem states that every $n$-vertex graph with $\lfloor \frac{n^2}{4} \rfloor +t$ edges, where $t>0$, contains a triangle. The problem of determining the minimum number of triangles in such a graph is usually referred to as the Erd\H{o}s-Rademacher problem. Lov\'asz and Simonovits proved that there are at least $t\lfloor n/2 \rfloor$ triangles in each of those graphs. Katona and Xiao considered the same problem under the additional condition that there are no $s-1$ vertices covering all triangles. They settled the case $t=1$ and $s=2$. Solving their conjecture, we determine the minimum number of triangles for every fixed pair of $s$ and $t$, when $n$ is sufficiently large. Additionally, solving another conjecture of Katona and Xiao, we extend the theory for considering cliques instead of triangles., Comment: Mistakes have been corrected