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)

2
votes
0answers
53 views

What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...
2
votes
0answers
63 views

Batched coupon collector with quota

Assume that you draw coupons uniformly at random from a collection of $n$ coupons and you want to collect $m_i$ coupons of type $i$. This is referred to as the coupon collector with quota ...
3
votes
1answer
72 views

Density of permutation of syndetic sets of integers

Define the upper uniform density of a set $A\subset\mathbb{Z}$ to be $$ D^+(A)=\lim_{r\rightarrow\infty}\sup_{a\in\mathbb{R}}\frac{|A\cap[a,a+r)|}{r} $$ Fix an arbitrary permutation of the integers ...
3
votes
0answers
95 views

Minimization module $p$

Let $p$ be a prime number, let $m$ be a fixed number (for example $2^{20}$), and $i=k^{-1}\cdot (j-t) \pmod{p}$ where $j \leq m$ and $m<k$. In the general case we have $t=0$, and $k,j$ are ...
1
vote
0answers
32 views

computational-expensive signal reconstruct - a combination problem [closed]

My problem is: I have a time series signal (vibration signal), use BSS algorithm (Blind Source Separation, we can regard it as a black box), separate the source signal into 100 components. Now I ...
4
votes
1answer
125 views

Maximum size of minimal sequence of transpositions whose product is a given permutation

Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...
0
votes
0answers
34 views

Minimal subset of an $n$-dimensional grid intersecting every ($n$-dim) arithmetic progression of length $k$

Let $$A=\{1,2,...,l\}^n \subset \mathbb{R}^n$$ for some positive integers $l$ and $n$, and $B \subset A$ be a set such that $|B| \ll l^n$. I am interested in determining how small must $B$ be in ...
11
votes
1answer
220 views

Generating function of a sequence is not algebraic

Let we have a sequence $\{a_{n}\}$, such that $\forall n \,\, a_{n}>0$ and $a_{n} \rightarrow\infty, n\rightarrow\infty$. Also let's suppose that we have a subsequence $\{a_{n_{k}}\}$ such that ...
1
vote
1answer
75 views
7
votes
1answer
126 views

Can the graph removal lemma be proved directly from the triangle removal lemma?

The Triangle Removal Lemma states that any graph with $o(n^3)$ triangles can be made triangle-free by removing only $o(n^2)$ edges. More generally, the Graph Removal Lemma states that for any graph ...
4
votes
1answer
148 views

What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
0
votes
1answer
129 views

Stable marriages for infinite bipartite graphs

Short and informal version: Does the stable marriage problem have a solution if there are $\kappa$ men and $\kappa$ women for any cardinal $\kappa \geq \aleph_0$? Long and formal version: Let ...
-2
votes
1answer
61 views

Splitting the vertices of undirected graphs into 2 sparse sets

(A version of this question for undirected graphs.) Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a ...
1
vote
1answer
111 views

Counting faces on multipermutahedra/multipermutohedra

A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron. In general, ...
1
vote
2answers
93 views

Minimal number of blocks in a $(n,n/2,\lambda)$ block design

A $(n,n/2,\lambda)$ block-design is a family $A_1,...,A_K$ of subsets of $[n]$ such that $|A_i|=n/2$ and for every $1 \leq i < j \leq n$ it holds that $\#\{1 \leq k \leq K : i,j \in A_k \} = ...
5
votes
2answers
166 views

How to construct particular De Bruijn sequences

For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples: ...
7
votes
3answers
292 views

A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
5
votes
0answers
73 views

Probabilistic distribution of sandpile model type

Let $G=(V,E)$ be a connected graph. Assume that $m\leqslant |V|$ hedgehogs sit in the vertices of $G$. If there are $r\geqslant 2$ hedgehogs in the same vertex $v\in V$, one of them goes to a randomly ...
1
vote
0answers
42 views

How to estimate the size of balanced biclique in random bipartite graph?

We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...
0
votes
2answers
160 views

Reference : Partition of integer

In algebraic number theory we come across following formula: $n= e_1f_1+\cdots+e_rf_r$ where all $e_i$ and $f_i$ are positive integers. I am sure writing a positive integer n as above must be ...
1
vote
1answer
113 views

Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings [closed]

As we know the number of different substrings has the upper bound $O(n^{2})$. Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings? Actually I ...
6
votes
1answer
360 views

Frankl's conjecture and Oeis sequence A188163

For every natural number $c \geq 2$, let $f(c)$ denote the least natural number $f$ with the following property : every union-closed family of sets with at least $f$ members has $c$ members whose ...
3
votes
0answers
49 views

Bounding the number of information sets in a linear binary code

A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a ...
2
votes
1answer
102 views

Intransitive finite irreducible linear groups whose orbits are all large

I am interested in intransitive irreducible linear subgroups $G\subseteq\mathrm{GL}_n(\mathbb{F}_p)$ acting on $V-\{0\}=\mathbb{F}_p^n-\{0\}$ in the natural way, such that all of the orbits are very ...
6
votes
1answer
140 views

