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)

0
votes
1answer
27 views

Combinatorial polynomials from general diagram fillings?

There is a plethora of polynomials defined on partition shaped Young diagrams, (Schur, Jack, Grothendieck,...), and skew Young diagrams. There are also composition shaped diagrams that are responsible ...
0
votes
0answers
21 views

Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph. It is known that every vertex transitive graph on $n$ vertices has vertex cover of size $\Omega(n)$. It is also not ...
5
votes
1answer
122 views

Dimension of the span of all partial derivatives of a given symmetric polynomial $f$ and the polynomial $E(f)$

I need some help on the problem below. Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set $$ ...
2
votes
0answers
210 views

How is $ \sum_{x \in X(\mathbb{F}_q)} \dots $ a generalization of cardinality?

This quarter Maxim Kontsevich is offering a course on exponential integral. There is not much in the way of notes, but is one page with mysterious comments. Let $X$ be an algebraic variety over ...
0
votes
0answers
39 views

Uncountability of the set of subsets of $\mathbb N$ [migrated]

Denote by $\mathbb{N}$ the set of natural numbers and by $2^{\mathbb N}$ the set of all subsets of $\mathbb N$. Let $E$ be some subset of $2^{\mathbb N}$ such that for every pair of elements in $E$, ...
2
votes
0answers
70 views

scalar multiple of Young symmetrizer

The following is a lemma from Fulton and Harris' book -Representation theory,a first course (page 53): Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar ...
4
votes
2answers
117 views

Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is $$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...
4
votes
0answers
27 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
1
vote
1answer
116 views

Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
1
vote
0answers
114 views

Largest Fourier coefficient of sparse boolean function

Consider a Boolean function $f: GF(2)^n \rightarrow \{0, 1 \}$. I would like to show that if $f$ is sparse, i.e. $\sum f(i) \leq t$, then $f$ must have a large Fourier coefficient. (A Fourier ...
8
votes
2answers
142 views

Extending subsets to supersets in different ways

We are given a collection of sets $A_1,\ldots,A_s$, pairwise different and each of cardinality $k$, and a collection of sets $B_1,\ldots,B_s$, pairwise different and each of cardinality $l>k+1$, ...
4
votes
1answer
133 views

Graph of graph homomorphisms

For (finite or infinite) undirected, simple graphs $G, H$, let $V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and $E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: ...
3
votes
1answer
141 views

Seymour's second neighborhood conjecture

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.
1
vote
0answers
34 views

Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...
5
votes
1answer
90 views

Algorithm that generates minimum n-simplex that cover n-cube?

Given an $n$-cube with unit volume, is there any algorithm that generates a minimum volume $n$-simplex that covers the $n$-cube?
2
votes
0answers
40 views

Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.) For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...
-1
votes
0answers
57 views

Sum of the k+l \choose l [closed]

I am tring to prove the following equality : $\displaystyle \sum_{k=0}^n {k+l \choose l} = {n+l+1 \choose l+1} $ However, I did not manage to find a proof... Do you have any ideas ? Thanks !
4
votes
0answers
84 views

Integer decomposition of dilated integral polytopes

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$. Question: Given $d > n + 2$ is it true that $$ ...
5
votes
0answers
90 views

A generalization of Erdős–Newman–Mirsky?

Given a sequence $S$ of natural numbers, write ${\bf Gap}(S)$ for the set of differences between consecutive terms. (So $|{\bf Gap}(S)|=1$ precisely for arithmetic progressions, hence the connection ...
0
votes
0answers
55 views

How can a binomial coefficient can be approximated by using Striling's formula? [closed]

I've met some difficulties with such question: How can we approximate a binomial coefficient by using a Stirling's factorial approximation. I've evaluate a little bit and got this How can I ...
25
votes
1answer
902 views

Combinatorics of K(Z,2)?

Anybody knows a semi-simplicial model for $K(Z,2)$ having finite number of simplexes in any dimension? With some regular description? I have heard about big activity on triangulating $CP^n$ but this ...
1
vote
0answers
28 views

Lattice-isotopic essentialization of arrangements

I'm working on a problem related to $\textbf{Randell's isotopy theorem}$ for complex hyperplane arrangements. I have a question which seems quite obvious. However, I haven't found a rigorous proof ...
6
votes
2answers
160 views

Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks). I will be thankful for answers ...
-3
votes
0answers
58 views

prove that the sequence a_n = [n((2)^(1/2))] + [n((3)^(1/2))] contains infinitely many even and odd integers [closed]

im not sure how to proceed.i have done a few problems similar to this but i can't solve this one. thanks for any help.( by the way this is a problem from croatia team selection test )
3
votes
1answer
103 views

