**5**

votes

**1**answer

199 views

### A partition of the set of all $n\times n\ (0,1)$-matrices

Let $S_n$ be the set of all the $n\times n\ (0,1)$-matrices and divide $S_n$ into two sets as follows:
$A_n=\{M\in S_n:$ there exist a row and a column of $M$ such that the sum of the row is equal to ...

**2**

votes

**1**answer

118 views

### Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem
(see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...

**0**

votes

**0**answers

77 views

### Reduction from 3-Partition to a cutting problem

My problem is the following:
Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$.
Output: $n$ sets of 3 numbers
Task: Cut the $b_i$'s into $3n$ integers ...

**1**

vote

**0**answers

32 views

### Atomic parts of lexicographic products of vertex-transitive graphs

Suppose $H_1$ and $H_2$ are connected, vertex-transitive graphs, $H_1$ is not the complete graph, and $|V(H_2)| \ge 2$. Then, the lexigraphic product $G=H_1 \circ H_2$ is vertex-transitive, $0 < ...

**11**

votes

**1**answer

400 views

### Generating function for certain partitions (with a restriction on the Durfee square)

First of all my apologies if this question is well known or obvious: this is not in my area of research.
Let $T(x)=\sum_{n=0}^\infty t_nx^n$, where $t_n$ is the number of partitions $\lambda$ of $n$ ...

**1**

vote

**3**answers

121 views

### In what types of graphs can the maximum independent set be found in polynomial time?

I need to find the maximum independent sets of a serial of regular graphs, which is generally NP-complete.
The wikipedia told me that this problem can be solved in polynomial time if the graph is ...

**1**

vote

**1**answer

61 views

### Reduced echelon form of sparce matrices and constructing hash function

Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...

**0**

votes

**0**answers

13 views

### Two-optimality of the Union of a Shortest Hamilton Cycle and a Minimum-weight Maximal Matching

let $G(V,E)$ be a complete, finite, symmetric and simple weighted graph with a unique shortest Hamilton cycle $T_{opt}(G)$ and a unique maximum matching of minimal weight $M_{opt}(G)$.
Is it ...

**8**

votes

**2**answers

231 views

### Asymptotic growth rate of coefficients of generating function

how to calculate the asymptotic growth rate of coefficients generating function $T(z)$ satisfied this identity
$T(z)=z+\frac{T(z)^3}{6}+\frac{T(z^2)T(z)}{2}+\frac{T(z^3)}{3}$

**27**

votes

**7**answers

1k views

### List of proofs where existence through probabilistic method has not been constructivised

Probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object. What are some of the most important objects for which we can show existence but ...

**6**

votes

**0**answers

86 views

### Constant term identity and the Grassmannian Gr(2,6)

The following conjecture is motivated by two different presentations of the affine cone over Grassmannian $Gr(2,6).$ One as a GIT quotient of $Hom(\mathbb{C}^2, \mathbb{C}^6)//SU(2)$ and the other as ...

**13**

votes

**1**answer

359 views

### A combinatorial identity involving generalized harmonic numbers

The $n$-th harmonic number is defined as
$$
H_n=\sum_{k=1}^{n}\frac{1}{k},
$$
and the generalized harmonic numbers are defined by
$$
H_{n}^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}.
$$
Recently, I have found ...

**5**

votes

**4**answers

298 views

### Counting refinements of partitions

Let $p$ and $q$ be partitions of $n$. We say $q$ refines $p$ if the parts of $p$ can be subdivided to produce the parts of $q$. For example, $(5,5,1)$ refines $(6,5)$ but not $(7,4)$. $(n)$ refines ...

**0**

votes

**1**answer

31 views

### Vector version of balanced incomplete block designs

I am interested in finding out what is known about the following generalization of balanced incomplete block designs (BIBDs):
"What is the maximum size of a collection $B$ of $v$-dimensional unit ...

**4**

votes

**1**answer

79 views

### Complexity of this minimization

For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$
where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, ...

**4**

votes

**0**answers

210 views

### The original proof of Szemerédi's Theorem

Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...

**0**

votes

**1**answer

90 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**2**

votes

**1**answer

80 views

### “Hypo” and “Hyper” for Perfect Matching

There is a fairly rich classification on graphs with respect to the existence of Hamiltonian cycles either in unmodified graphs or after certain small modifications.
Do there also exist such ...

**7**

votes

**2**answers

301 views

### Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$?
Are examples of such extremal ...

**0**

votes

**0**answers

43 views

### What is wrong with this isomorphism preserving transformation to a graph of bounded clique width and bounded rank width?

Got an isomorphism preserving transformation to a graph of bounded
clique width and rank width. It, a paper and graphclasses.org imply
graph isomorphism is in P, so likely something is wrong.
Let $G$ ...

**17**

votes

**3**answers

452 views

### Is there a short proof that the Kostka number $K_{\lambda \mu}$ is non-zero whenever $\lambda$ dominates $\mu$?

This is maybe a little basic for MathOverflow, but I'm hoping it will get some interesting answers.
Let $\unrhd$ be the dominance order on partitions of $n \in \mathbb{N}$.
For partitions $\lambda$ ...

**3**

votes

**0**answers

73 views

### Do the classical Laver tables induce periodic systems of jump Laver tables?

Let $A_{n}=(\{1,...,2^{n}\},*_{n})$ where $*_{n}$ is the binary operation on $A_{n}$ such that $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ for $x,y,z\in\{1,...,2^{n}\}$, $x*1=x+1$ for $x<2^{n}$ and ...

**1**

vote

**0**answers

59 views

### Determining finite abelian groups among algebraic theories by counting

Let $T$ be a Lawvere theory (algebraic theory) which contains the theory $T_{\mathrm{grp}}$ of groups as a subtheory (so that $T$ has, in general, more equations that $T_\mathrm{grp}$).
Suppose ...

**7**

votes

**0**answers

70 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ ...

**5**

votes

**0**answers

105 views

### Nonclassical polynomials, circles, and groups

Tao and Ziegler have introduced a generalization of polynomials over a prime field called nonclassical polynomials, useful for studying the Gowers norm.
A nonclassical polynomial of degree $d$ is a ...

**2**

votes

**0**answers

32 views

### Does conjugate Bailey pair have conjugate Bailey lemma like Bailey pair have Bailey lemma?

Motivation of my question: Does conjugate Bailey pair have conjugate Bailey lemma like Bailey pair have Bailey lemma?

**4**

votes

**1**answer

113 views

### does every vertex-cut set in a maximal planar graph contain a cycle?

$G = (V, E)$ is a 3-connected plane triangulation. Let $S \subset V$ such that $G(V - S)$ is disconnected. Is it true that $G(S)$ must contains a separating cycle?
My intuition is leading me to ...

**1**

vote

**0**answers

74 views

### Number of increasing integer sequences which may be sides of a convex $k$-gon [closed]

We need to find the total number of sequences $(x_1,\dots,x_k)$, $x_1<\dots<x_k$, $x_i\in \{1,\dots,N\}$, such that $x_1+\dots+x_{k-1}>x_k$.

**16**

votes

**14**answers

1k views

### Applications of Representation Theory in Combinatorics

What are the examples of interesting combinatorial identities (e.g. bijection between two sets of combinatorial objects) that can be proved using representation theory, or has some representation ...

**1**

vote

**1**answer

103 views

### $q$-connectedness of random digraphs obtained from a fixed graph

Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).
Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...

