12 results on '"Leader, Imre"'
Search Results
2. Decomposing the complete r-graph.
- Author
-
Leader, Imre, Milićević, Luka, and Tan, Ta Sheng
- Subjects
- *
HYPERGRAPHS , *DECOMPOSITION method , *BIPARTITE graphs , *PARTITIONS (Mathematics) , *MATHEMATICAL induction - Abstract
Let f r ( n ) be the minimum number of complete r -partite r -graphs needed to partition the edge set of the complete r -uniform hypergraph on n vertices. Graham and Pollak showed that f 2 ( n ) = n − 1 . An easy construction shows that f r ( n ) ≤ ( 1 − o ( 1 ) ) ( n ⌊ r / 2 ⌋ ) and it has been unknown if this upper bound is asymptotically sharp. In this paper we show that f r ( n ) ≤ ( 14 15 + o ( 1 ) ) ( n r / 2 ) for each even r ≥ 4 . [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. 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
4. Multiple cross-intersecting families of signed sets
- Author
-
Borg, Peter and Leader, Imre
- Subjects
- *
INTERSECTION theory , *SET theory , *CYCLIC permutations , *GROUP extensions (Mathematics) , *MATHEMATICAL analysis , *MATHEMATICAL statistics - Abstract
Abstract: A k-signed r-set on is an ordered pair , where A is an r-subset of and f is a function from A to . Families are said to be cross-intersecting if any set in any family intersects any set in any other family . Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of . Our aim is to generalise Hilton''s bound to one for families of k-signed r-sets on . The main tool developed is an extension of Katona''s cyclic permutation argument. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
5. 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
6. The Angel and the Devil in three dimensions
- Author
-
Bollobás, Béla and Leader, Imre
- Subjects
- *
ALGEBRAIC number theory , *NUMBER theory , *NUMERICAL analysis , *MATHEMATICAL analysis - Abstract
Abstract: Our main aim in this paper is to show that, in Conway''s Angel and Devil game, an Angel of sufficient speed can always escape in three dimensions. We also prove some related results and make some conjectures. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
7. 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
8. Independent Arithmetic Progressions in Clique-Free Graphs on the Natural Numbers
- Author
-
Gunderson, David S., Leader, Imre, Prömel, Hans Jürgen, and Rödl, Vojtěch
- Abstract
We show that if Gis a Kr-free graph on N, there is an independent set in Gwhich contains an arbitrarily long arithmetic progression together with its difference. This is a common generalization of theorems of Schur, van der Waerden, and Ramsey. We also discuss various related questions regarding (m, p, c)-sets and parameter words.
- Published
- 2001
- Full Text
- View/download PDF
9. Correlation for permutations.
- Author
-
Robert Johnson, J., Leader, Imre, and Long, Eoin
- Subjects
- *
MALVACEAE , *PERMUTATIONS , *MATHEMATICAL equivalence - Abstract
In this note we investigate correlation inequalities for 'up-sets' of permutations, in the spirit of the Harris–Kleitman inequality. We focus on two well-studied partial orders on S n , giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on S n , up-sets are positively correlated (in the Harris–Kleitman sense). Thus, for example, for a (uniformly) random permutation π , the event that no point is displaced by more than a fixed distance d and the event that π is the product of at most k adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure 1/2 whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
10. Additive and Multiplicative Ramsey Theory in the Reals and the Rationals
- Author
-
Bergelson, Vitaly, Hindman, Neil, and Leader, Imre
- Abstract
Let a finite partition Fof the real interval (0,1) be given. We show that if every member of Fis measurable or if every member of Fis a Baire set, then one member of Fmust contain a sequence with all of its finite sums and products (and, in the measurable case, all of its infinite sums as well). These results are obtained by using the algebraic structure of the Stone–Čech compactification of the real numbers with the discrete topology. They are also obtained by elementary methods. In each case we in fact get significant strengthenings of the above stated results (with different strengthenings obtained by the algebraic and elementary methods). Some related (although weaker) results are established for arbitrary partitions of the rationals and the dyadic rationals, and a counterexample is given to show that even weak versions of the combined additive and multiplicative results do not hold in the dyadic rationals.
- Published
- 1999
- Full Text
- View/download PDF
11. Distinguishing subgroups of the rationals by their Ramsey properties.
- Author
-
Barber, Ben, Hindman, Neil, Leader, Imre, and Strauss, Dona
- Subjects
- *
GROUP theory , *RAMSEY numbers , *COEFFICIENTS (Statistics) , *LINEAR equations , *MATHEMATICAL analysis , *RING theory - Abstract
A system of linear equations with integer coefficients is partition regular over a subset S of the reals if, whenever S ∖ { 0 } is finitely coloured, there is a solution to the system contained in one colour class. It has been known for some time that there is an infinite system of linear equations that is partition regular over R but not over Q , and it was recently shown (answering a long-standing open question) that one can also distinguish Q from Z in this way. Our aim is to show that the transition from Z to Q is not sharp: there is an infinite chain of subgroups of Q , each of which has a system that is partition regular over it but not over its predecessors. We actually prove something stronger: our main result is that if R and S are subrings of Q with R not contained in S , then there is a system that is partition regular over R but not over S . This implies, for example, that the chain above may be taken to be uncountable. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
12. 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.