# Tagged Questions

**-5**

votes

**0**answers

47 views

### How many ways are there to order the numbers from 1 to 25 so that no primes occur consecutively? [on hold]

I just had this on an exam and was wondering if I answered it correctly. My solution was to first order the 16 composite numbers in this range, giving 17 spots to insert the 9 primes. So we have ...

**5**

votes

**2**answers

434 views

### mod 5 partition identity proof

I am looking for a proof that:
$$\prod_\limits{m=0}^\infty \dfrac{1}{(1-x^{5m+1})}=\sum_\limits{i=0}^\infty \dfrac{x^i}{\prod_\limits{j=1}^i (1-x^{5j})}$$
The left hand side expands into:
...

**8**

votes

**2**answers

75 views

### How many uniquely colored degree two vertices in 3-coloring of subcubic graph?

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as ...

**7**

votes

**2**answers

207 views

### What is the probability that two random permutations have the same order?

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...

**-1**

votes

**1**answer

99 views

### Frankl's union-closed sets conjecture for infinite families

This question is motivated by Frankl's union-closet sets conjecture.
Let $X$ be a non-empty set. We say that a family ${\cal A} \subseteq {\cal P}(X)$ is union-closed if $\emptyset\notin{\cal A}$ and ...

**1**

vote

**2**answers

115 views

### question about literature in the field of Ramsey's theory [on hold]

i am searching for an on- line paper or a book, or maybe just a paper or a book which consists a proof of finite Ramsey's theorem for sets (not for graphs). i need a combinatorial proof which is not ...

**2**

votes

**1**answer

45 views

### Induced matching of cycle

Definition:
A graph $G$ is chordal if every induced cycle in $G$ has length 3, and is co-chordal if the complement graph $G^c$ is chordal.The co-chordal
cover number, denoted $cochord (G)$, is the ...

**2**

votes

**1**answer

73 views

### Discrepancy of elements in minimal members of a union-closed set

This question is motivated by Frankl's union-closet sets conjecture.
Let $n\in\mathbb{N}$ and set $[n] = \{0,1,\ldots,n\}$. We say that a family ${\cal A} \subseteq {\cal P}([n])$ is union-closed if ...

**0**

votes

**1**answer

179 views

### Order-Perserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...

**0**

votes

**0**answers

92 views

### Ramanujan graphs and stable real polynomials

I have a problem with the lemma 6.5 and the theorems 5.1, 6.6 in the paper of Adam Marcus, Daniel Spielman and Nikhil Srivastava. http://arxiv.org/pdf/1304.4132.pdf
I do not understand how they use ...

**1**

vote

**1**answer

72 views

### Vectors which average to zero over any graph neighborhood

Given an undirected connected graph on $n$ nodes, let $S$ be the subspace of vectors $x \in \mathbb{R}^n$ which satisfy $$\sum_{j \in N(i)} x_j = 0,$$ for all $i=1, \ldots, n$. Here $N(i)$ is the set ...

**6**

votes

**1**answer

176 views

### Even parking functions and spanning trees of complete bipartite graphs

Set $\mathbb{N} := \{0,1,2,\ldots\}$. A parking function of length $n$ is a sequence $(\alpha_1,\ldots,\alpha_n) \in \mathbb{N}^n$ whose weakly increasing rearrangement $\alpha_{i_1} \leq \alpha_{i_2} ...

**2**

votes

**2**answers

138 views

### Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?
I've done some work on this and have found a way of calculating this that's ...

**5**

votes

**1**answer

182 views

### Does this notion related to species/operads/FI-modules have a name?

Let $B$ be the symmetric monoidal category of finite sets and bijections with disjoint union. Let $C$ be a symmetric monoidal category. Is there a standard name for a lax monoidal functor $F:B \to C$? ...

**5**

votes

**1**answer

161 views

### How often can subsets of a universe intersect exactly once?

My question is inspired by the following observation:
Claim: It is not possible to choose $n$ subsets of the universe $[n]$, each of size $\Omega(n)$, such that for each subset $S$ and each element ...

