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)

4
votes
1answer
217 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 ...
3
votes
0answers
91 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
0answers
146 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
0answers
46 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 ...
3
votes
0answers
110 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) ...
3
votes
0answers
61 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
1answer
135 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 ...
10
votes
0answers
339 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
0answers
109 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 ...
5
votes
3answers
345 views
+50

A conjecture about the entropy of matrix vector products

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
5
votes
0answers
55 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 ...
6
votes
2answers
182 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
1answer
81 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
1answer
119 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
0answers
35 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
0answers
131 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
2answers
126 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
0answers
97 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
1answer
224 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 ...
10
votes
0answers
324 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
3answers
282 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
1answer
104 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
1answer
326 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 ...
6
votes
1answer
184 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
2answers
241 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
3answers
395 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
5answers
251 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
0answers
451 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
0answers
56 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 ...
4
votes
1answer
196 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
1answer
180 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}.$ ...
23
votes
2answers
484 views

Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
5
votes
2answers
239 views

Balls and bins with color

Say I have $n$ balls each of $k$ different colors (i.e. $nk$ balls altogether), and I throw these balls independently into $N$ bins. Is there anything that can be said (in expectation, limits with ...
2
votes
1answer
132 views

counting the number of ordered pairs in a permutohedron

Recall that a permutohedron is a graph on the set of permutations $S_n$ with an edge between $\sigma$ and $\tau$ if they differ by one adjacent transposition: $\tau = (i,i+1) \circ \sigma$ for some $i ...
1
vote
2answers
260 views

Mixed integer programming formulation for Ising model

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...
0
votes
0answers
38 views

Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs. What is the complexity of graph isomorphism in $(P_4 ...
0
votes
1answer
82 views

An upper bound on families of subsets with a small pairwise intersection

Given integers $ n,r,s $, we can define $M(n,r,s)$ to be the maximal size of a family $F$ of $r$-subsets of $\{1,...,n\}$ such that the pairwise intersection between any two subsets is at most $s$. Is ...
5
votes
2answers
157 views

What is known about tiling a rectangle in an irreducible way by smaller rectangles?

Given two naturals $s<t$. Is there always a square (or at least a bigger rectangle) that can be tiled with $s\times t$ rectangles in an irreducible way (i.e. any grid line splitting it cuts at ...
3
votes
1answer
97 views

Graph transformation related to graph isomorphism

Basically got graph transformation related to graph isomorphism. Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$. ...
6
votes
1answer
169 views

Subset of $F_2^n$ that must contain some subspace of dimension $k$

This question has practical meanings in algebraic attack of stream ciphers in cryptography. It can be stated as follows: Suppose $V$ is a $n$ dimensional vector space over the field $F_2$, where ...
15
votes
0answers
312 views

Spencer's “six standard deviations” theorem - better constants?

This question is about Joel Spencer's famous "six standard deviations" theorem. The theorem says that when $$ L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{in} x_n, \quad 1 \leq i \leq n, $$ are $n$ ...
1
vote
0answers
151 views

Number of Orbits of symmetric group acting on $(\mathbb{Z}/n)^{l}$ [migrated]

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
2
votes
1answer
166 views

A parametrization of subsets

Suppose $I\subseteq\{1,\dots,n\}$, and let $\{1,\dots,n\}\setminus I=\{j_1,\dots,j_m\}$ be an enumeration of the complement of $I$ with $j_r<j_{r+1}$ for each $r\in\{1,\dots,m-1\}$. To $I$ I can ...
2
votes
2answers
218 views

Finding the set of all $0-1$ vectors in an affine subspace

We are given a $0-1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0-1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) ...
4
votes
1answer
167 views

Is the monoid of taking iterated images and inverse images freely generated by the image and inverse image operation?

Let $\mathcal{F}$ denote the class of all functions. Let $U,L:\mathcal{F}\rightarrow\mathcal{F}$ denote the mappings where if $f:X\rightarrow Y$, then $U(f):P(X)\rightarrow P(Y),L(f):P(Y)\rightarrow ...
1
vote
0answers
31 views

Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances

To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view. Examples are: the diagonals of the convex hull of a set of points in the euclidean plane; ...
11
votes
2answers
359 views

how to find cubic polynomial that an unknown subset of a set of integers satisfies

I have a set, $S$, of positive integers and I have reason to believe that some infinite subset of them may be parametrized by a cubic polynomial with integer coefficients evaluated at integer ...
4
votes
1answer
60 views

Is it true that every hypergraph with a large “semi-shattered” set has large VC dimension?

Given a hypergraph $H=(V,E)$ and a set $X\subseteq V$ of vertices, let $int(X)$ be the number of distinct intersections of edges with $X$, i.e. $$int(X)=|\{S\subseteq X, \exists e\in E, e\cap ...
4
votes
1answer
121 views

Transalate of a Richardson Variety

For $v \leq w$ are Weyl group elements, the intersection of a Schubert variety $X^w$ and the opposite Schubert variety $X_v$ is called a Richardson variety. It is denoted by $X_v^w$. It is well know ...
0
votes
1answer
202 views

two correlated processes

I apologize if this question is not placed in the right place. But I am having a hard time to figure it out. It would be greatly appreciated if some one could help me out. Assume that there are two ...