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
49 views

A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts. Start with an ...
7
votes
3answers
289 views

Increasing tower of subsets of ${1, …, k}$

Suppose $k$ is fixed. Consider a set $X$ of subsets of the ground set $\{1, \dots, k \}$, with the following property: there is some ordering of the elements of $X$, as $X = \{ x_1, \dots, x_n \}$, ...
0
votes
0answers
47 views

A lower bound on the number of matrices whose image contains all multiples of $p^e$

Let $0\leq e<e^\prime$ be integers. Now suppose $N$ is the number of $n\times n$ matrices over the ring $R:=\mathbb{Z}/p^{e^\prime}\mathbb{Z}$ (where $p$ is prime) such that ...
0
votes
1answer
86 views

Permutation with restricted pairwise ordering

There exist work on permutation with restricted positions (say, a permutation $\sigma$ satisfies $\sigma(i) = k$), and I am wondering if there exists a theory on permutation with restricted pairwise ...
8
votes
0answers
116 views

Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$. It is not very difficult to show that if $r(n) > 0$ ...
6
votes
1answer
161 views

Almost Hadamard matrices

As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$ and pairwise orthogonal rows or columns. Such matrices exist conjecturally in every dimension divisible by $4$. Call ...
7
votes
1answer
304 views

A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...
4
votes
0answers
178 views

A closed formula for this arithmetic function

The following function comes up in my research as part of a sufficient condition for capability of $p$-group of class two and prime exponent. Given a nonnegative integer $m$, express $m$ as a ...
3
votes
2answers
186 views

Making a graph claw-free by adding as few edges as possible

Independent set is polynomial in claw-free graphs, so I am wondering if this can approximate independent set. By adding enough edges to $G$ and gets claw-free $G'$. IS in $G'$ is IS in $G$, so this ...
2
votes
0answers
77 views

Techniques for proving that a set of constraints over the integers are inconsistent

I have a problem which boils down to showing that a set of constraints has no solutions. A simplified version of this constraint system would be the following system: $$ \left\{ \begin{array}{l} ...
2
votes
0answers
73 views

Lagrangean equations for the generating function of quadrangulations

Let $M(z)$ be the generating function of edge-rooted connected quadrangulations, with $z$ marking the number of edges. I derived the following Lagrangean equations for $M(z)$: $$M(z) = ...
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
813 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
106 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
107 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
392 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
100 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
126 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
207 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
59 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
107 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
184 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
65 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
899 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
237 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
216 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
571 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
176 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
155 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
205 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
175 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
206 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
129 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
144 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 ...