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)

2
votes
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
5answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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 ...