15 results on '"Leader, Imre"'
Search Results
2. An isoperimetric inequality for antipodal subsets of the discrete cube.
- Author
-
Ellis, David and Leader, Imre
- Subjects
- *
SET theory , *ISOPERIMETRIC inequalities , *CUBES , *MATHEMATICAL sequences , *EXTREMAL problems (Mathematics) - Abstract
We say a family of subsets of { 1 , 2 , … , n } is antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of { 1 , 2 , … , n } (of any size). Our inequality implies that for any k ∈ N , among all such families of size 2 k , a family consisting of the union of two antipodal ( k − 1 ) -dimensional subcubes has the smallest possible edge boundary. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. 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
4. 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
5. 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
6. 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
7. Sums and k-sums in abelian groups of order k
- Author
-
Gao, Weidong and Leader, Imre
- Subjects
- *
ABELIAN groups , *GROUP theory , *GROUP algebras , *AUTOMORPHISMS - Abstract
Abstract: Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence that does not have 0 as a k-sum is attained at the sequence , where is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
8. 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
9. 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
10. 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
11. Product-free sets in the free semigroup.
- Author
-
Leader, Imre, Letzter, Shoham, Narayanan, Bhargav, and Walters, Mark
- Subjects
- *
ALPHABET , *DENSITY , *RESPECT - Abstract
In this paper, we study product-free subsets of the free semigroup over a finite alphabet A. We prove that the maximum density of a product-free subset of the free semigroup over A , with respect to the natural measure that assigns a weight of | A | − n to each word of length n , is precisely 1 ∕ 2. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
12. The width of downsets.
- Author
-
Duffus, Dwight, Howard, David, and Leader, Imre
- Subjects
- *
LOGICAL prediction , *EVIDENCE - Abstract
How large an antichain can we find inside a given downset in the Boolean lattice B (n) ? Sperner's theorem asserts that the largest antichain in the whole of B (n) has size n ⌊ n ∕ 2 ⌋ ; what happens for general downsets? Our main results are a Dilworth-type decomposition theorem for downsets, and a new proof of a result of Engel and Leck that determines the largest possible antichain size over all downsets of a given size. We also prove some related results, such as determining the maximum size of an antichain inside the downset that we conjecture minimizes this quantity among downsets of a given size. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
13. 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
14. 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
15. Cops and robbers in a random graph
- Author
-
Bollobás, Béla, Kun, Gábor, and Leader, Imre
- Subjects
- *
RANDOM graphs , *GRAPH theory , *COMPUTATIONAL complexity , *COMPUTER science , *COMPUTER networks - Abstract
Abstract: The cop-number of a graph is the minimum number of cops needed to catch a robber on the graph, where the cops and the robber alternate moving from a vertex to a neighbouring vertex. It is conjectured by Meyniel that for a graph on n vertices cops suffice. The aim of this paper is to investigate the cop-number of a random graph. We prove that for sparse random graphs the cop-number has order of magnitude . The best known strategy for general graphs is the area-defending strategy, where each cop ‘controls’ one region by himself. We show that, for general graphs, this strategy cannot be too effective: there are graphs that need at least cops for this strategy. [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.