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
1answer
154 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
165 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
99 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
93 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
149 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 ...
3
votes
0answers
100 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
245 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
452 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
166 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 ...
5
votes
2answers
202 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
467 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
178 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
51 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
216 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
309 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
52 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
325 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
95 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
132 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
405 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
257 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
151 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
184 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
242 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
204 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
329 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
577 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
161 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
214 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
167 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
80 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
184 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
143 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
285 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
167 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 \\ ...
2
votes
0answers
51 views

Generalized separating systems

We call a set system $\mathcal{A}$ of subsets of the $n$ element universe $U$ a separating system if for any pair of elements $x,y \in U$ there is at least one set $A \in \mathcal{A}$ such that either ...
7
votes
1answer
464 views

How to determine if there exists a non-zero vector in the kernel

If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel? Could this problem ...
0
votes
0answers
90 views

topological space of Wang Tile

When trying to reprove a theorem in Wang tile: An established proof in Wang Tile which I doubt , a few notions are provided which I would like to seek for more information: For a given set of blocks ...
3
votes
3answers
209 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
5
votes
1answer
154 views

Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small. The famous Nash-Williams conjecture claims ...
3
votes
3answers
735 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
4
votes
2answers
229 views

Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
8
votes
5answers
992 views

Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively. A graph is almost regular if $\Delta-\delta=1$. Now, here is a simple way to generate ...
4
votes
1answer
212 views

Circulant matrix with integer entries and determinant 1 or -1

CONJECTURE Let $A= (c_0,c_1,\ldots,c_n)$ be a circulant matrix, i.e if $(c_0,c_1,\ldots,c_n)$ is the first column of $A$ then the $i$th column of $A$ is obtained by applying the permutation ...
1
vote
0answers
224 views

Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions: $f(ax) = af(x)$ for ...
3
votes
1answer
99 views

Results where complexity bounds implies finite number of test cases

We have all been there, when a formula works for the first 30 parameters, but it is not sufficient for a proof. My question is where one can actually just check a finite number of cases, to conclude ...
2
votes
3answers
170 views

branching schubert calculus

Let $X=Gr(r,V), Y=Gr(r+1,W)$ where $V,W$ are complex vector spaces with $\dim V > r$ and $\dim W > \dim V$. Let $\phi:X\rightarrow Y$ be some embedding of varieties. This induces a morphism on ...