Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

0
votes
0answers
73 views

Rank function and closure operator for a set system

I would like to trace the concepts "rank function" and "closure operator" back to some structures as primitive as possible. For a set system $(E,F)$ which is an independence system or a greedoid, I ...
3
votes
0answers
100 views

Convex hull of a discrete set of points

If i was to give an $n×n$ grid with each grid point having probability $p$ of being selected, would it be difficult to calculate distributions of various measures regarding the convex hull of all ...
1
vote
1answer
90 views

maximal chain in (strong) Bruhat order satisfying constraint

Consider the (strong) Bruhat order, $\leq_B$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma∈S_n$ such that $\pi\geq_B \sigma$. Suppose further that they satisfy the ...
0
votes
0answers
70 views

latest classification of difference sets

I am looking for a reference including the last classification of difference sets and almost difference sets. Would you mind letting me know some of them? The recent ones are preferred.
18
votes
3answers
607 views

Number of primitive $n$th roots with positive versus negative real parts

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ ...
3
votes
1answer
436 views

“Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988: A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...
5
votes
1answer
259 views

Does this matroid have a name?

Sorry if this question is a dumb one. I used a special family of matroids in my research. One of them, of rank 3, can be represented by the following matrix over $\mathbb F_5$ or over $\mathbb R$: ...
1
vote
0answers
69 views

Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph? In particular is there a necessary condition for not having empty k-junction ...
3
votes
1answer
189 views

Geometric RSK correspondece and classical RSK correspondence

In the paper, geometric RSK correspondence is given by $$ \left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \mapsto \left( \begin{matrix} \frac{bc}{b+c} & ab \\ ac & ...
1
vote
1answer
148 views

Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case. I found on arxiv the following interesting articles: 1)Alexander Postnikov: Total ...
3
votes
2answers
140 views

Asymptotics of the number of elements in the intersection of two growing sets

Let $[n]:=\{1,\dots,n\}$ and $0\leq p_n\leq n$. Fix any subset $A_n$ of $[n]$ with $p_n$ elements. The number of subsets $B$ of $[n]$ with $p_n$ elements that are disjoint from $A$ is ...
1
vote
0answers
118 views

Reduce a Combinatorial problem

It is given n sets with k vectors. (k is element-wise positive or zero) Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal. What i also know but is ...
0
votes
1answer
148 views

Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...
8
votes
0answers
161 views

Consequences of Zeeman's conjecture

Recall the Zeeman's conjecture: if $K$ is a contractible polyhedron of dimension 2, then $K\times I$ has a collapsible subdivision. Zeeman showed that this implies the Poincaré conjecture in ...
6
votes
2answers
198 views

Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index. Based on limited experiments (up to 8 vertices and few larger graphs), I suspect: Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...
1
vote
1answer
91 views

Ratio of expected diameter and height of a conditioned Galton-Watson tree

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...
2
votes
1answer
91 views