An upper bound on the number of sets of parallel lines covering points in a finite plane?

Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a ...
83
votes
7answers
3k views

Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$? My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
12
votes
2answers
659 views

Mysterious identity between numbers of odd/even meander systems

Definitions: An upper arch system of order $n$ is a subset of the plane consisting of $n$ non-intersecting closed semicircles in the upper half-plane whose endpoints belong to the set $\{(k,0)\mid ...
12
votes
2answers
624 views

A combinatorial question about orthonormal bases

Suppose that $F:S^{n-1}\to A$ is a map of sets from the unit sphere in $\mathbb R^n$ to an abelian group, and that the sum $F(v_1)+\dots +F(v_n)$ over an orthonormal basis is independent of the basis. ...
14
votes
0answers
173 views

Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed. Say that a coloring of the dots of a Ferrers ...
4
votes
0answers
116 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
2
votes
2answers
260 views

Local coordinates on (infinite dimensional) Lie groups, factorization of Riemann zeta functions

Given a (finite dimensional) Lie group $G$ (real $k=\mathbb{R}$ or complex $k=\mathbb{C}$) and its Lie algebra $\mathfrak{g}$, one can prove (a basis $B=(b_i)_{1\leq i\leq n}$ of $\mathfrak{g}$ being ...
3
votes
1answer
130 views

A question of terminology regarding integer partitions

I am wondering if there is a standard notation and name for the following. Let $\lambda$ be a partition $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_r\geq 1$ of $n$ into $r$ parts. Then we can ...
3
votes
1answer
115 views

Regarding left-to-right minima

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is ...
19
votes
2answers
1k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
4
votes
2answers
156 views

Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community. Setup: Let ...
7
votes
0answers
107 views

Some $q-$analogues of $ \sum\limits_{j = - k}^k {{{( - 1)}^{ j}}}\binom{n}{k-j}\binom{n}{k+j}=\binom{n}{k}.$

Let ${\left( {a;q} \right)_n}=\prod\limits_{j = 0}^{n - 1} {(1-{q^j}a} )$ and let $ {{n}\brack{k}}_q$ denote a $q-$binomial coefficient. I am interested in $q-$analogues of the identity $ ...
1
vote
1answer
74 views

Balls from bin with replacement, distinct elements, concentration inequality

Draw $n$ numbers, denoted by $a_1, a_2, \ldots, a_n$, from set $[n]$, that is, for each $i$, $a_i$ is a uniformly random number from $[n]$. Let $A = \{a_1, a_2, \ldots, a_n\}$. Then $$ ...
5
votes
0answers
84 views

The Maximum Number of Lines Contained in the Point Set of a Finite Projective Plane

Consider a finite projective plane of order $q$. Define $f(m)$ to be the maximum number of lines completely contained in any point set of size $m$, where $1 \leq m \leq q^2+q+1$. I would like to ...
7
votes
1answer
144 views

Determinant of a checkerboard Hankel matrix with Catalan numbers

My goal is to compute \begin{equation} I = \det \left(\mathbf{I} + \mathbf{A}\right) \end{equation} where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers: $$ \left\{ ...
3
votes
0answers
87 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
15
votes
1answer
833 views

Evaluating a remarkable term for primes p = 5 (mod. 8)

Let $p > 3$ be a prime number, and $\zeta$ be a primitive $p$-th root of unity. I am interested in knowing the exact value of $$w_p = \prod_{a \in (\mathbb F_p^{\times})^2}(1 + \zeta^a) + \prod_{b ...
11
votes
2answers
451 views

“The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects. ...
2
votes
0answers
55 views

Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $ \lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...
3
votes
0answers
118 views

A Result of Anders Bjorner: Matchings in countably infinite geometric lattices of finite height

Let $L$ be a countably infinite geometric lattice of finite height $r\ge3$. (A geometric lattice of height $r$ is an atomistic semimodular lattice such that every maximal chain has $r+1$ elements.) ...
28
votes
1answer
1k views

“The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler. Two sheriffs in neighboring towns are on the track of a killer, in a case involving eight ...
4
votes
2answers
153 views

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...
7
votes
2answers
159 views

Decomposition of a cross-polytope into simplices

Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...
4
votes
1answer
190 views

Young tableau with no i in row i, name that derangement

This question has its genesis in a group assignment: $k$ students are to be given oral exams. Each student will be asked one distinct question from $n$ questions given to them earlier, no two students ...
6
votes
2answers
104 views

Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$. ...
3
votes
1answer
139 views

Identify ring of polynomials symmetric under forgetting variables

I came across the following ring $A$, which appears as a Chow ring. I am wondering if it has been studied before; in particular, I am looking for a reference where this object might have been ...