**17**

votes

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**4**answers

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

**3**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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 ...