1
vote
0answers
88 views

Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
-2
votes
1answer
77 views

Monotonic sequence (edited) [closed]

For any two n-dim vector $v$ and $v'$ define $v\leq v'$ iff for each $1\leq i\leq n$, $v_i\leq v_i'$. Suppose further that the entry of vectors can only take values from $m$ distinct values $\{a_1, ...
4
votes
0answers
61 views

Reference for statement that almost every $n$-element partial order has trivial automorphism group

I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...
3
votes
1answer
99 views

For what classes of comparability graphs are their complements also comparability graphs?

An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...
10
votes
1answer
209 views

Order dimension and weak poset partitions

The order dimension of a poset $(P,\leq)$ is the least number of linear extensions of $(P,\leq)$ such that the intersection of these extensions is $(P,\leq)$. The wikipedia entry provides some ...
0
votes
1answer
95 views

Counting linear extensions of unlabeled series parallel structures

I am interested in the problem of counting the number of linear extensions of series-parallel structures. The wikipedia article at http://en.wikipedia.org/wiki/Series-parallel_partial_order pointed me ...
1
vote
1answer
111 views

Covering of a partial order by upwards convex sets

First off: I'm not an expert in order theory, so some of my terms might be off; correct them if you wish. Let me call a subset $A$ of a lattice $(S,\le)$ upwards convex (not sure if that's actually ...
1
vote
0answers
104 views

Generalization of order dimension and interval orders

A partial order $(X, <_X)$ has order dimension $n$ if it can be realized as the product order of $n$ total orders, which means that there is an order-embedding between $(X, \lt_X)$ and $(Y^n, ...
2
votes
3answers
289 views

A characterisation of Boolean algebras

Let $M$ be a meet-semilattice with a least element $0$. Suppose there is an order-reversing involution $a \mapsto -a$ on $M$ such that for all $a, b \in M$, $a \wedge b = 0$ if and only if $b \le ...
9
votes
0answers
194 views

Reference for sparseness of incomparability graphs implying sparseness of covering graphs

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...
0
votes
2answers
244 views

Automorphisms of locally finite countable posets-2

Given is a locally finite countable connected poset which satisfies further the following properties: Let $C$ be any maximal chain ( i.e. inextendible chain) and $A$ be any antichain. Then $A$ is ...
1
vote
1answer
356 views

Causal sets quantization

Hi, Here are a couple of questions: Is there a way to classify all homomorphisms between two finite posets? Same question as (1) but for infinite, locally finite countable connected posets. ...
4
votes
1answer
231 views

Automorphisms of locally finite countable posets

I rephrase my last question. Given a locally finite countable connected (as a graph) poset which satisfies the following further condition: the intersection of any antichain with the set of elements ...
2
votes
1answer
198 views

Automorphisms of locally finite countable posets

Hi, Is the automorphism group of a countable locally finite connected poset finite or countable? If not, is there a way to equipp it (the uncountable group) with a topology and a measure? Need this ...
2
votes
2answers
229 views

Algorithm to compute certain poset from a given poset.

Hi. Associated with a finite poset $P$, one can consider the poset $S(P)$, whose elements are the intervals of $P$, ordered by inclusion. (See Discrete version of Nullstellensatz? for some motivation ...
4
votes
1answer
329 views

Intervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets?

BACKGROUND Assume a poset $\langle P, \le \rangle$. For two points $a,b \in P$ with $a \le b$, then $I = [a,b] = \{ x : a \le x \le b \}$ is the interval between $a$ and $b$. When $P$ is a chain ...
10
votes
1answer
741 views

Discrete version of Nullstellensatz?

Hi. I was reading the paper "On the foundations of combinatorial theory (VI): The idea of a generating function" by Doubilet, Rota and Stanley, and there is a relation treated which is very ...
7
votes
1answer
2k views

Number of graphs with a given number of nodes, edges and triangles

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and ...
5
votes
1answer
480 views

Bridge game with only one suit: strategy

This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...
2
votes
0answers
75 views

A specific notion between the notions of transversal and system of distinct representatives.

Let $X$ be a set, let $\mathcal{C}$ be a collection of subsets of $X$, and let $x_1, \dots , x_k \in X$. Say that the sequence $\{x_i\}_{i=1\dots k}$ is a sequential transversal (of length $k$) ...
8
votes
1answer
374 views

Does this “flipping lexicographic” ordering have a standard name?

I’ve run into the following straightforward variant of lexicographic ordering, and am wondering if it has a standard name. I’ve been calling it the flipping lexicographic ordering, for evident ...
8
votes
1answer
315 views

Decomposing posets into countably many chains

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some ...
5
votes
1answer
495 views

Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?

It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...
3
votes
2answers
608 views

Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

Consider two partially ordered sets $A = \{a< b,a< c\}$, $B=\{x< z,y< z\}$. Their linear extensions (here we allow equality in linear extensions) for $A, B$ are $$A_L=\{A_1=\{a< b< ...
3
votes
0answers
337 views

a poset with small “cycles”

(a followup to this recent question) I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that...): Suppose that $z$ is covered by ...
14
votes
3answers
2k views

Proving that a poset is a lattice

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...
2
votes
0answers
170 views

How linearly independent are the obvious combinatorial invariants of a Bruhat interval?

Let $[u, v]$ be a Bruhat interval in some Coxeter group. Let $I$ be the set of all Bruhat intervals. I am interested in functions $I \to \mathbb{Z}$ which are invariant under poset isomorphisms. ...
7
votes
1answer
236 views

Monotonic maximal chains in a Coxeter group

Let $(W, S)$ be a Coxeter system, and let $T = \bigcup_{w \in W, s \in S} wsw^{-1}$. Associated to every element $t \in T$ is a unique positive root $\alpha_t \in \Phi^{+}$ considered as a vector in ...
14
votes
3answers
798 views

Subposets of small Dushnik-Miller dimension

The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, ...
27
votes
2answers
609 views

What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds order-preservingly into $\mathbb{B}$. For example, every partial order ...
11
votes
5answers
3k views

infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
4
votes
2answers
232 views

Is there a poset with 0 with countable automorphism group?

Is there a poset P with a unique least element, such that every element is covered by finitely many other elements of P (and P is locally finite -- actually, per David Speyer's example, let's say that ...
8
votes
7answers
1k views

Generalizations of Boolean posets/lattices

A Boolean lattice has a number of rather nice properties which give it a central role in many parts of combinatorics. For instance, it's a lattice, it can be augmented with a ring structure, it can ...
2
votes
1answer
403 views

Chains intersecting antichains in finite posets

I feel a little embarrassed to be asking this question here, since I think it should be much easier than I'm making it, but here goes: Given a finite poset P, does there necessarily exist some chain ...
3
votes
3answers
515 views

Is there a “universal LYM inequality?”

This question is based on a blog post of Qiaochu Yuan. Let P be a locally finite* graded poset with a minimal element, and w be a weight function on the elements of P. Suppose that the total weight ...