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)

1
vote
0answers
101 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
103 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
122 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
83 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
392 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
190 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
50 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
235 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
194 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
697 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
323 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 ...
3
votes
2answers
268 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
96 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
354 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
306 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
118 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
146 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
77 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
120 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
32 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
310 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
167 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
171 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
374 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 ...
6
votes
0answers
165 views

Counting categories with at most $n$ morphisms

There are a number of results which count the number of possible algebraic structures on a set of $n$ elements. Notable previous MO questions are for example here and here. The analogous question for ...
1
vote
0answers
150 views

An extrasensory perception strategy :-)

I asked this question at MSE some months ago but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
4
votes
2answers
117 views

combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual ...
3
votes
2answers
145 views

Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$. Is $\gamma(L(D))$ determined only by ...
8
votes
3answers
508 views

A combinatorial problem - counting the solutions

Consider a square. There are 16 ways to paint its sides with two colors. For convenience, we will represent one color with a blank side, and the other - with a line drawn from the squares' center to ...
4
votes
0answers
61 views

Reference for statement that almost every $n$-element partial order has trivial automorphism group

I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...
2
votes
0answers
44 views

Any one know the results of tensor decomposition by hypergraph partitioning?

Tucker Decomposition and CANDECOMP/PARAFAC (CP) Decomposition are two widely used tensor decomposition methods. However, when we model the hypergraph into tensor, what's the connection between the ...
3
votes
1answer
111 views

Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?