Existence of a particular kind of polygonal subdivisions of surfaces

Let $\Sigma$ be a closed, compact, connected, oriented smooth $2$-manifold (in other words, a sphere or a torus with $g$ handles). We may draw smooth arcs on the surface in such a way that they cut it ...
1
vote
0answers
91 views

Recursively defined numbers vs geometric series

Let $a,b\in{\mathbb Z}^{\ge0}$ and $h\in{\mathbb R}(d_1,d_2)$ be such that $$a\ge b, \quad h(d_1,d_2)>0~~\forall\,d_1,d_2\in{\mathbb Z}^+, \quad ...
5
votes
2answers
142 views

Minimum length of a convex lattice polygon containing k lattice points?

Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary). It is not too hard to show that $k = \frac{1}{4\pi} ...
8
votes
1answer
285 views

How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$. Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting ...
4
votes
2answers
199 views

Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...
2
votes
0answers
101 views

Asymptotic analysis of generating functions

Let $a_d\!\in\!{\mathbb R}^+$ with $d\!\in\!{\mathbb Z^+}$ be a sequence such that $$\limsup \sqrt[d]{a_d}=1\,.$$ Define $$F(z)=\sum_{d=1}^{\infty}a_d\,{\text{e}}^{d z}\,.$$ Suppose $F(z)$ admits an ...
3
votes
0answers
131 views

A different equivalence relation on partizan combinatorial games

The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...
3
votes
1answer
83 views

Tournament whose large subtournaments contain no automorphism

For sufficiently large $n$, it is known that most tournaments of size $n$ contains no nontrivial automorphism, though I forgot the reference. For sufficiently large $n$, does there always exist a ...
4
votes
1answer
123 views

Representing a graph's vertices as linear combinations of paths

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...
5
votes
1answer
192 views

Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between ...
4
votes
0answers
128 views

Confusion with proof of Pieri's Formula

In Manivel's Symmetric Functions, Schubert Polynomials, and Degeneracy Loci, I am confused with some parts of his proof of Pieri's Formula. It is given as Pieri's Formula $3.2.8$ (p. $109$): If ...
3
votes
1answer
207 views

Periodic strings

I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end ...
4
votes
1answer
217 views

Eliminating a variable from a two-variable linear recurrence

In attempting to enumerate a combinatorial class of objects, I've come to a bivariate recurrence: $$ a_{n,k} = 2a_{n,k-1} + (k+1)a_{n-1,k+1} - ka_{n-1,k} - a_{n,k-2} + a_{n-1,k-1}. $$ Together with ...
7
votes
2answers
150 views

Self-complementary block designs

For what $n$ does there exist a self-complementary $(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design? (All I know is that a self-complementary design with these parameters does exist for all ...
3
votes
1answer
94 views

Menger's Theorem for planar triangulations

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...
3
votes
1answer
155 views

Braid group: Can a left-twist increase the number of right twists?

Disclaimer: This question was first posted on math.se without any answer. This is something that naturally occurs in my research, but I am no expert on this - it feels like a natural question so I am ...
0
votes
0answers
25 views

A measurement for vertex- and edge failure sensitivity

I want to have a metric that helps me judge how independent different paths in one graph are. So here are my assumptions: A graph consists of a set of vertices ($V$) and edges ($E$). A path ...
3
votes
1answer
102 views

Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations ...
1
vote
2answers
186 views

High order central moments of a symmetric binomial variable

Consider a random variable $X\sim B(n,\frac 12)$. I'm trying to estimate the asymptotic behaviour of its central moments $E((X-\frac n2)^r)$, where $r$ is even and in the range $\Omega(1)\leq r\leq ...
4
votes
1answer
117 views

A decomposition of $w_0$ which is similar to the reduced decomposition

Some basic definitions about reduced decomposition: In the symmetric group $S_n$, let $s_i$ denote the adjacent transposition $(i,i+1),i\in \{1,2,\cdots,n-1\}.$ Since $S_n$ is generated by adjacent ...
5
votes
1answer
166 views

Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$

How can I prove the following: $d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$ where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...
5
votes
0answers
125 views

Complexity of $\mathbb{Z}^n$ tilings

Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice. We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...
1
vote
2answers
155 views

aproximate sum involving binomial coefficients

I have the problem for computing the j-derivative of a logarithm, with $j\gg1$ \begin{equation} c_j=\left.\frac{\partial^j}{\partial s^j}\log\left(1+Ae^s+Be^{2s}\right)\right|_{s=0}, \end{equation} ...
9
votes
1answer
448 views

combinatorics on cyclic sequences

Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos. Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define ...
0
votes
0answers
45 views

Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific. Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...
4
votes
0answers
107 views

Littlewood-Richardson rule for the complete flag variety: GapP complete?

The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be ...