15 results on '"Leader, Imre"'
Search Results
2. Some New Results on Monochromatic Sums and Products in the Rationals
- Author
-
Hindman, Neil, Ivan, Maria-Romina, Leader, Imre, Ivan, Maria [0000-0003-0817-3777], and Apollo - University of Cambridge Repository
- Subjects
monochromatic sums and products ,FOS: Mathematics ,Mathematics - Combinatorics ,Ramsey Theory ,Combinatorics (math.CO) ,05D10, 11B13 - Abstract
Our aim in this paper is to show that, for any $k$, there is a finite colouring of the set of rationals whose denominators contain only the first $k$ primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a `uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic., Comment: 17 pages
- Published
- 2022
- Full Text
- View/download PDF
3. Some new results on monochromatic sums and products in the rationals.
- Author
-
Hindman, Neil, Ivan, Maria-Romina, and Leader, Imre
- Subjects
RAMSEY theory - Abstract
Our aim in this paper is to show that, for any k, there is a finite colouring of the set of rationals whose denominators contain only the first fc primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a 'uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic. [ABSTRACT FROM AUTHOR]
- Published
- 2023
4. A Ramsey characterisation of eventually periodic words.
- Author
-
Ivan, Maria‐Romina, Leader, Imre, and Zamboni, Luca Q.
- Subjects
- *
FACTORIZATION , *RAMSEY numbers , *RAMSEY theory , *VOCABULARY , *COLOR , *SUFFIXES & prefixes (Grammar) , *FINITE, The - Abstract
A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ of an infinite word x$x$ on alphabet X$X$ is called 'monochromatic', for a given colouring of the finite words X∗$X^*$ on alphabet X$X$, if each ui$u_i$ is the same colour. Wojcik and Zamboni proved that the word x$x$ is periodic if and only if for every finite colouring of X∗$X^*$ there is a monochromatic factorisation of x$x$. On the other hand, it follows from Ramsey's theorem that, for any word x$x$, for every finite colouring of X∗$X^*$ there is a suffix of x$x$ having a monochromatic factorisation. A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ is called 'super‐monochromatic' if each word uk1uk2⋯ukn$u_{k_1} u_{k_2} \cdots u_{k_n}$, where k1<⋯
- Published
- 2022
- Full Text
- View/download PDF
5. Monochromatic infinite sumsets.
- Author
-
Leader, Imre and Russell, Paul A.
- Subjects
- *
VECTOR spaces - Abstract
We show that there is a rational vector space V such that, whenever V is finitely coloured, there is an infinite set X whose sumset X + X is monochromatic. Our example is the rational vector space of dimension sup{..., ...). This complements a result of Hindman, Leader and Strauss, who showed that the result does not hold for dimension below ...w. So our result is best possible under GCH. [ABSTRACT FROM AUTHOR]
- Published
- 2020
6. PARTITION REGULARITY WITHOUT THE COLUMNS PROPERTY.
- Author
-
BARBER, BEN, HINDMAN, NEIL, LEADER, IMRE, and STRAUSS, DONA
- Subjects
INFINITE matrices ,COLUMNS ,PARTITIONS (Mathematics) ,RAMSEY theory ,NATURAL numbers - Abstract
A finite or infinite matrix A with rational entries is called partition regular if whenever the natural numbers are finitely coloured there is a monochromatic vector x with Ax = 0. Many of the classical theorems of Ramsey Theory may naturally be interpreted as assertions that particular matrices are partition regular. In the finite case, Rado proved that a matrix is partition regular if and only it satisfies a computable condition known as the columns property. The first requirement of the columns property is that some set of columns sums to zero. In the infinite case, much less is known. There are many examples of matrices with the columns property that are not partition regular, but until now all known examples of partition regular matrices did have the columns property. Our main aim in this paper is to show that, perhaps surprisingly, there are infinite partition regular matrices without the columns property -- in fact, having no set of columns summing to zero. We also make a conjecture that if a partition regular matrix (say with integer coefficients) has bounded row sums then it must have the columns property, and prove a first step towards this. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
7. Transitive sets in Euclidean Ramsey theory
- Author
-
Leader, Imre, Russell, Paul A., and Walters, Mark
- Subjects
- *
SET theory , *MULTIPLY transitive groups , *RAMSEY theory , *MATHEMATICAL proofs , *SYMMETRY groups , *EMBEDDING theorems - Abstract
Abstract: A finite set X in some Euclidean space is called Ramsey if for any k there is a d such that whenever is k-coloured it contains a monochromatic set congruent to X. This notion was introduced by Erdős, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory. In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever ‘rival’ conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively—in other words, if all points of the set look the same—our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement. Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
8. Independence for partition regular equations
- Author
-
Leader, Imre and Russell, Paul A.
- Subjects
- *
GRAPH theory , *MATRICES (Mathematics) , *COMBINATORICS , *UNIVERSAL algebra - Abstract
Abstract: A matrix A is said to be partition regular (PR) over a subset S of the positive integers if whenever S is finitely coloured, there exists a vector x, with all elements in the same colour class in S, which satisfies . We also say that S is PR for A. Many of the classical theorems of Ramsey Theory, such as van der Waerden''s theorem and Schur''s theorem, may naturally be interpreted as statements about partition regularity. Those matrices which are partition regular over the positive integers were completely characterised by Rado in 1933. Given matrices A and B, we say that A Rado-dominates B if any set which is PR for A is also PR for B. One trivial way for this to happen is if every solution to actually contains a solution to . Bergelson, Hindman and Leader conjectured that this is the only way in which one matrix can Rado-dominate another. In this paper, we prove this conjecture for the first interesting case, namely for matrices. We also show that, surprisingly, the conjecture is not true in general. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
9. Consistency for partition regular equations
- Author
-
Leader, Imre and Russell, Paul A.
- Subjects
- *
COMPUTATIONAL mathematics , *PARTITIONS (Mathematics) , *EQUATIONS , *NUMBER theory - Abstract
Abstract: It is easy to deduce from Ramsey''s theorem that given positive integers and a finite colouring of the set of positive integers, there exists an injective sequence with all sums of the form () lying in the same colour class. The consistency version of this result, namely that given positive integers and , and a finite colouring of , there exist injective sequences and with all sums of the form and all sums of the form () in the same colour class, was open for some time, being recently proved by Hindman, Leader and Strauss. The proof is long and relies heavily on the structure of the semigroup of ultrafilters on . Our aim in this note is to present a short proof of this result which does not use properties of . Our proof also gives various results not obtainable by the previous method of proof. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
10. Independent Deuber sets in graphs on the natural numbers
- Author
-
Gunderson, David S., Leader, Imre, Prömel, Hans Jürgen, and Rödl, Vojtěch
- Subjects
- *
SET theory , *RAMSEY theory , *GRAPH theory - Abstract
We show that for any
k,m,p,c, ifG is aKk -free graph onN then there is an independent set of vertices inG that contains an(m,p,c) -set. Hence ifG is aKk -free graph onN , then one can solve any partition regular system of equations in an independent set. This is a common generalization of partition regularity theorems of Rado (who characterized systems of linear equationsAx=0 a solution of which can be found monochromatic under any finite coloring ofN ) and Deuber (who provided another characterization in terms of(m,p,c) -sets and a partition theorem for them), and of Ramsey''s theorem itself. [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF
11. The Semigroup of Ultrafilters Near 0.
- Author
-
Hindman, Neil and Leader, Imre
- Subjects
- *
SEMIGROUPS (Algebra) , *ULTRAFILTERS (Mathematics) , *RAMSEY theory , *IDEMPOTENTS - Abstract
The set 0+ of ultrafilters on (0,1) that converge to 0 is a semigroup under the restriction of the usual operation + on &BetaR[subd] the Stone-Çech compactification of the discrete semigroup (R[subd], +). It is also a subsemigroup of Β((0, 1)[subd]). The interaction of these operations has recently yielded some strong results in Ramsey Theory. Since (0[sup+],.) is an ideal of &Beta((0, 1)[subd],.), much is known about the structure of (0[sup+],.). On the other hand, (0[sup+],+) is far from being an ideal of (ΒR[subd],+) so little about its algebraic structure follows from known results. We characterize here the smallest ideal of (0[sup+],+), its closure, and those sets "central" in (0[sup+],+), that is, those sets which are members of minimal idempotents in (0[sup+],+). We derive new combinatorial applications of those sets that are central in (0[sup+],+). [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
12. A note on feebly continuous functions
- Author
-
Leader, Imre
- Subjects
- *
CONTINUOUS functions , *RAMSEY theory , *CONTINUITY , *CONTINUUM hypothesis , *SET theory , *MATHEMATICS - Abstract
Abstract: A function f from to is said to be feebly continuous at a point if there exist sequences and with . Dales asked if every function has a point of feeble continuity. Our aim in this short note is to show that (assuming the Continuum Hypothesis) the answer is ‘no’. Dales also asked what happens for functions taking only two values: we show that in this case the answer is ‘yes’. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
13. Poset saturation and other combinatorial results
- Author
-
Ivan, Maria and Leader, Imre
- Subjects
Extremal combinatorics ,Poset saturation ,Ramsey theory - Abstract
In this dissertation we discuss a number of combinatorial results. These results fall into four broad areas: poset saturation, Ramsey theory, pursuit and evasion, and union-closed families. Chapter 2 is dedicated to the area of poset saturation. Given a finite poset P, we call a family F of subsets of [n] P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The size of the smallest P-saturated family with ground set [n] is called the induced saturated number of P, which is denoted by sat∗(n,P). In this chapter we look at four posets: the butterfly, the diamond, the antichain and the poset N . We establish a linear lower bound for the butterfly, a lower bound of(2√2 − o(1))√n for the diamond, a lower bound of √n for the poset N , and the exact saturation number for the 5-antichain and the 6-antichain. Chapter 3 is dedicated to two different Ramsey theory questions. In Section 3.1 we establish a Ramsey characterisation of eventually periodic words. More precisely, for a finite colouring of X∗ (the set of finite words on alphabet X) we say that a factorisation x = u1u2 · · · of an infinite word x is 'super-monochromatic' if each word uk1 uk2 · · · ukn, where k1 < · · · < kn, is the same colour. We show that a word x is eventually periodic if and only if for every finite colouring of X∗ there is a suffix of x having a super-monochromatic factorisation. This has been a conjecture for quite some time. In Section 3.2 we investigate the question of whether or not, given a finite colouring of the rationals or the reals, we can find an infinite subset with the property that the set of all its finite sums and products is monochromatic. The main result of this section is the existence of a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has the set of all of its finite sums and products monochromatic. In Chapter 4 we explore the game of cops and robbers on infinite graphs. The main question is: for which graphs can one guarantee that the cop has a winning strategy? In the finite case these graphs are precisely the 'constructible' graphs, but the infinite case is not well understood. For example, we exhibit a graph that is cop-win but not constructible. This is the first known such example. On the other hand, every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). We also investigate how this notion relates to the notion of 'locally constructible' (every finite graph is contained in a finite constructible subgraph). The main result of this chapter is the construction of a locally constructible graph that is not a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. Finally, in Chapter 5 we discuss the union-closed conjecture which asserts that for any union-closed family of sets, there exists an element of the ground set contained in at least half of the sets of the family. Our attention is on the small sets of union-closed families. More precisely, we construct a class of union-closed families of sets such that the frequency of the elements of the minimal sets is o(1) - so that these elements are not generally in half of the sets of union-closed families.
- Published
- 2023
- Full Text
- View/download PDF
14. Tilings and other combinatorial results
- Author
-
Gruslys, Vytautas and Leader, Imre Bennett
- Subjects
511 ,Combinatorics ,Tilings ,Combinatorial Geometry ,Extremal Graph Theory ,Ramsey Theory - Abstract
In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.
- Published
- 2018
- Full Text
- View/download PDF
15. Partition regularity in the rationals.
- Author
-
Barber, Ben, Hindman, Neil, and Leader, Imre
- Subjects
- *
MATHEMATICAL regularization , *PARTITIONS (Mathematics) , *LINEAR equations , *MATHEMATICAL proofs , *NATURAL numbers - Abstract
Abstract: A system of homogeneous linear equations with integer coefficients is partition regular if, whenever the natural numbers are finitely coloured, the system has a monochromatic solution. The Finite Sums theorem provided the first example of an infinite partition regular system of equations. Since then, other such systems of equations have been found, but each can be viewed as a modification of the Finite Sums theorem. We present here a new infinite partition regular system of equations that appears to arise in a genuinely different way. This is the first example of a partition regular system in which a variable occurs with unbounded coefficients. A modification of the system provides an example of a system that is partition regular over but not , settling another open problem. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.