Do NOT use this tag; instead you might use co.combinatorics or various more specific tags.

learn more… | top users | synonyms

6
votes
0answers
741 views

How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective. I am interested in the size of ...
5
votes
0answers
103 views

Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
5
votes
0answers
556 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
5
votes
0answers
836 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
0answers
156 views

The properties of Pos

Given $n\in\mathbb{N}$, and $f:\mathbb{N}^*\rightarrow \mathbb{N}$, let define $Pos$ as: $$Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}|$$ When given $n\in\mathbb{N}$, this function gives the 'position' of $...
4
votes
0answers
226 views

Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
3
votes
0answers
110 views

Find the number of boolean functions of n variable that satisfy the following condition

For how many boolean functions is this true? The length of the shortest disjunctive normal form of that functions is equal to 2^(n-1). And the the number of variable entries in the minimal dnf of that ...
3
votes
0answers
126 views

Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum $$ F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1} $$ where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...
3
votes
0answers
66 views

What is the maximal number of partitions with this maximal intersection property?

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...
3
votes
0answers
108 views

“Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane. Here is the setup: Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...
3
votes
0answers
51 views

A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements. In a well celebrated paper Richard ...
3
votes
0answers
129 views

Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* $R(S)=\...
3
votes
0answers
126 views

Are there existing resources on modular-esque recurrence relations?

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this? $\begin{align*} f_{n,k}(x) & =a(x)f_{n-1,k}(x)+b(x)f_{n-2,k}(...
3
votes
0answers
135 views

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello, What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain $E = \{1,...,n\}$ and a partial function $f: E^3 \to \{-1, 0, 1\}$ ...
3
votes
0answers
763 views

Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation? For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...
2
votes
0answers
48 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 ...
2
votes
0answers
88 views

Growth of inner products between two random vectors on the sparse hypercube

We define the $s$-sparse hypercube in $\mathbb{R}^d$ as \begin{align} \mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\}, \end{align} where $ \| {\bf v} \|_0 $ ...
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
97 views

What kinds of complexes can be collapsed to?

A simplicial complex $S$ is collapsible if there is a sequence of elementary collapses that bring $S$ down to a single point; I'll denote this as $S \searrow \{pt\}$. I am wondering about a similar ...
2
votes
0answers
73 views

Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...
2
votes
0answers
553 views

Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
2
votes
0answers
184 views

Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$ where all $c_{ij}<0$ (so that ...
1
vote
0answers
39 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+ \...
1
vote
0answers
57 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 ...
1
vote
0answers
37 views

Is the complement of a vertex figure in an (abstract) polytope connected?

I consider an (abstract) regular polytope $P$, and $H$ a vertex figure of $P$. Is the complement $P \setminus H$ connected (as a poset, in the sense that its Hasse diagram, ignoring the improper faces,...
1
vote
0answers
26 views

Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions. Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...
1
vote
0answers
67 views

Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In particular i'm interested in the construction Valiant describes to prove that it is possible to ...
1
vote
0answers
15 views

Maximization of the difference of a monotone submodular function and a linear function with a cardinality constraint

Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can ...
1
vote
0answers
44 views

Estimates for derivatives of a positive discrete harmonic function

There is the following estimation (Duffin, Discrete potential theory, Theorem 5): Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...
1
vote
0answers
48 views

Simplifying closed form for Meta Operator

I was consider the set of linear operators: $$O_{a,k} = \frac{f(ax^k) - f(x)}{ax^k - x} $$' Particularly I am looking for the closed forms of the eigenfunctions of this operator, that is the ...
1
vote
0answers
93 views

Cross-correlation of two functions which are not fixed

I am trying to cross-correlate two functions, but one of which is changing each 'step' of the cross-correlation. I want to cross-correlate T(f) and ...
1
vote
0answers
212 views

Trigonometric semialgebraic conditions for two floors to be unequal [edited]

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric ...
1
vote
0answers
170 views

recursion formula for odd holonomic function

suppose we have a map $f:\mathbb{Z}\longrightarrow\mathbb{C}[t^{\pm}]$ with property that $f(i)=-f(-i)$. The algebra $\mathcal{T}=\mathbb{C}[t^{\pm}][L^{\pm},M^{\pm}]/[LM=tML]$ acts on $f$ by $(Lf)(...
1
vote
0answers
433 views

Zeroes of a tricky function.

I am attempting to show that there does not exist an N past which every open unit interval (k, k+1) -where k is an integer- contains a zero of the following function: $h(x)=\sum_{n=2}^{[\sqrt(x)]} \...
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 ...
0
votes
0answers
64 views

Factorial Sums over Compositions or ``Unlabeled Permutations"

Let $C_n$ denote subset of integer compositions of $n$ and $c=(c_1,c_2,\dots c_n)$ In a divergent sum, the sequence $$ a_n=\sum_{c\in C_n} \prod_{c_i\in c} c_i! $$ frequently shows up and one ...
0
votes
0answers
96 views

Summing up costs over a Markov chain

I apologize in advance if this question is too simplistic to be appropriate for MathOverflow. I have inquired in multiple places but have found little to indicate that this is a previously studied ...
0
votes
0answers
183 views

Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and $...
0
votes
0answers
133 views

A good upper bound on the size of k-biclique in random bipartite graphs.

Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...
0
votes
0answers
86 views

An upperbound related to inductively reducing a set by adding the two least elements

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:) Let $S_0={\{a_1,...
0
votes
0answers
238 views

Partial Recurrence Equation

Hey people I have the following equation, which I don't manage to solve. The background of the problem is the clustergrowth of two chemical species, resulting in a final relation I'd like to solve: ...