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

Closed form solution of a complex recurrence relation

I am looking for a closed form expression for $ST(n, k)$ defined as $$ ST(n, k) = \sum_{s = 0}^{n - k} {{n - k} \choose s} QT( k + s, k + s - 2, k), $$ where $QT( n, m, k)$ is defined by the ...
4
votes
0answers
113 views

Convex polytopes as “products” of lower dimensional polytopes of the same family

This MO answer on enumerative geometry details the sense in which an associahedron is a product of lower dimensional associahedra, and the comments in this MSE-Q indicate the same is true for ...
11
votes
1answer
1k views

Why is this character expression an integer?

Let $\gamma$ be an $n$-dimensional complex representation of a finite group $G$ with character $\chi$ and let $e=c_0, c_1, ..., c_{\ell}$ be a set of conjugacy class representatives for $G$. In the ...
2
votes
1answer
152 views

Generating function for numbers divisible by some primes

Consider the first $k$ primes $p_1 = 2, p_2 = 3, \dots, p_k$. Let $A_k$ be the set of numbers that are divisible by at least one $p_i$. We can represent this set as a generating function: $$G_k(x) = \...
1
vote
0answers
52 views

On structure of patterns of subset sums?

There are roughly $2^{nm}$ choices of sets of $m$ distinct integers in $[-2^n,2^n]$ (after fixing ordering). Each set of $m$ integers has $2^m$ subsets. Suppose we assign $\{0,1\}$ value to each ...
8
votes
1answer
77 views

Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?

Suppose we have a symmetric polynomial $P$ in $n$ variables. We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}. We can thus see $P$ as an element in $Q[x_1]...
0
votes
1answer
79 views

Does general case of following function exist?

Suppose we have the following: $m_1 m_2 m_3$ Where $m_1$, $m_2$, $m_3$ are constants $> 0$ I'm looking for a function $f$ such that: $m_1 m_2 m_3 = 1.0 + f(m_1,m_2,m_3) + f(m_2,m_1,m_3) + f(m_3,...
2
votes
0answers
64 views

Which matroids have not unique unimodular representation?

Matroid $M$ is represented by real vectors, and we know that any base of $M$ generates the same lattice (this is called unimodular representation, I guess.) If we change the sign of any vector, we ...
2
votes
1answer
245 views

Number of subsets that sum to $0$

Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
7
votes
2answers
207 views

Graphs with prescribed numbers of k-cliques

Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers. Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...
2
votes
1answer
90 views

How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?

I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$...
2
votes
1answer
133 views

How many lines of exactly n points can be placed in a discrete, square grid of size m x m?

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of ...
5
votes
2answers
136 views

Multiplication in universal enveloping algebra in terms of PBW isomorphism

Let $\mathfrak g$ be a Lie algebra. Consider the multiplication map $m:\mathfrak g\otimes U(\mathfrak g)\to U(\mathfrak g)$ and $i:S(\mathfrak g)\to U(\mathfrak g)$ -- Poincare-Birkhoff-Witt ...
2
votes
0answers
115 views

Nonvanishing of the dual Euler totient on boolean intervals of finite groups

