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)

17
votes
3answers
2k views

Where in mathematics do these polynomials appear?

Does anyone recognize the following sequence of polynomials? $f_0(x) = x-1$ $f_1(x) = x^2-x$ $f_2(x) = x^4-2x^2+x$ $f_3(x) = x^8-3x^4+3x^2-x$ $f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$ $\vdots$ The ...
2
votes
1answer
66 views

Point-Hyperplane incidence in finite projective spaces

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...
1
vote
1answer
99 views

The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$ which is obtained by replacing each vertex $x$ by a complete graph $K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$. Let $G$ ...
5
votes
0answers
127 views

Is Euler-characteristic of a simplicial complex on $n$ vertices and $f$ facets at most $n^{O(\log f)}$?

(Definition: Facet = Maximal Face) This question is a continuation of the previous one that I had asked a couple of years ago: Is Euler characteristic of a simplicial complex upper bounded by a ...
2
votes
1answer
84 views

On a conjecture by Hibi regarding h-vectors

For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing). A non-integral polytope do not, in general, ...
4
votes
1answer
168 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...
4
votes
2answers
154 views

Joint probability distribution as functions

Suppose $X$ and $Y$ are correlated random variables in a finite set ${\mathcal A}$, and let $f, g$ be functions that map elements from ${\mathcal A}$ to ${\mathcal B}$ for some finite set ${\mathcal ...
2
votes
2answers
765 views

Number of 1 in binary representation of n

Let $1(n)$ be the number of digits $1$ in binary representation of number $n$. For example, $13=1101_2$ so $1(13)=3\\$ Is there explicit form of $\,\,\sum{1(i)x^i} $? I checked OEIS and didn't find ...
1
vote
0answers
103 views

Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
3
votes
0answers
106 views

What is the combinatorial data classifying non-normal affine toric varieties?

Recall that a toric variety is a variety $V$ containing an open dense algebraic torus. Here an algebraic torus means a finite product of copies of the multiplicative group of the ground field (which I ...
2
votes
0answers
123 views

Number of kxk matrices whose rows and columns are permutations

Let $\sigma_1,\ldots, \sigma_k$ be permutations of $\{1,2,\ldots,k\}$. I want to determine the number of $k$-tuples $(\sigma_1,\ldots, \sigma_k)$ of permutations such that, for each $1\leq j\leq k$, ...
0
votes
0answers
85 views

Database of non-isomorphic trees

As there are several free prime number databases, is there something similar for non-isomorphic trees?
8
votes
1answer
394 views

Is there an interesting species whose generating function gives the zigzag numbers?

Let's say a species is a functor $$F: \mathrm{FinSet}_0 \to \mathrm{FinSet}_0$$ from the groupoid of finite sets and bijections to itself. Let $F(n)$ be its value on your favorite $n$-element ...
0
votes
0answers
53 views

Partitions contained in staircase shape

Let $\lambda_n=\{n-1,n-2,\dots,1\}$ be a partition of staircase shape. Let $f(n,k)=\#\{|\mu|=k|\mu\leq\lambda_n\}$ and $g(n,(i,j))=\#\{\mu|(i,j)\notin \mu,~\mu\leq \lambda_n\}$, where $(i,j)$ denotes ...
6
votes
1answer
191 views

maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that (1) $|S_i| = k$ for all $i$, (2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$. What's the maximum ...
1
vote
0answers
51 views

Point sets with tangents through every point

Let $D=(P,L)$ be either a $(v,k,\lambda)$-design or a near-linear space (or, more generally, any incidence structure with "points" and sets of points which are called "blocks" or "lines") and let $S ...
5
votes
1answer
149 views

The number of partitions between two fixed partitions

Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} ...
-1
votes
1answer
236 views

Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$ Reccurence formula is $a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose ...
4
votes
0answers
198 views

Double sum involving binomial coefficients

I came across a sum of binomial coefficients while trying to solve a problem involving $SU(2)$ group integrals. I am not able to solve it, nor I found a similar identity in the literature. I would ...
9
votes
3answers
698 views

Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably also define a special class of Pythagorean triples. A perfect squared square PSS is a square (as a plane figure) partitioned into smaller ...
1
vote
0answers
56 views

Stronger condition than being a normal polytope?

A polytope $P$ with integer vertices is called normal if for every $p = \sum_j a_j p_j $ such that $a_j \geq 0$, $\sum_j a_j = k \in \mathbb{N}$, $p_j$ are vertices of $P$ and $p$ is an integer ...
4
votes
1answer
324 views

Balog-Szemeredi-Gowers with dilates of sets

All sets are assumed to be finite subsets of the integers. The additive energy of two sets $E(A,B)$ is defined as the number of solutions to $a+b=a'+b'$ with $a,a'\in A$ and $b,b'\in B$. The ...
4
votes
2answers
275 views

Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge. Note that the number of cycles in $k$-necklace is at least $2^k.$ Question : Suppose a ...
1
vote
1answer
116 views

Max order for which connected Cayley Graphs are known to be Hamiltonian

There is a well-known conjecture that all connected Cayley graphs are Hamiltonian. For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?
-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, ...
3
votes
1answer
98 views

Proof for the emergence of a ranking with paired comparisons [closed]

Take a set {A, B, C, D, E}, and assume each of the set elements has a random real value attached to it between 0 and 1. For example, this gives us: {A, B, C, D, E} = {0.1, 0.9, 0.4, 0.6, 0.5}. Assume ...
6
votes
1answer
142 views

Does high min degree and high odd girth imply near bipartiteness?

Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
9
votes
1answer
355 views

How many ways to partition a group of people?

My friend (who is a medical student!) posed me the following question: There are 70 people, and you want to split them up into 10 groups of 7 people each. Two such partitions are "compatible" if no ...
2
votes
1answer
52 views

The minimal number of halfspaces to represent a convex but non strongly convex cone

We say a cone at the origin in $R^n$ means that it is an intersection of finitely many halfspaces, i.e. $$C=\bigcap_{i\in I}H_i,\text{ where }|I|<\infty.$$ A cone is strongly convex if $C\cap ...
0
votes
0answers
63 views

Determinant of a pseudograph

Let G be a directed pseudograph and let A be the adjacency matrix of G. Say that G is non-singular if the determinant of A is non-zero mod 2. Is there a graph theoretic description of the collection ...
2
votes
0answers
34 views

Finding the number of leaf nodes at specific level of a random tree

Given a uniform recursive tree (URT) of size $N$ rooted at one node whereby the tree is generated as follows: Starting with a root node, at each iteration, a new node is connected to one of the ...
3
votes
2answers
119 views

Almost disjoint set (finite case)

I'm interested in the following: Given a set $S_{n,k}$ of binary sequences of length $n$ with $k$ many 1-entries, what is the maximal size of a subset $S'_{k'}\subset S_{n,k}$ such that for every ...
4
votes
4answers
311 views

Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed. I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...
3
votes
3answers
119 views

Isomorphism testing in STS(13)

What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points? Train structure and cycle structure, as described here, do the ...
5
votes
1answer
146 views

The number of connected components of a generalized hypecube

For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows. The vertices are the binary strings of length $n$. Two vertices are adjacent if they differ in exactly $m$ consecutive bits. ...
5
votes
2answers
147 views

Nonextendable partial Hadamard matrices

An $m\times n$ matrix with entries $\pm 1$ is said to be partial Hadamard if any two rows are orthogonal. See Reference for partial Hadamard matrices. Given $n\equiv 0\,(\mathrm{mod}\,4)$, what is the ...
5
votes
0answers
55 views

Labeled polytopes

In a "problem of a week" contest in my school, I gave the following problem to students: we assign to each vertex of a cube a number $1$ or $-1$. And we associate to each face the product of the ...
2
votes
1answer
79 views

Constructing an interval exchange given a prescribed trajectory

Given a prescribed trajectory, is it possible to construct an interval exchange having this trajectory? For example, given a 3-letter word (like aaabbbccabcaaa ), is it possible to construct a 3- ...
6
votes
0answers
122 views

A variant of an Eventown problem for modulo a prime number

Consider the following problem, called the 'Eventown problem': In a town, residents can form different clubs. The town council establishes the following rules: 1) Every club must have an even ...
2
votes
0answers
33 views

Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge). Is there some simple graph $H$ such that the $t$-fold ...
0
votes
0answers
174 views

Two Laurent polynomials actually being equal

I encountered two Laurent polynomials $$\sum_{j=0}^k\sum_{ \mbox{$\begin{array}{c} i_1,\dots,i_k\geq 0\\ i_0=-N-i_1-\dots-i_k\end{array}$}} \sum_{m=0}^{i_j} \begin{pmatrix} -N\\ ...
5
votes
2answers
120 views

Length of the longest chain in dominance order

If $\Pi_n$ is the set of partitions of $n$, then for $\lambda, \mu\in \Pi_n$ we say $\mu$ dominates $\lambda$ if $\sum\limits_{i=1}^k \lambda_i \leq \sum\limits_{i=1}^k \mu_i$ for all $k$. This gives ...
3
votes
3answers
312 views

powers in strings

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th ...
5
votes
1answer
99 views

References to proofs of a theorem by Van Kampen-Flores

Theorem (Van Kampen-Flores 1930s) From any 7 points in four-dimensional space one can choose two disjoint triples such that the triangles with vertices at the triples intersect each other. This ...
2
votes
1answer
169 views

More asymptotics for trees

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
5
votes
2answers
174 views

Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...
2
votes
1answer
99 views

Family of sets with unique subsets

I am given a set $M\subseteq\{1,\dots,n\},\,|M|=m$ and a famliy of $k$-sets ($k<m$) $\mathcal{U}=\{U_1,\dots,U_p\},\,U_{i}\subset M$. For this family, I would like to check one of the following ...
13
votes
1answer
376 views

Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins 1, 1, 2, 3, 5, 6, 10, 11, 16, ... and it is ...
0
votes
0answers
74 views

The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
5
votes
1answer
191 views

Normal polytopes - counterexample?

An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points. I am looking for an example ...