**11**

votes

**1**answer

233 views

### A sum over characters of the symmetric group

Let $C_\mu$ be the size of the conjugacy class in $S_n$ of permutations whose cycletype is the partition $\mu\vdash n$. Let $\chi$ be the characters of the irreducible representations of $S_n$.
Let ...

**0**

votes

**0**answers

10 views

### Approximation preserving reductions

I've seen in the following document
https://hal.archives-ouvertes.fr/hal-00958028/document
A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...

**1**

vote

**0**answers

44 views

### Directed graph Laplacian with exactly one negative eigenvalue

Let $G$ be a digraph with adjacency matrix $A =(A_{ij})$ where $A_{ij}=1$ if and only if there is a directed edge $i \to j$ and $A_{ij}=0$ otherwise. Let $D= (D_{ij})$ be the degree matrix with ...

**-3**

votes

**0**answers

38 views

### To find the minimum no of games from the given average average may be ither integer or in decimal form [closed]

suppose a player plays no of games and he scores some score in his each games . And his average score is given we have to find how many minimum games he will play to score given average score . And ...

**-5**

votes

**0**answers

31 views

### There are ten chairs in a row [closed]

There are ten chairs in a row.
In how many of these will two people be sitting in adjacent chairs?
I count 16. P1 and P2 must sit beside each other, adjacent, so there are only 8 chairs where that ...

**4**

votes

**1**answer

123 views

+50

### Probability bound for perfect matching

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**3**

votes

**4**answers

211 views

### How small can a set system containing a large subset of every set be?

Fix $1>c>0$. Consider the set $[n]=\{1,2,\ldots,n\}$ and the set of all subsets of this set which we'll denote as $2^{[n]}$. Let $S \subseteq 2^{[n]}$ be a set system such that for every ...

**0**

votes

**0**answers

100 views

### Use of category theory for representing, describing, and/or predicting high dimensional objects [closed]

Is there any work that has investigated the use of category theory for representing, describing, and/or predicting high dimensional objects in which there can be a huge number of combinatorial ...

**2**

votes

**1**answer

150 views

### Extracting a full rank matrix from a 0-1 matrix

If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...

**3**

votes

**1**answer

69 views

### Generalizations of the Triangle Removal Lemma to smaller exponents

The Triangle Removal Lemma states:
For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by ...

**10**

votes

**2**answers

265 views

+50

### Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?
Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = ...

**2**

votes

**2**answers

365 views

### Closed formula for the generating function of the sequence of powers

Does anyone know of a closed formula for the function
$f_k(x)=\sum_{n=1}^{\infty}{n^k x^n}$ ? That is, the generating function of the sequence $1^k,2^k,3^k...$.
It is not hard to see that ...

**0**

votes

**0**answers

129 views

### Shortest distance on a combinatorial chess board

Consider a random $n\times n$ combinatorial $0/1$ square matrix over field $\Bbb F$ of rank $r$ with every row distinct and every column distinct as a chess board.
Definition of combinatorial ...

**0**

votes

**0**answers

41 views

### Inapproximability of Combinatorial Optimization Problems

I've been reading the "Inapproximability of Combinatorial Optimization Problems" by Luca Trevisan (see: link). On pages 3-4 it mentions that a polynomial time algorithm for 3SAT would exist if there ...

**0**

votes

**0**answers

50 views

### Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,...,H_{r-1},H_r=H' \} \subseteq P$ so that ...

**2**

votes

**1**answer

210 views

### Generalization of the Bollobas theorem in extremal set theory

The Bollobas'1965 theorem is the following:
If $A_1,...,A_n$ and $B_1,...,B_n$ are two sequences of subsets of $X=\{1,...,r\}$ such that $A_i\cap B_j = \emptyset$ if and only if $i=j$, then
...

**4**

votes

**0**answers

85 views

### For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?

