**2**

votes

**2**answers

178 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

411 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

44 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

107 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

134 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

107 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

230 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

138 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

315 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

101 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

150 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 ...

**8**

votes

**2**answers

305 views

### Characters of permutation groups

Let $N$ be a fixed positive integer, and denote by $C(m)$ the number of
permutations on an $N$-element set that have exactly $m$ cycles (counting
$1$-cycles). Then it is in the literature that the ...

**3**

votes

**0**answers

72 views

### Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this?
...

**0**

votes

**0**answers

51 views

### Order statistic of Markov chain sample path and related probabilities

Consider a 1D sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with transition ...

**-1**

votes

**1**answer

170 views

### FInd smallest value $r$ such that a $n\times r$ matrix exists [closed]

The input of my problem is an integer $n\geq 3$.
The output is an integer $r\geq 1$ which must be as small as possible such that there is a $(n\times r)$ matrix verifying the following constraints:
...

**3**

votes

**2**answers

149 views

### Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...

**0**

votes

**0**answers

36 views

### lower bound for solve ECDLP

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Suppose $\ell$ be the number of bits in $k$, and let $k_i$ ...

**7**

votes

**0**answers

80 views

### Degree of GL(n,C) irreducible representations for Young diagrams with less than r rows

Let $\mathsf Y_{N,r}$ be the set of all Young diagrams with $N$ boxes and no more than $r$ rows. Let $d_y$ be the degree of the irreducible representation of GL(n) corresponding to the Young diagram ...

**4**

votes

**2**answers

102 views

### Cluster Variables for non-convex n-gons

Most of the lectures and lecture notes on Cluster Algebras (at least from Combinatorial point of view) start with mutations of the diagonals of a convex n-gon (mostly the pentagon) as the illustration ...

**1**

vote

**0**answers

54 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 ...

**5**

votes

**0**answers

85 views

### Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...

**3**

votes

**0**answers

65 views

### Number of k-ary monotone maps from 1..n+1 to 1..n+1

[Remark: Last week I asked the same question at math.stackexchange but I have not gotten any answer, so I have thought that there are more chances to get an answer (perhaphs partial) here]
Given ...

**8**

votes

**1**answer

360 views

### Edge chromatic number of hypergraphs

This is question Selection problem in a collection of non-empty sets with a simplification in criterion 3.
Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal ...

**-2**

votes

**2**answers

214 views

### Selection problem in a collection of non-empty sets

Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties?
$a\in {\cal F} \implies |a|\geq 2$,
...

**9**

votes

**1**answer

290 views

### A strengthening of Frankl's union-closed sets conjecture?

A Frankl family is a nonempty finite family $\mathcal F$ of nonempty finite sets such that $A,B\in\mathcal F\implies A\cup B\in\mathcal F.$ Define $d_\mathcal F(x)=|\{A\in\mathcal F:x\in A\}|$ and ...

**5**

votes

**5**answers

213 views

### Locked convex polyhedra

Call a set of polyhedra free if it is possible to rigidly move the polyhedra, without any polyhedron intersecting any other, so that their pairwise distances are arbitrary large, and locked otherwise. ...

**7**

votes

**2**answers

285 views

### Covering the zeros of 0/1 matrix with submatrices

The matrices I am dealing with are $n\times n$ of the following type (with $n=7$):
$M_7=\begin{pmatrix}1&0&0&0&0&0&1 \\ 1&1&0&0&0&0&0 \\ ...

**1**

vote

**1**answer

110 views

### diameter of Cayley graphs

For a group $G$ and an inverse closed subset $S$ of $G\setminus \{1\}$, the Cayley graph $Cay(G,S)$, is the graph whose vertices are the elements of $G$ and two vertices $x$ and $y$ are adjacent if ...

**0**

votes

**0**answers

26 views

### Minimum weight odd cycle with certain edge pairs forbidden

Given a weighted graph $G=(V,E)$ and several disjoint sets $S_1, \dots, S_t
\subset E$ of edges, is there a polynomial-time algorithm to find a minimum
weight odd cycle which does not contain more ...

**2**

votes

**1**answer

158 views

### On a determinantal equality

In my study, I come across the following curious equality, which I do not know a proof yet (so I am asking it here).
Let $k$, $l\in \Bbb Z$ be fixed, $m$ --- the size of the below matrix $M$ --- is ...

**5**

votes

**0**answers

52 views

### convex hull of all-ones principal submatrices

For a subset $S$ of $\{1,\ldots,n\}$,
let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...

**1**

vote

**1**answer

74 views

### 3_partite graphs [closed]

Is there nessesary and sufficient condition for a graph to be 3Partite?
A graph is 2_partite if and only if it has no odd cycles.I know that 3 partite graphs are 3_colorable.is thereanother condition ...

**6**

votes

**1**answer

184 views

### Bounds for maximum determinant of circulant matrices

The Hadamard circulant conjecture states that there do not exist circulant Hadamard matrices with more than $4$ columns.
An $n$ by $n$ Hadamard matrix where the entries are chosen from $\{-1,1\}$ ...

**4**

votes

**2**answers

139 views

### first order languages over graphs (and other discrete models)

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...

**4**

votes

**1**answer

103 views

### What is the best algorithm for even rank magic square?

Magic square is a $n*n$ matrix with numbers of $1,2,...,n^2$ and has the property that sum of any row and any column and sum of main diameter and
adjunct diameter is identical. There exists a very ...

**9**

votes

**0**answers

100 views

### Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...

**1**

vote

**0**answers

29 views

### Generate connected subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the input ...

**14**

votes

**2**answers

220 views

### Generating functions for objects with irrational sizes

A problem I'm investigating concerns a combinatorial class in which the 'atoms' have irrational sizes. It seems likely that this is something that has been considered before, but I haven't been able ...

**6**

votes

**1**answer

201 views

### Are there infinite constructions for partial circulant hadamard matrices?

I believe that the circulant Hadamard conjecture (that there are no circulant Hadamard matrices of size greater than $4\times4$) is still open.
I also know that examples of $(n/2) \times n$ matrices ...

**3**

votes

**1**answer

176 views

### Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed ...

**3**

votes

**1**answer

169 views

### Restricted integer partitions modulo k

Let $p(n,m)$ be the number of partitions of the integer $n$ into exactly $m$ parts. Consider the sequence $a_n = p(n,m)$. What is known about the sequence $a_n$ mod $k$? In particular, is it ...

**-2**

votes

**1**answer

65 views

### Hadwiger partitions where one block is always a singleton

Let $G=(V,E)$ be a simple, undirected graph.
We call a partition ${\cal P}$ of a non-empty subset of $V$ a Hadwiger partition if
every block (member of ${\cal P}$) is non-empty and connected, and
...

**2**

votes

**0**answers

75 views

### Kruskal-Katona for multisets?

Following Fedor Petrov's remarks, here is a "set-theoretic version" of the
question I asked a while ago.
For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite)
multisets with ...

**5**

votes

**1**answer

416 views

### Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices.
Each vertex has exactly 6 neighbors. $P$ is connected ...