17
votes
5answers
545 views

Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
25
votes
2answers
880 views

A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture: Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
10
votes
2answers
327 views

Inequalities for averaging over partially ordered sets

Let's start from a classical inequality: If $0\le a_1\le\cdots\le a_k$ and $0\le b_1\le\cdots\le b_k$ then $(a_1+\cdots+a_k)(b_1+\cdots+b_k)\le k(a_1b_1+\cdots+a_k b_k)$. It can be written also in ...
6
votes
1answer
104 views

How “accidental” are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?

Background What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...
2
votes
1answer
142 views

Lattice automorphisms of finite order

Are there any known examples of lattice automorphisms of finite order in indefinite lattices being classified up to conjugacy?
1
vote
0answers
74 views

Group actions on polytopes in indefinite integer lattices

Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, ...
1
vote
1answer
81 views

Submodular measures on the hypercube

By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the ...
7
votes
0answers
224 views

What are the homological properties of Young's lattice?

Young's lattice $Y$ is a graded poset and a distributive lattice whose elements are all the partitions of $n$ for $n \in \mathbb{N}$ with the poset relation coming from inclusion of Young diagrams. ...
2
votes
1answer
281 views

Automorphism groups of indefinite non-unimodular integer lattices

Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite non-unimodular integral lattice are calculated? The exact lattice isn't so important and they ...
1
vote
1answer
113 views

General and translational Birkhoff lattices. Equational classes.

By  lattice  I'll mean  Birkhoff lattice. The two classical equational classes of lattices are modular lattices and distributive lattices. The old problem used to be: Is there an ...
5
votes
0answers
200 views

Lattice points inside a (n-dimensional) tetrahedron

Hi, overflowers. I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and ...
5
votes
2answers
469 views

Area of a lattice polygon in terms of its width

Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$). Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M)=\max\limits_{x,y\in ...
3
votes
0answers
125 views

references for properties/examples of breadth in (semi)lattices

This is in some sense following up on my earlier question and the answer given by NN. I am currently revising the paper which used the condition mentioned in my question. It was pointed out in NN's ...
5
votes
0answers
657 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
3
votes
2answers
265 views

Cancellation theorem for lattices

By a lattice, we mean a finitely generated, free $\mathbb{Z}$-module together with a symmetric bilinear form. Typical examples are the hyperbolic lattices $U$ and the root lattices $A_{n}, D_{n}, ...
2
votes
1answer
183 views

Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice

Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs ...
15
votes
4answers
472 views

The latice spanned by $m$ random 0-1 vectors of length $n$

Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
2
votes
1answer
193 views

Spanning set for Lattice generated by an orbit of the group.

For a vector spaces it always holds that any set of vectors spanning vector space $V$ has a subset of vectors which is a basis for $V$. While for lattices it is not true. For example consider one ...
1
vote
3answers
345 views

Triangulations of lattice polygons

Let L be a 2-dimensional lattice and P- a lattice polygon. Suppose, it is triangulated into lattice tiangles. What are restrictions on their areas? For instance, can a lattice triangle of even area ...
0
votes
0answers
97 views

Question regarding contiguous forms

I read about contiguous forms in Achill Sc├╝rmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
6
votes
2answers
509 views

Maximal number of edges and triangular cells for n points in a triangular lattice

Consider a subset of $n$ points in an equilateral triangular lattice. Draw all the edges between nearest-neighbor points. What is the maximum, over all such subsets, of the number of edges? This ...
5
votes
1answer
284 views

Orthogonal Complements of Root Lattices in E_8

I have a rather stupid lattice theory question. Suppose $L$ is a root lattice that can be primitively embedded in the $ E_8 $ lattice. Is the orthogonal complement of $ L$ in $E_8$ unique up to ...
12
votes
1answer
1k views

Sublattices of Young's Lattice

Young's Lattice is the lattice of inclusions of Young tableaux, or integer partitions. In R. Stanley's Enumerative Combinatorics Vol. 1, Proposition 1.4.4., there is a generalization of integer ...
2
votes
1answer
275 views

Count of lattices on finite set

Let $p(n)$ denote count of lattices on finite set $G$, $|G|=n$ (without isomorphism). It's know closed formula for $p(n)$? It's clear, that $1 \leq p(n)$ and also that $p(n-1) \leq p(n)$ for $n \geq ...
5
votes
0answers
343 views

Have you seen this sort of an anti-involution on a lattice?

While looking at a representation theory question, I came up with the following sort of object. I want to know if it comes up often in combinatorics or some other area of mathematics. Let $P$ be a ...
3
votes
0answers
344 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 ...
0
votes
1answer
217 views

Constructing a smooth lattice from a discrete one.

I have the standard lattice L defined over partitions of $1\ldots n$ under the split-merge relation. I also have an antimonotone function from L to R that's submodular, and so gives me a metric on L ...
9
votes
1answer
430 views

Condition for existence of certain lattice points on polytopes

Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer. I am interested in whether there exist integers $x_1,\cdots, x_n$ with $0<x_i<a_i$ satisfying: ...
0
votes
2answers
442 views

Is a lattice of convex sets distributive?

Is a lattice of convex sets in $R^2$ distributive?
9
votes
1answer
603 views

Which lattices have more than one minimal periodic coloring?

The lattice $\mathbb{Z}^n$ has an essentially unique (up to permutation) minimal periodic coloring for all $n$, namely the "checkerboard" 2-coloring. Here a coloring of a lattice $L$ is a coloring of ...
18
votes
4answers
1k views

What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?

So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice ...
9
votes
3answers
600 views

A “round” lattice with low kissing number?

Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. ...