The rank $n$ boolean lattice $B_n$, is the subset lattice of $\{1,2, \dotsm n \}$. Let $[H,G]$ be a boolean interval of finite groups. Its Euler totient is defined by $$\varphi(H,G):=\sum_{K \in ...
3
votes
0answers
60 views

How many unimodular lattices does it take to fill a cube with high probability?

Consider $C_a$ in $\Bbb Z^n$ a cube of height $a$ at origin in positive coordinates with one corner at origin. Consider the set $M_c$ of all unimodular matrices in $\Bbb Z^{n\times n}$ with each ...
0
votes
0answers
76 views

Derandomizing AP existence in $A\subseteq \{1,\ldots,N\}$ for $\delta(A) \geq 1/k$

In the answer to the mathoverflow question here, it was established that if we let $p$ be the probability of including point $v$ in $A\subseteq \{1,\ldots,N\}$ and this is done independently for all ...
1
vote
0answers
114 views

A probability question related to combinatoric problem

I am trying to solve a combinatoric problem. The problem is the following: There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X ...
0
votes
0answers
24 views

is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...
1
vote
1answer
107 views

Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$. Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...
1
vote
1answer
91 views

Intersection of members in a separating union-closed family of sets

Tony Huynh gave a nice answer to a question I asked here : Number of members of a separating union-closed family whose universe has given cardinality The answer shows in fact that if $\mathcal{F}$ ...
0
votes
0answers
161 views

Warren's Theorem

At the end of page 12 in this document Noga Alon mentions Warren's Theorem on sign patterns: tau.ac.il/~nogaa/PDFS/tools1.pdf Does anyone know of an intuitive explanation of the proof of it ? Also, ...
1
vote
3answers
214 views

Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, ...
5
votes
1answer
269 views

Vector with many non-zero coordinates

Given finite field $\mathbb{F}_q$, positive integers $n$ and $k<n$. Given $k$-dimensional subspace $X$ of $\mathbb{F}_q^n$, for which $m=m(q,k,n)$ may we find for sure a vector in $X$ with at least ...
2
votes
0answers
63 views

Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there? A vaguer question: can I write $K_{4n}= K_4 + K_4 +.......
2
votes
1answer
106 views

Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement : If $n$ is a natural number $\leq 4$, if $\mathcal{F}$ is a union-closed family of nonempty sets, if the universe of $\mathcal{F}$ (i.e. ...
1
vote
1answer
47 views

How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...
1
vote
0answers
69 views

Missing count in number of perfect matchings

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
3
votes
1answer
82 views

Does the Chen-Chvátal Conjecture on metric spaces hold for maximal lines?

A conjecture by Chen and Chvátal asks for the minimum number of induced "lines" in a metric space, in the same spirit as the De Bruijn–Erdős theorem. Though the statement of this problem on Douglas ...
3
votes
0answers
39 views

Does the rank (=height) of a well partial order bound its type (=length, =stature)?

Terminology and context (This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.) A partially ordered set is called well-...
6
votes
1answer
214 views

Is the exponent $2$ sharp in the Balog-Szemerédi-Gowers Theorem?

The Balog-Szemerédi-Gowers theorem can be stated in the following form: let $A,B$ be subsets of $\mathbb{Z}/n\mathbb{Z}$ (say) with equal cardinality, such that $$ \|1_A*1_B\|_2 \ge K^{-1} \|1_A\|_1 \|...
0
votes
1answer
75 views

Choosing directed subgraph in a triangulation

Consider triangulation $T.$ Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...
12
votes
1answer
480 views

A combinatorial identity involving harmonic numbers

The harmonic numbers are given by $$H_n=\sum_{k=1}^n\frac{1}{k}.$$ Numerical calculation suggests $$ \sum_{k=1}^{n}(-1)^k{n\choose k}{n+k\choose k}\sum_{i=1}^{k}\frac{1}{n+i}=(-1)^nH_n. $$ I can not ...
1
vote
0answers
147 views

A conjecture about orbits in a recursive function motivated by Kolakoski's sequence

We first introduce several functions motivated by Kolakoski's sequence. The conjecture itself can be stated independently of Kolakoski's sequence. You can skip straight to the formulation of the ...
15
votes
1answer
336 views

Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6) Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each ...
2
votes
2answers
124 views

Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$

It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^...
5
votes
1answer
250 views

Combinatorics: set partitions of a poset

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $\max(B_i)$ be the maximum value in the ...
2
votes
1answer
144 views

Can we deduce that a finite topology $T$ satisfies Frankl's union-closed set conjecture?

Let $X$ be a finite set and $T$ be a topology on $X$. Then $T$ is both union-closed and intersection-closed. Can we deduce that $T$ satisfies Frankl's union-closed set conjecture? (We know that a ...
1
vote
0answers
40 views

Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$. Define linear functions $f(x)= a_1x_1+ \...
4
votes
1answer
96 views

Probability of existence of a base in the span of sparse vectors in GF(2)

For $i=1,2,\dots,l$, let $\mathbf{v}_i =(v_{i1},v_{i2},\dots,v_{in}) \in \mathbb{F}_2^n$ be a sparse vector in GF(2) such that all $v_{ij}$'s are independent for all $1 \le i \le l, 1 \le j \le n$ and ...
2
votes
1answer
160 views

The class of $(-1,0,1)$-matrix with all row sums and column sums equalling to $0$

Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ satisfying all row sums and column sums are equal to $0$. For any $M\in ...
4
votes
2answers
130 views

Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...
3
votes
2answers
144 views

Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of $A$...
2
votes
0answers
70 views

Given a vector of positive integers, count the number of combinations which have a sum that produces a different value

I have a list (vector) of positive integer numbers, including repetitions. For example, $L = [1, 1, 4, 1, 3]$; I want to calculate the number of different sums obtained by using the elements of $L$, ...
1
vote
0answers
59 views

bounded degree graph colouring.

I was wondering if anyone could provide references on the following: Is determining the chromatic number of a bounded degree graph APX-complete? 2.I've seen the result that states it is NP-hard ...
3
votes
0answers
73 views

Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
4
votes
1answer
83 views

Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number $\chi(...
2
votes
1answer
261 views

upper bound on derivatives of a function defined on an arc

This is a simple question I asked in math.SE last month but unfortunately no one gives any comment. So I decided to try some luck here. You can skip examples below and read from "General setting" at ...
5
votes
1answer
207 views

Can we cover a set by a particular family of sets?

Let $A_1,A_2,\ldots,A_m,B_1,B_2,\ldots, B_m$ be (not necessarily distinct) subsets of $[n]=\{1,2,\ldots,n\}$. Suppose that each $i\in [n]$ appears in at least $k$ of these $2m$ sets. I want to ...
1
vote
1answer
89 views

Weighted counting of circular codes

Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}...
3
votes
1answer
179 views

A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...