Erdős–Szekeres Theorem for Lines

According to the Erd?s–Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd?s–Szekeres theorem.     

Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set \(\mathcal{P}\) of n points determines o(n) distinct distances, then no line contains Ω(n ^7/8) points of \(\mathcal{P}\) and no circle contains Ω(n ^5/6) points of \(\mathcal{P}\).We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20].A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.     

An Erdős-Ko-Rado theorem for finite classical polar spaces

Consider a finite classical polar space of rank \(d\ge 2\) and an integer n with \(0<n<d\). In this paper, it is proved that the set consisting of all subspaces of rank n that contain a given point is a largest Erd?s-Ko-Rado set of subspaces of rank n of the polar space. We also show that there are no other Erd?s-Ko-Rado sets of subspaces of rank n of the same size.     

Simplexes in a normed space

Is it true that any set of n + 1 points in Rⁿ can be isometrically embedded into any n-dimensional real normed apace? For n ≥ 3, the answer to this question is unknown to the author of this paper. For n = 2, it is clear that the answer is positive. For n = 3, the problem is reduced to the case where four points lie in a plane. A certain reduction is assigned for arbitrary n.     

An axiomatic look at the Erdős-Trost problem

The Erd?s-Trost problem can be formulated in the following way: “If the triangle XY Z is inscribed in the triangle ABC—with X, Y, and Z on the sides BC, CA, and AB, respectively—then one of the areas of the triangles BXZ, CXY , AY Z is less than or equal to the area of the triangle XY Z.” There are many different solutions for this problem. In this note we take up a very elementary proof (due to Szekeres) and deduce that the class of ordered translation planes is the level in the hierarchy of affine planes where the Erd?s-Trost statement still holds true. We also look at the conditions an absolute plane needs to satisfy for the validity of the Erd?s-Trost statement.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Independence numbers of random subgraphs of a distance graph

We consider the so-called distance graph G(n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G(n, 3, 1) in the Erd?s–Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, 3, 1).     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

Tightness games with bounded finite selections

For a topological space X and a point x ∈ X, consider the following game—related to the property of X being countably tight at x. In each inning n ∈ ω, the first player chooses a set A _n that clusters at x, and then the second player picks a point a _n ∈ A _n ; the second player is the winner if and only if \(x \in \overline {\left\{ {{a_n}:n \in \omega } \right\}} \).In this work, we study variations of this game in which the second player is allowed to choose finitely many points per inning rather than one, but in which the number of points they are allowed to choose in each inning has been fixed in advance. Surprisingly, if the number of points allowed per inning is the same throughout the play, then all of the games obtained in this fashion are distinct. We also show that a new game is obtained if the number of points the second player is allowed to pick increases at each inning.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

A Munn type representation of abundant semigroups with a multiplicative ample transversal

In this note, we consider the Erd?s–Straus Diophantine equation

$$\begin{aligned} \frac{c}{n}=\frac{1}{x} + \frac{1}{y} + \frac{1}{z}, \end{aligned}$$

where n and c are positive integers with \(\gcd (n, c) = 1\). We provide a formula for the number f(n, c) of all positive integral solutions (x, y, z) of the equation. In 1948, Erd?s and Straus conjectured that \(f(n,4) \ge 1,\) for all integers \(n \ge 2\). Here, we solve the conjecture for a special case of n.

     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

A note on the Structure of Turán Densities of Hypergraphs

Let r ≥ 2 be an integer. A real number α ∈ [0, 1) is a jump for r if there exists c > 0 such that no number in (α, α + c) can be the Turán density of a family of r-uniform graphs. A result of Erd?s and Stone implies that every α ∈ [0, 1) is a jump for r = 2. Erd?s asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.     

Maximum union-free subfamilies

An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? A family of sets is called union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. We show that every family of m sets contains a union-free subfamily of size at least \(\left\lfloor {\sqrt {4m + 1} } \right\rfloor - 1\) and that this bound is tight. This solves Moser’s problem and proves a conjecture of Erd?s and Shelah from 1972.More generally, a family of sets is a-union-free if there are no a + 1 distinct sets in the family such that one of them is equal to the union of a others. We determine up to an absolute multiplicative constant factor the size of the largest guaranteed a-union-free subfamily of a family of m sets. Our result verifies in a strong form a conjecture of Barat, Füredi, Kantor, Kim and Patkos.     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.     

New Families of <Emphasis Type="Italic">n</Emphasis>-Clusters Verifying the Erdős–Faber–Lovász Conjecture

Erd?s, Faber and Lovász conjectured in 1972 that the vertices of a linear hypergraph with n edges, each of size n, can be strongly colored with n colors. It was shown by Romero and Sánchez-Arroyo that an equivalent conjecture is obtained when linear hypergraphs are replaced by n-clusters. In this paper we describe new families of EFL-compliant n-clusters; that is, those for which the conjecture holds. Moreover, we describe ways to extend some n-clusters to larger ones preserving EFL-compliance. Also, our approach allowed us to provide a new upper bound for the chromatic number of n-clusters.     

Hereditary normality of a space of the form ℱ(<Emphasis Type="Italic">X</Emphasis>)

Assuming the continuum hypothesis we construct an example of a nonmetrizable compact set X with the following properties(1) X ⁿ is hereditarily separable for all n ∈ ?(2) X ⁿ \ Δ _n is perfectly normal for every n ∈ ?, where Δ _n is the generalized diagonal of X ⁿ , i.e., the set of points with at least two equal coordinates(3) for every seminormal functor ? that preserves weights and the points of bijectivity the space ? _k (X) is hereditarily normal, where k is the second smallest element of the power spectrum of the functor ?; in particular, X ² and λ ₃ X are hereditarily normal.Our example of a space of this type strengthens the well-known example by Gruenhage of a nonmetrizable compact set whose square is hereditarily normal and hereditarily separable.     

An upper bound for the number of uniformly packed binary codes

Under study are the binary codes uniformly packed (in the wide sense) of length n with minimum distance d and covering radius ρ. It is shown that every code of this kind is uniquely determined by the set of its codewords of weights ?n/2? ? ρ, …, ?n/2? + ρ. For odd d, the number of distinct codes is at most

$2^{2^{n - \tfrac{3}{2}\log n + o(log n)} } $

.

     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.