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)

0
votes
0answers
64 views

Usage of multinomial theorem with infinite series

What are the conditions for using the multinomial theorem with infinite series? I have an expression but I don't know if I can use it. The expression is: $$ \left[\sum_{m=0}^{\infty} \frac{\mu^m ...
7
votes
2answers
802 views

Linear independence of the square roots over Q

Does there exist a real number $a$ such that the numbers $\sqrt{n^2 + a^2}$ (for all natural $n$) are linearly independent over the field of rational numbers? It is evident that $a$ cannot be ...
0
votes
0answers
102 views

What is the number of connected subgraphs with $n$ vertices of a labelled connected simple graph with $n$ vertices?

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs ...
3
votes
0answers
105 views

Kasteleyn, Gessel-Viennot and eigenvalues

The Kasteleyn matrix (for counting perfect matchings) and the Lindström-Gessel-Viennot matrix (for counting families of nonintersecting lattice paths) are tightly related, as observed many times by ...
6
votes
0answers
295 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
4
votes
5answers
389 views

Lattice points in dilated polytopes and sumsets

Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$. Let $p_1,\dots,p_m$ be all lattice points in $P$. Question: What is the condition on $P$ that guarantees ...
10
votes
0answers
98 views

Does a huge set of random points in the plane almost surely have a checkerboard-triangulation

A set of $n$ points in the plane in generic position (no alignement of three points) has at least $2.012^n$ different triangulations of its convex hull involving only the set of given points.We call ...
6
votes
1answer
125 views

Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: ...
1
vote
1answer
205 views

Sum of covariance matrix of products of dependent variables

Consider the sequences of random variables $\{X_i\}_{i=1}^n$ and $\{Y_i\}_{i=1}^n$, as well as the corresponding sequence of products, $\{X_i Y_i\}_{i=1}^n$. All $X_i$ share the same mean value, ...
3
votes
0answers
58 views

Asymptotics of partitions in at most n parts, bounded by r

