Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
10,515
questions
0
votes
0
answers
81
views
Find minimal set of progressions which intersections, unions or negations covers given set
Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline ...
3
votes
0
answers
124
views
Number cubes with consecutive line sums
This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics.
The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...
2
votes
1
answer
207
views
Hitting sets (aka covers aka transversals) of Steiner triple systems
Does there exist a constant $c$ so that the lines of every Steiner
triple system on $v$ points can be covered by $cv$ points?
That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...
14
votes
2
answers
1k
views
The Simultaneous Conjugacy Problem in the symmetric group $S_N$
We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\...
5
votes
2
answers
164
views
Computational complexity of deciding isomorphism of rational polyhedral cones
Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...
3
votes
1
answer
503
views
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
3
votes
2
answers
285
views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
2
votes
1
answer
297
views
A variant of Kruskal's theorem
For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of $y$...
6
votes
1
answer
888
views
Complexity of counting words of given length in regular or context-free language
Let $L$ be a regular or context-free language over
alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$
all words ...
35
votes
6
answers
2k
views
Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
59
votes
1
answer
2k
views
Which region in the plane with a given area has the most domino tilings?
I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...
2
votes
1
answer
206
views
Assigning unique binary strings to the squares of a chessboard s.t. inter-string Hamming distances are the same as inter-square Manhattan distances
Consider a chessboard with $(n_1 \times n_2)$ squares, where we would like to assign a unique binary string, of some length $L$, to each square s.t. the Hamming distance between the strings ...
3
votes
2
answers
1k
views
Definition of the Moebius Ladder Graph
I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.
according to Wikipedia (http://en.wikipedia.org/...
9
votes
1
answer
558
views
Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$
$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$
Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to $x$, $\...
2
votes
2
answers
258
views
Which graphs generate a matroidal independence complex?
The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...
20
votes
1
answer
4k
views
What have simplicial complexes ever done for graph theory?
(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...
2
votes
0
answers
140
views
Arctic Circle Theorems and the Wave Equation
I've seen the following remark in a number of papers but don't know what to make of it. In this paper by Cohn, Elkies and Propp, it is mentioned that the normalized average Height function $\mathcal{H}...
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 ...
4
votes
1
answer
319
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 ...
2
votes
1
answer
256
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$ ...
6
votes
0
answers
281
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 ...
4
votes
1
answer
261
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
303
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 $G$...
4
votes
2
answers
375
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 B}...
5
votes
2
answers
3k
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
386
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 ...
6
votes
2
answers
683
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
211
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$, ...
1
vote
0
answers
197
views
Database of non-isomorphic trees
As there are several free prime number databases, is there something similar for non-isomorphic trees?
12
votes
1
answer
734
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 set; ...
0
votes
0
answers
242
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 ...
10
votes
1
answer
3k
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 ...
2
votes
0
answers
67
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
286
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} q^{|\lambda|}$$...
-1
votes
1
answer
294
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 \...
6
votes
1
answer
2k
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 ...
10
votes
3
answers
2k
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
101
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 ...
5
votes
1
answer
775
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 well-...
4
votes
2
answers
454
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
153
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
103
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
114
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 ...
7
votes
1
answer
253
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
1k
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
78
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 -C=\...
2
votes
0
answers
184
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
257
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
1k
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 ...
6
votes
3
answers
448
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 ...