There exists a Latin square of order $8$ which can be partitioned into $2 \times 4$ subrectangles:
$$
\begin{bmatrix}
\color{red} 1 & \color{red} 2 & \color{red} 3 & \color{red} 4 & ...

**4**

votes

**0**answers

107 views

### Reference for the notion of polyhedra “degenerations”

Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ ...

**2**

votes

**2**answers

175 views

### Batched Coupon Collector Problem

The batched coupon collector problem is a generalization of the coupon collector problem. In this problem, there is a total of $n$ different coupons. The coupon collector gets a random batch of $b$ ...

**11**

votes

**1**answer

402 views

### Plugging $1-x$ into Schur polynomials

I have a symmetric Laurent polynomial $f$ in $k$ variables expressed as a linear combination of Schur polynomials. I'd like to know what happens when I make the substitution $p(x_1,\ldots,x_k)\mapsto ...

**-3**

votes

**2**answers

131 views

### Does every 3-regular bridgeless graph have a perfect matching? [closed]

Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?

**0**

votes

**0**answers

43 views

### Co-chordal graph properties

Definition:
A graph $G$ is chordal if every induced cycle in $G$ has length 3, and is co-chordal if the complement graph $G^c$ is chordal.
Suppose $G$ is co-chordal subgraph of $G_1$, where ...

**3**

votes

**1**answer

106 views

### How different can characters be for a sum of modular forms to still be in Gamma_0?

I have a modular form I am constructing out of sums and products of various dissected divisor-sum series, namely forms of the type $$f_i = \sum_{j=0}^\infty \sigma_1(36j+i) q^{36j+i}.$$
Each of these ...

**1**

vote

**0**answers

23 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} ...

**5**

votes

**2**answers

122 views

### Generalized cycle index polynomial for the symmetric group

The answer to a particular calculation in quantum information theory gives me the following expression:
Given $M$ specific elements of the symmetric group $S_n$, define the polynomial
$$Z_n(\pi_1, ...

**2**

votes

**1**answer

79 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**2**

votes

**0**answers

106 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...

**2**

votes

**1**answer

229 views

### Estimate of the number of rabbit integers with a given congruence

Consider the Fibonacci words $B_n$:
$B_1 = 1$
$B_2 = 10$
$B_3 = 101$
$B_4 = 10110$
$B_5 = 10110101$
(start with $B_1=1$, and go from $B_n$ to $B_{n+1}$ by replacing every occurence of $1$ in ...

**2**

votes

**0**answers

136 views

### Polynomials representing locally constant functions

Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...

**5**

votes

**0**answers

178 views

### Factorization of permutations into two factors with fixed number of cycles, plus a placement condition

In my recent work I have been led to consider the following type of permutation factorizations.
Let $\pi_1$ and $\pi_2$ be two fixed permutations, with disjoint support, i.e. $\pi_1$ acts on ...

**6**

votes

**3**answers

310 views

### Does a planar triangulation always contain a Hamiltonian path?

What about a Hamiltonian path in a triangulation of an n-gon? If not, how long is the longest path?

**2**

votes

**0**answers

99 views

### Variants of Szemeredi's regularity lemma

I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs.
Specifically, I'm interested in the distinction between two of ...

**1**

vote

**0**answers

44 views

### Rank-unimodality and Sperner property of higher dimensional partitions

I did a google-search but have not been able to find much reference on this problem. So I am asking it here hoping to get some information.
Consider the set of all 4-dimensional Ferrer's diagram ...

**5**

votes

**1**answer

201 views

### reverse definition for magic square

Recently, I saw a question in see here which is so interesting for me. This question is as follows:
Is it possible to fill the $121$ entries in an $11×11$ square with the values $0,+1,−1$, so that ...

**5**

votes

**1**answer

145 views

### Smallest length of {0,1} vectors to satisfy some orthogonality conditions

Let $n$ be a positive integer.
The output of the problem is another positive integer $r$ which must be as small as possible.
I want to construct $2n$ binary vectors $x_i\in\{0,1\}^r$ and ...