I posted this question on MathStackexchange (http://math.stackexchange.com/questions/639878/asymptotics-of-partitions-in-at-most-n-parts-bounded-by-r) some time ago, but it did not receive any answer, ...
0
votes
0answers
37 views

Minimize $td-2\sum_{i=0}^{t-1} w_k(i)$ where $w_k(i)$ is the sum of the base-$k$ digits of $i$

Let $K_k^n$ denote the $n$-fold cartesian product of the complete graph on $k$ vertices, and let $[R,T]$ be the edge cut, consisting of the edges between complementary vertex sets $R$ and $T$. I ...
1
vote
0answers
46 views

Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size. Here is a picture of $K_{6}$ with 5 ...
3
votes
1answer
50 views

Are all (non-constant) symmetric submodular functions non-monotone?

I am trying to show (if possible) that symmetric submodular functions are non-monotone (excluding constant sub-modular functions). Recall that a submodular function $f : 2^{\Omega} \rightarrow R$ is ...
4
votes
2answers
136 views

class 1 vs class 2 in regular graphs

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph. A graph with edge chromatic number equal to ...
31
votes
1answer
1k views

Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar ...
3
votes
1answer
106 views

Domino Shuffling and Warren's process

In this paper by Nordenstam, it is shown that a certain interlacing particle process that arises from uniformly random Aztec diamond tilings is amazingly similar to Warren's process. One of the ...
4
votes
2answers
183 views

Union of Permutations

This is a problem I asked on http://math.stackexchange.com/questions/647382/union-of-permutations. Feel free to close it if you think it below research level. Having $k$ different permutations, ...
1
vote
0answers
64 views

Separating unit disks by circles

This is inspired by the recent question about separating unit disks by lines, which I will refer to as the "line case". Replacing "line" by "circle" adds one degree of freedom, and I'm wondering if ...
34
votes
2answers
898 views

Is there an analog of Sperner's lemma for the Hopf invariant?

Recall that Sperner's lemma is essentially a combinatorial version of the topological statement "A map from $S^n$ to $S^n$ with degree one cannot be nullhomotopic." My question is, does there exist ...
5
votes
1answer
236 views

Homomesy in perfect matchings

Assume $n \geq 2$. Let $\mathcal{M}_n$ denote the set of perfect matchings on $[2n] := \{1,\ldots,2n\}$, i.e., the set of partitions of $[2n]$ into pairs. For $M \in \mathcal{M}_n$, and $p = ...
7
votes
1answer
215 views

Separating unit disks by lines

Given $n\ge 2$. For a real $d>2$, consider a constellation $C$ of $2n$ disks of radius $1$ in the plane such that $h(C)$, the minimal distance between any two of their centers, is equal to $d$. Let ...
5
votes
3answers
569 views

Binomial Identity

I recently noted that $$\sum_{k=0}^{n/2} \left(-\frac{1}{3}\right)^k\binom{n+k}{k}\binom{2n+1-k}{n+1+k}=3^n$$ Is this a known binomial identity? Any proof or reference?
4
votes
1answer
175 views

An intutive reason why a “distance” metric may be a poor one for a procedure where we attempt to modify a string (mutating 0 OR 1 bits)

If I'm attempting to mutate one arbitrarily chosen binary string $s_a$, to another arbitrarily chosen binary string $s_b$, in the smallest number of steps (i.e. with the smallest number of mutations) ...
21
votes
3answers
533 views

Number of terms in certain polynomials over $\mathbb{F}_2$

I raised this question in my answer to On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$. Let $s_1,s_3,s_5,\dots$ be indeterminates over the field $\mathbb{F}_2$, and recursively set ...
1
vote
1answer
154 views

Natural bijection between sets with coloured elements?

In Andreas Blass's famous paper `Seven Trees in One', the existence of a natural bijection between binary trees and 7-tuples of binary trees is related to the equation $T^7 = T$ being satisfied by a ...
5
votes
0answers
141 views

Power sums and Jack symmetric functions

Let $\Lambda$ be the algebra of symmetric functions in infinitely many variables over $\mathbb{C}$. The $n$-th power sum symmetric function $p_n$ is defined (formally) as \begin{equation} p_n=\sum_i ...
2
votes
3answers
204 views

Regular graphs whose neighbourhoods induce matchings

Studying some problem I've arrived to the following notion. Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a ...
6
votes
1answer
175 views

The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
-9
votes
1answer
173 views

Combinatorics by complex number [closed]

Compute: $ \binom{n}{o} $- $\binom{n}{2}$+ $\binom{n}{4}$- $\binom{n}{6}$+ $\binom{n}{8}$-...-$\binom{n}{4k-2}$+$\binom{n}{4k}$.
3
votes
1answer
185 views

Product of cycles of length $n$

Let $n = 2k$ and suppose that $\sigma$ is a permutation in $S_n$ which is equal to a product of k disjoint cycles of length $2$. In how many ways one can write $\sigma$ as a product of two cycles of ...
1
vote
1answer
116 views

Upper-bound for maximal-cliques on perfect graphs

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison ...
3
votes
2answers
380 views

summation of products of combinatorials

For any natural number $N$ and $0\le n\le N$ define $$ f(n) = f(n,N) = \frac{1}{(N+1)!} \sum_{\substack{{S\subset \{1,\ldots,N\}} \\ {|S|=n}}} \prod_{s\in S} s. $$ (The empty product is interpreted ...
2
votes
0answers
196 views

Complete presentations for one-relator semigroups (100\$+100\$ question)

It is an open problem whether word problem for one-relator semigroups is decidable, but it is even unnknown if one-relator semigroups always admit finite complete presentations (i.e. a finite complete ...
6
votes
1answer
115 views

Separating infinite words sharing factors by automata

Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other. Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...
1
vote
0answers
128 views

Asymptotic behaviour of sequence

I am interested in the sequence $$a(n)=\sum_{k=0}^n {p(n-k)-1 \choose k}$$ where $p(n)=(r-1)n^2+(2r-1)n+r$ for some $r \in \mathbb{N}$ or more generally any polynomial equation. When $r=1$ this ...
6
votes
0answers
106 views

What is the mobius function for the set of simplicial complexes on n vertices?

Consider the set of simplicial complexes on $n$ vertices, with partial ordering by containment. What is the Mobius function for this poset? Are other combinatorial facts known about it (e.g. the ...
2
votes
0answers
105 views

Is there a system of quasigroup equations implying non-associativity?

I have read that if 4 quasigroup operations, $\cdot,\circ,\star,\square$, on a set $S$ respect the following equation: $$x\cdot (y\circ z) = (x \star y) \square z$$ for all $x,y,z\in S$, then all 4 ...
4
votes
1answer
143 views

Can a partition free family in $2^{[n]}$ always be enlarged to one of size $2^{n-1}$?

Let $\left[ n \right]=\{{1,2,\cdots,n\}}$ and call a family $\mathcal{F} \subset 2^{\left[n\right]}$ partition-free if it does not contain any partition of $\left[n\right]$. A recent question asked ...
1
vote
1answer
112 views

Partition-free subsets of $2^{[n]}$

Let $[n]$ denote the set of integers $\{1,2,\ldots,n\}$. A subset of $2^{[n]}$ is partition-free if it does not contain a partition of $[n]$. What is the maximum size of a partition-free subset of ...
0
votes
0answers
65 views

Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...
8
votes
3answers
339 views

colorings of ${\mathbb Z}^d$ with constraints

For a lattice $\mathbb Z^d$, denote by lattice line any line that contains two (and thus infinitely many) lattice points. For $2\le k<n$, define a $(n,k)$-coloring, or $C_d(n,k)$ for short, ...
10
votes
2answers
483 views

A binomial determinant fomula

Is there an existing or elementary proof of the determinant identity $ \det_{1\le i,j\le n}\left( \binom{i}{2j}+ \binom{-i}{2j}\right)=1 $?
3
votes
1answer
169 views

Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs. Conversion from a Hadamard Matrix into a Hadamard Graph An $n$-Hadamard graph $G$ ...
3
votes
0answers
198 views

How many combinations does Android pattern have? [closed]

Rules- 1) At-least 4 and at-max 9 dots must be connected. 2) There can be no jumps 3) Once a dot is crossed, you can jump over it.
24
votes
2answers
841 views

A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture: Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
1
vote
1answer
187 views

Groups with no small generating set

Is there a classification of groups having the property that any set of $d$ elements (say including the identity) is contained in a proper subgroup? It is appealing to call the maximum such integer ...
6
votes
1answer
228 views

Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; ...
5
votes
1answer
69 views

Generalising the adherence operator and its closure properties with regard to regular (rational) languages

Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some ...
1
vote
1answer
228 views

A problem on counting k-subsets of {-n,-n+1,…,n-1,n} satisfying that sum of elements equal to 0

I'll use another way to give the question besides the title. Define $$ A_k(n) = \frac{1}{2 \pi \mathrm{i}} \int_{|q|=1} \left( \frac{1}{2 \pi \mathrm{i}}\int_{|z|=1}\prod_{j=-n}^{n}(1+qz^j) ...
1
vote
1answer
147 views

Associative binary operations defined on a finite set

We can easily test the commutativity of a binary operation on a set of $\ n\in\mathbb{N}\ $ elements by observing the symmetry of the $\ n\times n\ $ multiplication table. I was looking for a ...