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
1answer
123 views

Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties. Actually my question is ...
2
votes
1answer
92 views

Integrally closed polytopes from 01-matrices

Let $A$ be a matrix with entries either 0 or 1, where each column contains at least one 1, to remove trivial degenerations. Let $P$ be the convex hull of all integer vectors $x$ that satisfy $Ax \leq ...
7
votes
0answers
227 views

diameter as a Morse function

Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...
5
votes
1answer
288 views

A result from Peter McMullen's thesis

The classical definition of regular polytopes is recursive. It says that a polytope is regular if its facets and vertex figures (both smaller-dimensional polytopes) are regular. The modern definition ...
17
votes
0answers
151 views

A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph? I'd like to avoid exhaustive ...
0
votes
0answers
90 views

Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers $$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$ For example $f_{n,0} = ...
1
vote
1answer
106 views

Formula for the Ordinal Number of k-Sets of Positive Integers

Background of my question is, that I would like to store flags indicating the relation between a pairs of non-adjacent edges of a graph (that relation could for example be, whether the edges cross, ...
0
votes
0answers
116 views

Non existence (or existence) of a set that is equidistributed modulo $q$ for every $q$

I have been thinking about some set that is equidistributed modulo $q$, uniformly in $q$ in some sense. I was starting to think this particular condition, which I describe below, is too strong and ...
0
votes
1answer
77 views

Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...
4
votes
3answers
246 views

Number of binary vectors of a given Hamming weight in a subspace of the Hypercube

Let $n$ be a natural number. Let $U \subseteq \mathbb{F}_2^n$ be a linear subspace of dimension $k$. What is the maximum number of vectors in $U$ of Hamming weight $\ell$? The case I am specifically ...
1
vote
0answers
68 views

Inverse of matrix of generalised harmonic numbers

For $s=0,1,\dots$ and $n=1,2,\dots$, denote $r_{n,s}=\sum_{k=1}^n k^s$. It is well-known that $r_{n,s}$ are polynomials in $n$ with leading term $\frac{1}{s+1}n^{s+1}$. Let $R_{n,s}$ be the ...
4
votes
0answers
91 views

A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...
6
votes
5answers
579 views

What makes a set random?

There are many results in number theory, where the existence of some $B \subseteq \mathbb{N}$ with certain properties is proved by a probabilistic argument employing "random sets". One such example ...
3
votes
0answers
75 views

Orthogonal basis for the multilinear polynomials with zero “trace”

We say that a multilinear polynomial $P(x_1,\ldots,x_n)$ in $n$ commuting variables over $\mathbb{R}$ has zero trace if $$ \frac{d}{dt} P(t,\ldots,t) = 0. $$ Equivalently, $$ \left(\sum_{i=1}^n ...
2
votes
1answer
133 views

Is there a bijection from indecomposable to irreducible set partitions?

A partition of $[n]$ is indecomposable if no subset of its blocks partitions $[k]$ with $k \in [n-1]$. Irreducible set partitions are defined at http://oeis.org/A055105 . Both are counted by ...
1
vote
1answer
68 views

planar bipartite cubic graph

Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square ...
1
vote
1answer
147 views

Question about the theory of combinatorial species

The definition of a (combinatorial) species $F$ emphasizes that any bijection $\phi\, :\, A \to B$ between support sets $A$ and $B$ must induce a bijection between $F[A]$ and $F[B]$ (the ...
16
votes
2answers
343 views

Shortest supersequence of all permutations of $n$ elements

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences? A subsequence can be obtained from a sequence by deleting any characters, ...
2
votes
0answers
316 views

The twisted kiss of the curvaceous cubic and the staid tetrahedron (references)

(Migrated from MSE) While investigating some operators, I came across some relations between the twisted cubic curve and the tetrahedron that link together some notions in differential geometry, ...
1
vote
0answers
111 views

Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...
5
votes
0answers
174 views

Is it always optimal to evenly split search space in Rényi-Ulam game?

Suppose that we want to find one of finitely many elements (called pivot) by asking binary questions (one after the other) of which for at most $e$ we might get an incorrect answer and our goal is to ...
7
votes
1answer
137 views

Distribution of entries of a doubly-sorted random matrix

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...
10
votes
1answer
277 views

Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line ...
1
vote
0answers
118 views

How to prove this identity? (Perhaps related to partition) [closed]

How to prove this identity? $ \sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)}= \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$ I will appreciate it a lot if a solution using method ...
3
votes
0answers
119 views

characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set. Now, I wish to characterize all the periodic tilings of this set (better if they are ...
10
votes
1answer
470 views

Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq: Gonthier, Georges. Formal proof—the four-color theorem. Notices Amer. ...
15
votes
1answer
314 views

partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, ...
3
votes
0answers
85 views

Sets of polynomials with restricted set of products

Let $F = \{f_1, ..., f_n\}$ be a set of distinct monic polynomials (and thus also $f_i^2$ are distinct). Let $F' = \{f_i f_j: i \neq j\}$ be the set of pairwise products of all distinct elements from ...
5
votes
1answer
248 views

Grassmann-Plücker relations for permanents

Let $K$ be a field, $1 \leq d \leq n$ integers and $V$ an $n$-dimensional vector space. The Grassmann-Plücker relations are quadratic forms on $\wedge^d V$ whose zero set is exactly the set of ...
4
votes
2answers
311 views

A question about pairs of lines in 3D projective space

Consider a 3-dimensional projective space $X$. Let $m$ be the smallest number so that there are $m$ pairs of lines $ \ell_1,\ell'_1$, $ \ell_2,\ell_2'$, ... , $\ell_m, \ell'_m$ in $X$: a) For ...
3
votes
1answer
115 views

Cayley graph which is isomorphic to the line graph of a complete graph

From the literature, we know that the line graph of a complete graph $L(K_{q})$ is a Cayley graph if and only if $q \equiv 3$( mod 4) is a prime power. Now, if $q \equiv 3$( mod 4) is a prime power, ...
2
votes
1answer
146 views

relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color. However, could we convert edge type of Wang Tile ...
0
votes
0answers
182 views

A sum of binomial coefficients

Let $$ a_{i,j} = \binom{i+j}{i}\binom{2n-(i+j)}{n-i}. $$ I want to (asymptotically in $n$) compute $$ \sum_{i=0}^{n}\sum_{j=0}^{n} a_{i,j}^2. $$ Is there an easy way to do this? Are there generating ...
7
votes
1answer
446 views

Number of walks

How many walks (asymptotically) of length $2n$ with up or right steps from $(0,0)$ to $(n,n)$ are there such that the walk is always between the lines $y=x+k$ and $y=x-k$?
2
votes
1answer
134 views

Maximal number of antichains of a connected poset

Assume we have a connected poset $P$ of $n$ elements, I am searching to know what is the maximal number of antichains such a poset can have? $2^n$ is obviously an upper bound, and my feeling is that ...
7
votes
0answers
102 views

Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...
0
votes
0answers
115 views

Maximal “Spot It!” card count

This question was triggered by the game Spot It!. The game consists of cards, each having $k$ different symbols from an alphabet of $n>k$ symbols, with the property that any 2 cards have at least ...
8
votes
3answers
514 views

Changing combination lock [closed]

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...
2
votes
1answer
252 views

Bound for a combinatorial sum

I was playing around with a problem and I obtained a certain combinatorial sum. I was wondering if there was a way to simplify or bound it. I have a real valued function $f$, which satisfies $|f(x)| ...
3
votes
0answers
101 views

Triangulations of special polyhedra

Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
0
votes
1answer
102 views

Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ ...
4
votes
2answers
343 views

Can we sometimes define the parity of a set?

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...
5
votes
1answer
345 views

Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite $F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that, for all but finitely many $s\in S$, $$ ...
3
votes
0answers
55 views

Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...
2
votes
1answer
127 views

Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...
3
votes
1answer
151 views

Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...
1
vote
0answers
37 views

TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed

In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the ...
7
votes
1answer
163 views

What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?

Questions: Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation ...
3
votes
0answers
113 views

Asymptotics and combinatorics

Wright's expansion of $$ (1-z)^b\exp[A/(1-z)^c], \text{for } A > 0, 0<c<1\tag{1} $$ is, in the words of the late, great Mark Kac "well known to those that know it well". (See, for example, ...
13
votes
0answers
531 views

What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...