**6**

votes

**1**answer

174 views

### Exotic line arrangements

I would like to discuss about the following problem. Hopefully, you will suggest me some ideas and bibliography.
At first I provide some basic definitions to set up the notation.
Let us consider a ...

**4**

votes

**0**answers

76 views

### Kruskal-Katona for homocyclic groups?

I need a version of the Kruskal-Katona theorem (better still, of the Lovasz "approximate" version thereof) for the elementary abelian / homocyclic groups, in the following spirit:
What is the ...

**0**

votes

**1**answer

57 views

### Finding maximal sets of words at minimum distance

Given an alphabet $Q$ with $k$ letters, consider the set $W(n, k)$ of all words in $Q$ with exactly $n$ letters.
In $W(n, k)$ we can define a distance by $dist(x,y) = \#\{ \text{Places where $x$ and ...

**4**

votes

**0**answers

75 views

### Face structures of chain polytopes

For a finite poset $P$ the chain polytope $\mathscr C(P)\subset\mathbb{R}^P$ consists of such $g$ that $g(p)\ge 0$ for all $p\in P$ and $$g(p_1)+\ldots+g(p_n)\le 1$$ for any chain ...

**3**

votes

**2**answers

182 views

### Counting Specific Permutations of Elements in a Multiset

I have a question regarding counting permutations of a multiset's elements. The problem is the following:
Given a multi-set $M=\{0^{m}, 1^{n-m}\}$ the number of all possible permutations of its ...

**4**

votes

**0**answers

57 views

### Kostka polynomials in root systems other than A

The q, t - Kostka polynomials $K_{\lambda\mu}(q, t)$ are defined as follows (all notations I do not explain here come from the classical book by Macdonald: Symmetric Functions and Hall polynomials, ...

**2**

votes

**2**answers

100 views

### On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$

Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.
It is clear ...

**10**

votes

**1**answer

215 views

### Optimization of points on a plane

Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...

**3**

votes

**2**answers

120 views

### f vectors of simplicial complexes homeomorphic to n dimensional spheres

In dimension 2, the euler poincare formula restricts the incidence properties of edges in a triangulation of a surface.
Are there analogous generalizations for higher dimensions, like elaborations ...

**1**

vote

**0**answers

156 views

### Concrete solution to the (oriented) Oberwolfach problem with one table

I asked the following on MSE, but it received little attention...
The oriented Oberwolfach problem (with only one table) and its solution are the following.
In a meeting of $n$ people during $n-1$ ...

**2**

votes

**1**answer

54 views

### l-wise t-intersecting families of shifts of finite sets of integers

Let $A$ be a finite set of non-negative integers and write $I_k$ for the set ${0,1,\ldots,k-1}$. Form all possible l-wise intersections $(A+k_1)\cap \ldots \cap (A+k_l)$, where each $k_i$ runs through ...

**3**

votes

**2**answers

100 views

### Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ ...

**0**

votes

**0**answers

93 views

### On number of disjoint sets with small stack depth in a set of permutations

Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is ...

**2**

votes

**0**answers

107 views

### Is there an odd number which has no prime to prime matchings when compared with its reverse order? [closed]

For example look at the number 9. It has prime-prime matching at 3,5, and 7.
For example the sequence of 13 has matchings at 1,3,7,11,13.
For example 15 has the matchings(crossings) at 3,5,11,13.
...

**3**

votes

**1**answer

214 views

### Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...

**2**

votes

**1**answer

89 views

### Intersections of translates of finite sets of integers

I am searching for a result in the literature that I am sure must be known, but I just fail to find it.
Let us starts with a simple example:
Let $A, B\subset \mathbb{Z}$ be a finite sets of integers ...

**4**

votes

**1**answer

251 views

### Problem related to Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if,
for any ...

**3**

votes

**1**answer

545 views

### A generalized theorem of Hall's marriage theorem

We all know Hall's marriage theorem as following:
A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.
And I am ...

**0**

votes

**1**answer

83 views

### Maximal induced cycles on $n$-clique graphs

For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$.
We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such ...

**1**

vote

**0**answers

74 views

### Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...