Duffus wrote in his 1978 Ph.D. thesis, “It is not obvious that is connected and imply that is connected”, where and are finite nonempty posets. We show that, indeed, under these hypotheses is connected and .
The Bruhat order is defined in terms of an interchange operation on the set of permutation matrices of order which corresponds to the transposition of a pair of elements in a permutation. We introduce an extension of this partial order, which we call the stochastic Bruhat order, for the larger class of doubly stochastic matrices (convex hull of permutation matrices). An alternative description of this partial order is given. We define a class of special faces of induced by permutation matrices,...
We investigate some natural questions about the class of posets which can be embedded into ⟨ω,≤*⟩. Our main tool is a simple ccc forcing notion which generically embeds a given poset E into ⟨ω,≤*⟩ and does this in a “minimal” way (see Theorems 9.1, 10.1, 6.1 and 9.2).
A lattice is said to satisfy (the lattice theoretic version of) Frankl’s conjecture if there is a join-irreducible element such that at most half of the elements of satisfy . Frankl’s conjecture, also called as union-closed sets conjecture, is well-known in combinatorics, and it is equivalent to the statement that every finite lattice satisfies Frankl’s conjecture. Let denote the number of nonzero join-irreducible elements of . It is well-known that consists of at most elements....
A rook placement is a subset of a root system consisting of positive roots with pairwise non-positive inner products. To each rook placement in a root system one can assign the coadjoint orbit of the Borel subgroup of a reductive algebraic group with this root system. Degenerations of such orbits induce a natural partial order on the set of rook placements. We study combinatorial structure of the set of rook placements in with respect to a slightly different order and prove that this poset is...
We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.
Which subgroups of the symmetric group Sn arise as invariance groups of n-variable functions defined on a k-element domain? It appears that the higher the difference n-k, the more difficult it is to answer this question. For k ≤ n, the answer is easy: all subgroups of Sn are invariance groups. We give a complete answer in the cases k = n-1 and k = n-2, and we also give a partial answer in the general case: we describe invariance groups when n is much larger than n-k. The proof utilizes Galois connections...
The arc graph of a digraph is the digraph with the set of arcs of as vertex-set, where the arcs of join consecutive arcs of . In 1981, S. Poljak and V. Rödl characterized the chromatic number of in terms of the chromatic number of when is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the...