Estimate for the travelling salesman problem for balls inside a grid

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around... The question concerns the TSP problem (with ...
3
votes
2answers
145 views

Finite lattices whose number of join-irreducibles does not exceed its height

In a finite distributive lattice $L$ one has $height(L) = |J(L)|$ i.e. the size of the largest chain equals the number of join-irreducible elements. Briefly, this follows by arranging the subposet ...
2
votes
0answers
96 views

Number of k-generated semigroups

Given some $k>1$, I am interested in the number of $k$-generated semigroups of order $n$ (either up to isomorphism or all associative binary operations on an n-element set). At first I thought ...
5
votes
2answers
240 views

A bound on a set

Let $x_1,\cdots , x_n$ be a sequence of real number such that $x_i\geq 1$ for all $1\leq i\leq n$, $S=\{\alpha_1x_1+\cdots +\alpha_nx_n | \alpha_i\in\{0,+1,-1\}\}$ and $I=[a,b)$ be a Interval with ...
21
votes
2answers
444 views

Convex hull of total orders

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...
1
vote
1answer
162 views

Existence of certain probability distributions on the set of all partitions of a finite set

Conjecture: Let $N$ be a non-empty and finite set. There exists a probability distribution $p$ on the set of all partitions of $N$, $Z(N)$, such that $$\sum_{P\in Z(N):S\in P}p(P)= {1 \over n\cdot ...
5
votes
0answers
125 views

Which Graeco-Latin hypercubes are impossible?

Define a Graeco-Latin hypercube of dimension $n$ and order $k$ as an $n$-dimensional grid, with $k$ cells in each direction (for a total of $k^n$ cells), where: Each cell contains an ordered tuple ...
4
votes
2answers
188 views

Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial: If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
7
votes
0answers
464 views

How many ways can a snake lie?

This is essentially a question about counting nonintersecting short paths in a cubic lattice, but with a twist. (One constraint that I did not make clear below is that when to turn is already ...
5
votes
1answer
174 views

Estimate the rank of a vector

Consider {0,1}-vectors $v$ with $n$ elements. For each $i\in[n]$ we are given $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. We can therefore associate a probability to each of the ...
1
vote
0answers
49 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there graph problems that can be solved in ...
2
votes
1answer
215 views

Examples of functors $\mathbf{Set} \to \mathbf{Set}$ which are not analytic

Let $\mathbb{B}$ denote the groupoid of finite sets and bijections. A functor $F : \mathbf{Set} \to \mathbf{Set}$ is analytic if it is the left Kan extension of some functor $G : \mathbb{B} \to ...
10
votes
1answer
215 views

On the Steiner System S(4,5,11)

Is there a nice way to partition the edges of the complete 5-uniform hypergraph on 11 vertices into 7 copies of the Steiner system S(4,5,11)? If this is obvious or elementary, I apologize in advance. ...
3
votes
1answer
306 views

“the” random permutation

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability. The random permutation is ...
1
vote
0answers
51 views

Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$. Call a graph $G = (U, ...
8
votes
1answer
319 views

Postnikov's approach to perfect matchings of graphs

Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
6
votes
0answers
91 views

Littlewood-Richardson coefficients for Jack symmetric functions

Let $\Lambda$ be the algebra of symmetric functions over $\mathbb{Q}(\alpha)$. We define a scalar product $\langle \cdot,\cdot\rangle_\alpha$ on $\Lambda$ by setting $\langle ...
6
votes
0answers
127 views

The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...
5
votes
1answer
402 views

A generalized Burnside's lemma

Let $G$ be a finite group acting on a set $X$, and let $S\subseteq G$ be a union of conjugacy classes. Then I believe I can prove: $$ \sum_{[x]\in X/G} \frac{|G_x \cap S|}{|G_x|} = \sum_{g\in S} ...
11
votes
2answers
253 views

Set system with different differences

What is the maximal number of sets in a set system $\mathcal{A}$ of subsets of an $n$ element set such that for every $i \neq j $ and $A_i,A_j \in \mathcal{A}$ the difference $A_i \setminus A_j$ is ...
3
votes
0answers
148 views

To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

This is a cross-post from MSE. In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a ...
3
votes
1answer
178 views

d-regular partitions and permutations

A $d$-regular partition is a partition of an $n$ element set with the additional restriction that $x,y$ with $|x-y|<d$ cannot be in the same block. So, if $d=2$, say, then the partition ...
5
votes
1answer
233 views

Parking Functions and the Binomial Theorem

Cross-post from http://math.stackexchange.com/questions/808490/parking-functions-and-the-binomial-theorem A parking function is a function $f: \{1, \ldots n\} \rightarrow \{1, \ldots n\}$ which has ...
2
votes
0answers
202 views

Hook Content Formula: Has anyone seen this proof?

Below is the outline of a proof idea I have for the Hook Content Formula. I'm wondering whether anyone is aware of whether this technique has been used before, and if so, if they could give me a ...
8
votes
2answers
324 views

Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...
11
votes
1answer
567 views

Colourings of $\mathbb Q\times \mathbb Q$ in three colours

Using two-adic valuation Monsky coloured $\mathbb Q\times \mathbb Q$ in red, blue, and green, so that on each line points of at most two colours are present. Question. I would like to know if there ...
1
vote
1answer
159 views

How is this combinatorial structure called?

Here is a "colourful" description of what I would like to count. Suppose you have one of those tables you see in a casino. I think they are for roulette, with $m$ squares, each of them with a number ...
5
votes
1answer
212 views

“strongly mixing” action on dimers?

In Local Statistics of Lattice Dimers we study a nice familiar object, domino tilings in the plane extending out to infinity. His paper is going to discuss the frequency of various "motifs" in ...
8
votes
1answer
161 views

Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$: $$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$ This bound is very elegant but ...
0
votes
0answers
79 views

Resources about integral maximization problem

I am looking at the following problem. Given an interval I, and a function f over that interval, find sub-intervals for which: The sum of the length of the sub-intervals is < k; The sub-intervals ...
3
votes
1answer
181 views

Why complete symmetric polynomials and elementary symmetric polynomials are dual to each other?

Here the definition of complete symmetric polynomial $h_{k}$ and elementary symmetric polynomial $e_{k}$ are: $$ e_{k}=\sum_{1\le i_1<\cdots <i_k\le n}x_{i_1}\cdots x_{i_k}, h_{k}=\sum_{1\le ...
1
vote
1answer
115 views

Name search for special Linear Integer Program

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
4
votes
3answers
282 views

Counting chains of inclusions

Let $g(n,k)$ be the number of chains $$ A_k \subset A_{k-1} \subset\dots\subset A_1 \subset A_0 $$ of $k$ proper subset inclusions, where $A_k\neq\emptyset$ and $A_0$ is a standard $n$-element set. ...
2
votes
1answer
166 views

Combinatorial sum (Author and generalization?)

In a book I have met one interesting equation (without reference): $$\frac{m!}{n!}\sum_{i=0}^n(-1)^i{n\choose{i}}{x+m+n-i\choose{m}}=\begin{cases} x+n+1,\, if \,m=n+1 \\ 1,\, if \,m=n \\ ...