**5**

votes

**2**answers

242 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**0**

votes

**1**answer

78 views

### Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to:
I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...

**1**

vote

**1**answer

138 views

### Is there a “Bipartite” Szemeredi-Trotter theorem?

One version of the Szemeredi-Trotter theorem states the following:
Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k ...

**0**

votes

**1**answer

42 views

### average number of cycles and closed walks length k in incomplete directed graph

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.
Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple ...

**11**

votes

**1**answer

658 views

### Szemeredi's theorem in the Gaussian integers

Suppose that $S\subseteq\mathbb{Z}[i]$ has the following properties:
For convenience, let $A_n = \{z : z\in\mathbb{Z}[i], \text{Nm}(z)\le n\}$
$$\limsup_{n\rightarrow\infty} \frac{|S\cap ...

**10**

votes

**3**answers

716 views

### What exact number of domino tilings cannot be realizable?

Inspired by some other questions, (this and this),
I wonder what numbers $n$ there are that satisfy
$$p(n)=\text{there is no region that admits exactly } n \text{ domino tilings}.$$
If this is true, ...

**1**

vote

**0**answers

96 views

### Representation of Permutation group: What is the isormorphism between the equivalent descriptions, (1)using schur functions and (2)abstract tensors

I assume that the two ways of describing the representation of the permutation group using abstract tensors (perhaps more naive but widely used in physics) and schur functions are equivalent. If ...

**35**

votes

**1**answer

870 views

### Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...

**6**

votes

**1**answer

243 views

### A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...

**4**

votes

**3**answers

197 views

### Can anyone suggest a text on polyhedral theory?

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes

**13**

votes

**1**answer

467 views

### When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...

**6**

votes

**3**answers

774 views

### A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...

**2**

votes

**0**answers

47 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

47 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**2**

votes

**3**answers

262 views

### Is the reduced plethysm (restricted to 2-columns in Young tableaux) of this Schur funtion known $\mathbb S_{3^1}(\mathbb S_{1^p})$?

I am working on a physical problem, where I need to compute the "reduced plethysm" that is all the irreducibles characterised by the Young tableaux of 2 columns or less. The plethysm problem I want to ...

**2**

votes

**1**answer

156 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**0**

votes

**0**answers

46 views

### Calculating the longest Bracelet(s) Common to a Set of Bracelets

I would like to know, if the following problems has been studied before:
let $\{B_1, ..., B_n\}$ be a set of Bracelets with the same set $\{\beta_1, ..., \beta_k\}$ of beads,
what is the ...

**6**

votes

**2**answers

201 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**6**

votes

**1**answer

273 views

### About an identity which gives immediate proof of the permanent lemma

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...

**4**

votes

**0**answers

133 views

### Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in ...

**0**

votes

**1**answer

288 views

### Basketball shots and stopping rule

Moved over from StackExchange.
You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...

**0**

votes

**0**answers

70 views

### asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...

**5**

votes

**1**answer

178 views

### Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...

**5**

votes

**0**answers

92 views

### Subplanes of Finite Projective Planes

If a finite projective plane $\pi_1$ of order $m$ contains, as a sub plane, a
finite projective plane $\pi_2$ of order $n$, then $m \geq n^2$ with equality holding only in the case of a Baer sub ...

**2**

votes

**1**answer

143 views

### Covering by subsets

There is set $A$ with cardinality $2^n$. For every $x \in A$ there is $A_x$ - subset of $A$ with cardinality $2^m$, $x \in A_x$. $M=\{A_x|x \in A \}$. Are there $B \subset A$ with cardinality $\ge ...

**11**

votes

**0**answers

376 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**0**

votes

**0**answers

118 views

### a question on sum of Gaussian binomial coefficients

I was trying to calculate something and at some point I get the following sum:
\begin{equation}
\sum_{t=0,t \text{ even}}^{s}{s+3n \brack s-t}\sum_{i = 0}^{t/2}q^{2i^2}{t/2+2n-i \brack t/2-i}{n ...

**0**

votes

**0**answers

57 views

### How many edges are in the kth-iterated common neighborhood knight's graph?

For terminology see https://www.academia.edu/2180382/The_Common_Neighborhood_Graph_and_Its_Energy)
It has been known for quite some time by players that a vertex whose corresponding square is in the ...

**7**

votes

**3**answers

681 views

### A conjecture about the entropy of matrix vector products

Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...

**6**

votes

**0**answers

69 views

### Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?
In ...

**7**

votes

**2**answers

264 views

### What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...

**0**

votes

**1**answer

117 views

### Maximize combinatorial sum for boolean function

I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...

**5**

votes

**1**answer

129 views

### Graphs where each edge belongs to the same number of 1-factors

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of ...

**2**

votes

**0**answers

42 views

### Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$.
The configuration space of Tverberg's theorem is the simplicial complex ...

**1**

vote

**0**answers

171 views

### Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1].
Is there a known tight upper bound in the number of polytopes in ...

**1**

vote

**2**answers

136 views

### Identity involving shifted Legendre coefficients

For small values of $n$ ($2\leqslant n\leqslant 5$), the coefficients $a_k = (-1)^k{n\choose k}{n+k\choose k}$ of the shifted Legendre polynomial $\tilde{P}_n(x)$ satisfy the identity ...

**1**

vote

**0**answers

108 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...

**4**

votes

**1**answer

229 views

### Non-vanishing of elements in cohomology of full Flag varieties

Consider the full flag variety $F_n$ consisting of full flags in $\mathbb C^n$. There is a collection of tautological bundles on $F_n$:
$0=U_0\subset U_1\subset ...\subset U_{n-1}\subset U_n=\mathbb ...

**11**

votes

**0**answers

344 views

### Erdos multiplication problem revisited

The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further ...

**3**

votes

**3**answers

300 views

### How to find an integer set, s.t. the sums of at most 3 elements are all distinct?

How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different.
Example with $|A|=3$: Out of the set $A ...

**1**

vote

**1**answer

120 views

### Vertex transitive and edge transitive and line graph

How can we find the proof of the following statement:
An undirected graph is edge transitive if and only if its line graph is vertex transitive.

**5**

votes

**3**answers

463 views

### Is the Manickam-Miklós-Singhi Conjecture solved?

This arXiv paper is claimed to contain a proof for the MMS conjecture. But it seems that this manuscript is not yet peer reviewed by other mathematicians. I personally tried to follow the paper, but ...

**7**

votes

**1**answer

198 views

### Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols,
and $p$ a pattern.
An example of a pattern is $p=XX$, where $X$ is any finite
string of symbols from $A^+$.
Avoiding $p$ is avoiding any subword repeated twice ...

**3**

votes

**2**answers

250 views

### Magic squares with specific properties

For what $n \geq 3$ does there exist an $n \times n$ matrix such that:
All entries are in $(0, 1)$.
Each row and column sums to $1$.
Aside from the rows and columns, no other subsets of the entries ...

**9**

votes

**3**answers

409 views

### Combinatorial interpretation of composition of power series?

This is a minor curiosity that came up in a joint project recently.
Consider the sequence $a_n=3\frac {(2n)!}{(n+2)!(n-1)!}$ (A000245 in OEIS).
It has multiple combinatorial descriptions.
One can ...

**3**

votes

**5**answers

255 views

### Given A set $U$ and a set $\mathcal O$ of subsets of $U$, how many subsets of $\mathcal O$ have union $U$?

Let $U$ be a finite set and $\mathcal O$ a set of subsets of $U$, how many subsets $\mathcal S$ of $\mathcal O$ satisfy the union of the elements of $\mathcal S$ is equal to $U$?
I think the problem ...

**13**

votes

**0**answers

469 views

### What's the big deal about $M_{13}$?

$M_{13}$ is the Mathieu groupoid defined by Conway in
Conway, J. H. $M_{13}$. Surveys in combinatorics, 1997 (London), 1–11,
London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, ...

**2**

votes

**0**answers

62 views

### Reference for MacMahon on Overpartitions

In the literature on overpartitions Percy A. MacMahon is usally cited as the genesis of the theory. Often the reference is to his 1916 textbook -- but, having recently checked this out of my school's ...

**5**

votes

**1**answer

208 views

### Continued fraction expansion of an algebraic number and its conjugates

Let $w$ be an element of a Galois extension $L:\mathbb{Q}$ such that $\text{Gal}(L/\mathbb{Q})=\langle g\rangle$ is cyclic of order $n$ (here $\mathbb{Q}$ is rationals). Suppose we know the continued ...

**1**

vote

**1**answer

190 views

### A problem in symbolic dynamics

I got a fun problem.
Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$
...