| 1 |
Front Matter |
|
|
Abstract
|
| 1 |
|
|
|
Abstract
|
| 1 |
Countable Almost Rigid Heyting Algebras |
Michael E. Adams,Aleš Pultr |
|
Abstract
For non-trivial Heyting algebras .., .. one always has at least one homomorphism .. →..; if .. = .. there is at least one non-identical one. A Heyting algebra . is . if ∣ End(.)∣ = 2 and a system of almost rigid algebras ℌ is said to be . if ∣ Hom(.., ..)∣ = 1 for any two distinct .., .. ∈ ℌ. We show that there exists a discrete system of 2. countable almost rigid Heyting algebras.
|
| 1 |
Piecewise-Bohr Sets of Integers and Combinatorial Number Theory |
Vitaly Bergelson,Hillel Furstenberg,Benjamin Weiss |
|
Abstract
We use ergodic-theoretical tools to study various notions of “large” sets of integers which naturally arise in theory of almost periodic functions, combinatorial number theory, and dynamics. Call a subset of N a Bohr set if it corresponds to an open subset in the Bohr compactification, and a piecewise Bohr set (PWB) if it contains arbitrarily large intervals of a fixed Bohr set. For example, we link the notion of PWB-sets to sets of the form A+B, where A and B are sets of integers having positive upper Banach density and obtain the following sharpening of a recent result of Renling Jin..Theorem. If A and B are sets of integers having positive upper Banach density, the sum set A+B is PWB-set.
|
| 1 |
A Generalization of Conway Number Games to Multiple Players |
Christopher Cunningham,Igor Kriz |
|
Abstract
We define an analogue of the the concept of J. H. Conway’s number games for games of multiple players. We define the value of such number game as an element of a vector space over the Conway field. We interpret the value in terms of the strategy of the game, and prove that all possible values in the vector space can occur.
|
| 1 |
Two Isoperimetric Problems for Euclidean Simplices |
Miroslav Fiedler |
|
Abstract
Best possible estimates for the lengths of a Hamiltonian path and of a Hamiltonian polygon on a Euclidean simplex of given volume are given. The extreme cases are described.
|
| 1 |
On Finitely Generated Varieties of Distributive Double ,-algebras and their Subquasivarieties |
Václav Koubek,Jiří Sichler |
|
Abstract
A quasivariety ℚ is .-universal if, for any quasivariety . of algebraic systems of a finite similarity type, the lattice .(.) of all subquasivarieties of . is isomorphic to a quotient lattice of a sublattice of the lattice .(ℚ) of all subquasivarieties of ℚ. We investigate .-universality of finitely generated varieties of distributive double .-algebras. In an earlier paper, we proved that any finitely generated variety of distributive double .-algebras categorically universal modulo a group is also .-universa1. Here we consider the remaining finitely generated varieties of distributive double .-algebras and state a problem whose solution would complete the description of all .-universal finitely generated varieties of distributive double .-algebras.
|
| 1 |
The ,-triangle of the Generalised Cluster Complex |
Christian Krattenthaler |
|
Abstract
The .-triangle is a refined face count for the generalised cluster complex of Fomin and Reading. We compute the .-triangle explicitly for all irreducible finite root systems. Furthermore, we use these results to partially prove the “. Conjecture” of Armstrong which predicts a surprising relation between the .-triangle and the Möbius function of his .-divisible partition poset associated to a finite root system.
|
| 1 |
|
|
|
Abstract
|
| 1 |
Monochromatic Equilateral Right Triangles on the Integer Grid |
Ron Graham,József Solymosi |
|
Abstract
For any coloring of the . × . grid using fewer than log log . colors, one can always find a monochromatic equilateral right triangle, a triangle with vertex coordinates (.), (.), and (.).
|
| 1 |
One-sided Coverings of Colored Complete Bipartite Graphs |
András Gyárfás,Miklós Ruszinkó,Gábor N. Sárközy,Endre Szemerédi |
|
Abstract
Assume that the edges of a complete bipartite graph . are colored with . colors. In this paper we study coverings of . by vertex disjoint monochromatic cycles, connected matchings, and connected subgraphs. These problems occur in several applications.
|
| 1 |
Nonconstant Monochromatic Solutions to Systems of Linear Equations |
Neil Hindman,Imre Leader |
|
Abstract
The systems of linear equations (homogeneous or inhomogeneous) that are partition regular, over ℕ or ℤ or ℚ, were characterized by Rado. Our aim here is to characterize those systems for which we can guarantee a nonconstant, or injective, solution. It turns out that we thereby recover an equivalence between ℕ and ℤ that is normally lost when one passes from homogeneous to inhomogeneous systems.
|
| 1 |
On the Induced Ramsey Number ,(, ,, ,) |
Alexandr Kostochka,Naeem Sheikh |
|
Abstract
The induced Ramsey number . is the least positive integer . such that there exists an N-vertex graph . with the property that for each 2-coloring of its edges with red and blue, either some induced in . subgraph isomorphic to . has all its edges colored red, or some induced in . subgraph isomorphic to . has all its edges colored blue. In this paper, we study .(.., .) for various ., where .. is the path with 3 vertices. In particular, we answer a question by Gorgol and Luczak by constructing a family {... such that ., where ..(.) is defined almost as ., with the only difference that . should be induced only . of . (not in . itself) and . should be induced only in the blue subgraph of ..
|
| 1 |
On Explicit Ramsey Graphs and Estimates of the Number of Sums and Products |
Pavel Pudlák |
|
Abstract
We give an explicit construction of a three-coloring of .. in which no .. is monochromatic for . = .., where ε > 0 is a constant.
|
| 1 |
|
|
|
Abstract
|
| 1 |
Hereditary Properties of Ordered Graphs |
József Balogh,Béla Bollobás,Robert Morris |
|
Abstract
An ordered graph is a graph together with a linear order on its vertices. A hereditary property of ordered graphs is a collection of ordered graphs closed under taking order-preserving isomorphisms of the vertex set, and order-preserving induced subgraphs. If . is a hereditary property of ordered graphs, then .. denotes the collection ., and the function . is called the speed of ...The possible speeds of a hereditary property of labelled graphs have been extensively studied (see [BBW00] and [Bol98] for example), and more recently hereditary properties of other combinatorial structures, such as oriented graphs ([AS00], [BBM06+c]), posets ([BBM06+a], [BGP99]), words ([BB05], [QZ04]) and permutations ([KK03], [MT04]), have also attracted attention. Properties of ordered graphs generalize properties of both labelled graphs and permutations..In this paper we determine the possible speeds of a hereditary property of ordered graphs, up to the speed 2.. In particular, we prove that there exists a jump from polynomial speed to speed .., the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from .. to .. (where .(.) is a polynomial and .. are the generalized Fibonacci numbers) converging to 2.. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations.
|
| 1 |
A Proof and Generalizations of the Erdős-Ko-Rado Theorem Using the Method of Linearly Independent Polynomials |
Zoltán Füredi,Kyung-Won Hwang,Paul M. Weichsel |
|
Abstract
Our aim is to exhibit a short algebraic proof for the Erdös-Ko-Rado theorem. First, we summarize the method of linearly independent polynomials showing that if ..,..., .. ⊂ [.] are sets such that .. does not satisfy any of the set of . intersection conditions .. but .. satisfies at least one condition in Rj for all . > . then .. The EKR theorem is follows by carefully choosing the intersection properties and adding extra polynomials. We also prove generalizations for non-uniform families with various intersection conditions.
|
| 1 |
Unions of Perfect Matchings in Cubic Graphs |
Tomáš Kaiser,Daniel Král’,Serguei Norine |
|
Abstract
We show that any cubic bridgeless graph with . edges contains two perfect matchings that cover at least 3./5 edges, and three perfect matchings that cover at least 27./35 edges.
|
| 1 |
Random Graphs from Planar and Other Addable Classes |
Colin McDiarmid,Angelika Steger,Dominic J. A. Welsh |
|
Abstract
We study various properties of a random graph .., drawn uniformly at random from the class . of all simple graphs on . labelled vertices that satisfy some given property, such as being planar or having tree-width at most κ. In particular, we show that if the class . is’ small’ and ‘addable’, then the probability that .. is connected is bounded away from 0 and from 1. As well as connectivity we study the appearances of subgraphs, and thus also vertex degrees and the numbers of automorphisms. We see further that if . is’ smooth’ then we can make much more precise statements for example concerning connectivity.
|
| 1 |
Extremal Hypergraph Problems and the Regularity Method |
Brendan Nagle,Vojtěch Rödl,Mathias Schacht |
|
Abstract
Szemerédi’s regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the . and has proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science..Recently, the graph regularity method was extended to hypergraphs by Gowers and by Skokan and the authors. The . has been successfully employed in a handful of combinatorial applications, including alternative proofs to well-known density theorems of Szemerédi and of Purstenberg and Katznel-son. In this paper, we apply the hypergraph regularity method to a few extremal hypergraph problems of Ramsey and Turán flavor.
|
|Archiver|手机版|小黑屋|
派博传思国际
( 京公网安备110108008328)
GMT+8, 2025-11-16 14:11
发表于 2025-3-21 18:02:27
