TRIPLE-PRODUCT-FREE SETS AGIGOR-MIKE, PRECIOUS U.; HART, SARAH B.; OBI, MARTIN C.
Bulletin of the Australian Mathematical Society,
10/2023
Journal Article
Peer reviewed
Abstract
In this paper, we study triple-product-free sets, which are analogous to the widely studied concept of product-free sets. A nonempty subset
S
of a group
G
is
triple-product-free
if
$abc ...\notin S$
for all
$a, b, c \in S$
. If
S
is triple-product-free and is not a proper subset of any other triple-product-free set, we say that
S
is locally maximal. We classify all groups containing a locally maximal triple-product-free set of size 1. We then derive necessary and sufficient conditions for a subset of a group to be locally maximal triple-product-free, and conclude with some observations and comparisons with the situation for standard product-free sets.
For a topological space X we propose to call a subsetS⊂Xfree in X if it admits a well-ordering that turns it into a free sequence in X. The well-known cardinal function F(X) is then definable as ...sup{|S|:S is free in X} and will be called the free set number of X.
We prove several new inequalities involving F(X) and F(Xδ), where Xδ is the Gδ-modification of X:•L(X)≤22F(X) if X is T2 and L(X)≤2F(X) if X is T3;•|X|≤22F(X)⋅ψc(X)≤22F(X)⋅χ(X) for any T2-space X;•F(Xδ)≤222F(X) if X is T2 and F(Xδ)≤22F(X) if X is T3.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Recall that a subset X of a group G is ‘product-free’ if X2∩X=∅, i.e. if xy∉X for all x,y∈X. Let G be a group definable in a distal structure. We prove there are constants c>0 and δ∈(0,1) such that ...every finite subset X⊆G distinct from {1} contains a product-free subset of size at least δ|X|c+1/|X2|c. In particular, every finite k-approximate subgroup of G distinct from {1} contains a product-free subset of density at least δ/kc.
The proof is short, and follows quickly from Ruzsa calculus and an iterated application of Chernikov and Starchenko's distal regularity lemma.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The main result of this paper is that, under PFA, for every regular space X with F(X) = \omega we have |X| \le w(X)^\omega; in particular, w(X) \le \mathfrak {c} implies |X| \le \mathfrak {c}. This ...complements numerous prior results that yield consistent examples of even compact Hausdorff spaces X with F(X) = \omega such that w(X) = \mathfrak {c} and |X| = 2^\mathfrak {c}.
We also show that regularity cannot be weakened to the Hausdorff property in this result because we can find in ZFC a Hausdorff space X with F(X) = \omega such that w(X) = \mathfrak {c} and |X| = 2^\mathfrak {c}. In fact, this space X has the strongly anti-Urysohn (SAU) property that any two infinite closed sets in X intersect, which is much stronger than F(X) = \omega. Moreover, any non-empty open set in X also has size 2^\mathfrak {c}, and thus our example answers one of the main problems of both Juhász, Soukup, and Szentmiklóssy Topology Appl. 213 (2016), pp. 8–23 and Juhász, Shelah, Soukup, and Szentmiklóssy Topology Appl. 323 (2023), Paper No. 108288, 15 pp. by providing in ZFC a SAU space with no isolated points.
On a problem of Angelo Bella Juhász, István; Soukup, Lajos; Szentmiklóssy, Zoltán
Topology and its applications,
12/2023, Volume:
340
Journal Article
Peer reviewed
Open access
The main result of this note is the following theorem.
If X is any Hausdorff space withκ=Fˆ(X)⋅μˆ(X)thenL(X<κ)≤ϱ(κ).
Here Fˆ(X) is the smallest cardinal φ so that |S|<φ for any set S that is free in ...X and μˆ(X) is the smallest cardinal μ so that, for every set S that is free in X, any open cover of S‾ has a subcover of size <μ. Moreover, X<κ is the G<κ-modification of X and ϱ(κ)=min{ϱ:ϱ<κ=ϱ}.
As a corollary we obtain that if X is a linearly Lindelöf regular space of countable tightness then L(Xδ)≤c, provided that c=2<c. This yields a consistent affirmative answer to a question of Angelo Bella.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let fr(n,v,e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, in which the union of any e distinct edges contains at least v+1 vertices. The study of fr(n,v,e) was ...initiated by Brown, Erdős and Sós more than forty years ago. In the literature, the following conjecture is well known.
Conjecture:nk−o(1)<fr(n,er−(e−1)k+1,e)=o(nk) holds for all fixed integers r>k≥2 and e≥3 as n→∞.
For r=3,e=3,k=2, the bound n2−o(1)<f3(n,6,3)=o(n2) was proved by the celebrated (6,3)-theorem of Ruzsa and Szemerédi. In this paper, we add more evidence for the validity of the conjecture. On one hand, using the hypergraph removal lemma we show that the upper bound part of the conjecture is true for all fixed integers r≥k+1≥e≥3. On the other hand, using tools from additive number theory we present several constructions showing that the lower bound part of the conjecture is true for r≥3, k=2 and e=4,5,7,8. Prior to our results, all known constructions that match the conjectured lower bound satisfy either r=3 or e=3. Our constructions are the first ones in the literature that break this barrier.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
This paper deals with extensions of free sets over commutative semirings. First, we discuss a necessary and sufficient condition that a finitely generated
-semimodule is free, and by the way, we give ...a necessary and sufficient condition that a finite set in a finitely generated
-semimodule is free. We then use these necessary and sufficient conditions to investigate the conditions that a free set in a finitely generated
-semimodule can be extended to a free basis.
Full text
Available for:
BFBNIB, GIS, IJS, KISLJ, NUK, PNG, UL, UM, UPUK
Given a linear equation L, a set A of integers is L-free if A does not contain any non-trivial solutions to L. Meeks and Treglown (2018) showed that for certain kinds of linear equations, it is ...NP-complete to decide if a given set of integers contains a solution-free subset of a given size. Also, for equations involving three variables, they showed that the problem of determining the size of the largest solution-free subset is APX-hard, and that for two such equations (representing sum-free and progression-free sets), the problem of deciding if there is a solution-free subset with at least a specified proportion of the elements is also NP-complete.
We answer a number of questions posed by Meeks and Treglown, by extending the results above to all linear equations, and showing that the problems remain hard for sets of integers whose elements are polynomially bounded in the size of the set. For most of these results, the integers can all be positive as long as the coefficients do not all have the same sign.
We also consider the problem of counting the number of solution-free subsets of a given set, and show that this problem is #P-complete for any linear equation in at least three variables.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We study four families of consequences of Ramsey's Theorem from the viewpoint of reverse mathematics. The first, which we call the Achromatic Ramsey Theorem, is from a partition relation introduced ...by Erdős, Hajnal and Rado: ω→ωc,≤dr, which asserts that for every f:ωr→c there exists an infinite H with |f(Hr)|≤d. The second and third are the Free Set Theorem and the Thin Set Theorem, which were introduced by Harvey Friedman. And the last is the Rainbow Ramsey Theorem. We show that, most theorems from these families are quite weak, i.e., they are strictly weaker than ACA0 over RCA0. Interestingly, these families turn out to be closely related. We establish the so-called strong cone avoidance property of most instances of the Achromatic Ramsey Theorem by an induction of exponents, then apply this and a similar induction to obtain the strong cone avoidance property of the Free Set Theorem. From the strong cone avoidance property of the Achromatic Ramsey Theorem and the Free Set Theorem, we derive the strong cone avoidance property of the Thin Set Theorem and the Rainbow Ramsey Theorem. It follows easily that a theorem with the strong cone avoidance property does not imply ACA0 over RCA0.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP