3
votes
1answer
70 views

Extremal graph theory for directed graphs

In extremal graph theory, there are results such as $$t(C_4,G)\geq t(K_2,G)^4,$$ where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...
3
votes
0answers
42 views

Reference for Frobenius’s proof of Schur’s finite version of the Rogers - Ramanujan identities

In his paper “Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche” I. Schur has stated that Frobenius has communicated to him a simple direct proof of his finite version of the ...
1
vote
0answers
51 views

Bases of a matroid such that their complement is an independent set

Let $M$ be some matroid on $[n]$ with set of bases $\mathcal{B}$. I am interested in the subset $\mathcal{B}' \subseteq \mathcal{B}$ of bases $b \in \mathcal{B}$ with the property that $[n] \setminus ...
4
votes
1answer
95 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
5
votes
1answer
99 views

References to proofs of a theorem by Van Kampen-Flores

Theorem (Van Kampen-Flores 1930s) From any 7 points in four-dimensional space one can choose two disjoint triples such that the triangles with vertices at the triples intersect each other. This ...
1
vote
0answers
150 views

An extrasensory perception strategy :-)

I asked this question at MSE some months ago but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
4
votes
0answers
61 views

Reference for statement that almost every $n$-element partial order has trivial automorphism group

I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...
5
votes
0answers
64 views

Classifying two-faces of four-polytopes

Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to ...
3
votes
1answer
219 views

Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS. It doesn't appear at this time. I can't find any reference to it either. Has anyone seen it? ...
16
votes
3answers
2k views

Silly me & Van der Waerden conjecture

So I walked into this very innocent-looking combinatorics problem, and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent. Now ...
4
votes
1answer
178 views

Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate. Is the Van der Waerden's function itself elementary in the sense of Kalmar?
3
votes
3answers
320 views

Estimating a sum involving binomial coefficients [refined]

Having some work done, here is a refined version of my initial question. For integer $m>0$ and $0\le q\le m$, consider the sum $$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$ I ...
6
votes
1answer
149 views

What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on $$ \sum_{i=1}^{n}{d_{i}^{2}}. $$ An example is de Caen's bound: $$ \sum_{i=1}^{n}{d_{i}^{2}} \leq ...
6
votes
0answers
106 views

What is the mobius function for the set of simplicial complexes on n vertices?

Consider the set of simplicial complexes on $n$ vertices, with partial ordering by containment. What is the Mobius function for this poset? Are other combinatorial facts known about it (e.g. the ...
1
vote
1answer
196 views

Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$. Consider the following parameter: $\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$ Has this parameter been studied? ...
8
votes
2answers
577 views

How to find counterfeit coins by weighing

In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. ...
6
votes
1answer
95 views

Maximizing ratio volume/diameter^n by an affinity

Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$. It is clear that there is a constant ...
1
vote
0answers
41 views

complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference. Thanks for any answer!
2
votes
2answers
125 views

Name for Kneser/Johnson-like graphs?

I wonder if the following simple generalization of Johnson and Kneser graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the set of $k$-element subsets of an $n$-set, with two $k$-sets ...
6
votes
1answer
499 views

“MultiCatalan numbers”

Could anyone provide a reference for the following (sort of) generalization of Catalan numbers: the multinomial coefficient $$ \binom{2k_1+3k_2+4k_3+...}{k_1+2k_2+3k_3+...,k_1,k_2,k_3,...} $$ is ...
3
votes
1answer
248 views

Geometric van der waerden theorem

Van der Waerden theorem states that sufficiently long initial segment of the natural numbers when divided into $r$ parts contains an arithmetic progression of length $k$. The length of the initial ...
11
votes
7answers
420 views

Does the notion of graphs with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have. It is actually a way to write in a ...
23
votes
4answers
928 views

Multiplying by irrational numbers in combinatorial problems

This is getting no attention on stackexchange. Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$. It had escaped my attention until last week, ...
7
votes
2answers
336 views

Overlapping sets

Consider the following problem: Let $F \subseteq 2^{I}$ be a finite family of finite subsets of some index set $I.$ Let $F_x$ be defined as the number of elements of $F$ that contains $x.$ Assume ...
12
votes
2answers
398 views

Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite? If the answer is yes, can ...
3
votes
1answer
102 views

Multipartite Ramsey theorem

Given $c<\infty$ colors, positive integers $k_1,\dots,k_n$ and positive integers $N_1,\dots,N_n$. Then there exist positive integers $M_1,\dots,M_n$ so that for disjoint finite sets $A_1,\dots,A_n$ ...
7
votes
1answer
285 views

Chromatic number of induced subgraphs as upper bound to the chromatic number

Motivation: At the Erdős100 conference in Budapest András Gyárfás presented some interesting conjectures. One of them was the following: Given that in a graph $G$, every subgraph $H$ formed by ...
2
votes
0answers
136 views

Schemes defined by a collection of Plücker coordinates

If $C \subset {[n]\choose k}$ is any collection of $k$-element sets, we can define a scheme $$ W(C) = \bigcap_{S\notin C} \{V \in Gr(k,n) : p_S(V)=0\} \qquad \subseteq Gr(k,n), $$ where $p_S$ is the ...
5
votes
0answers
175 views

Asymptotics of a Splitting Process

Consider $p(n)$ defined recursively by $p(1)=1$ and $\displaystyle p(n)=\frac{1}{(n-1)^n}\sum_{i=1}^{n-1}\left\{\sum_{j=i}^{n-1}(-1)^{j-i}{n \choose j}{j\choose i}(n-j)^j(n-j-1)^{n-j}\right\}p(i)$. ...
1
vote
2answers
208 views

Flips on standard Young tableaux and descent sets

Consider $T$ to be a standard Young tableau of shape $\lambda$ (in English notation). The descent set of $T$, $Des(T)$, is defined to the set of all positive integers $i$ such that $i+1$ lies strictly ...
2
votes
3answers
135 views

Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
3
votes
1answer
99 views

For what classes of comparability graphs are their complements also comparability graphs?

An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...
4
votes
3answers
228 views

multiply transitive groups

It seems to be well-known that the six-transitive finite groups are the symmetric and alternating groups, and the only other four-transitive finite groups are the Mathieu groups (the statement can be ...
4
votes
0answers
166 views

Permutations with all cycles odd

I have recently needed to compute the number of permutations in $S_n$ with all cycles odd, and while this is easy using Flajolet-Sedgewick theory (the exponential generating function seems to be ...
4
votes
0answers
176 views

Balls and bins — concentration bounds pertaining to the minimal load bin

Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
4
votes
2answers
156 views

Better bounds for exact-intersection Erdős–Ko–Rado system?

What is the largest possible number of subsets of a $4n$-element set $X$, such that each subset contains precisely $2n$ elements, and such that each of the pairwise intersections of the subsets has ...
6
votes
2answers
442 views

Why are negative sets multisets? (Reference request)

It is easy to establish that $$ \left({n\choose k}\right)=(-1)^k{-n \choose k}, $$ where the symbol on the left-hand-side counts the number of multisets of $k$ elements from $n$. On the Wikipedia ...
6
votes
1answer
258 views

The number of lattice paths below y=n/m x for gcd(m,n) = 1

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams http://arxiv.org/abs/1305.7286 on rational Catalan combinatorics. An important starting point of this paper is ...
4
votes
1answer
133 views

Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...
5
votes
2answers
233 views

Fractional chromatic number, find reference to a particular alternate definition for

I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs. Let me review the most common definition and basic properties first. Let $ G $ be ...
10
votes
2answers
274 views

Temperley-Lieb algebras for other Weyl groups?

The Temperley-Lieb algebra has the same generators as the $S_n$ group algebra, and the same commuting relations, but its other relations are different. A nice diagrammatic interpretation can be seen ...
8
votes
2answers
208 views

An operation on binary strings

Consider the “product” $\gamma = \alpha \times \beta$ of two binary strings $\alpha$, $\beta$ $\in \lbrace 0,1\rbrace^+$ which one gets by replacing every 1 in $\beta$ by $\alpha$ and each ...
8
votes
0answers
170 views

A duality on partial permutations

A partial permutation matrix $\pi$ is one with at most one 1 in any row and column (the rest 0s). Given one, we can cross out to the East and South (but not Southeast) of each 1. Some boxes get ...
8
votes
0answers
389 views

Reference/quote request: “All of combinatorics is the representation theory of $S_n$”

I think I remember reading somewhere a glib (or is it deep?) quote, perhaps due to Rota?, which was something like "All of combinatorics is essentially [or can be reduced to?] the representation ...
10
votes
2answers
465 views

Who constructed the projective plane of order $4$ from $K_6$?

I have been trying to hunt down the original reference for the construction of the projective plane of order $4$ from the complete graph on $6$ vertices. The reference I have at hand are Cameron and ...
1
vote
0answers
75 views

Generating series of free PROs

Let \begin{equation} G := \biguplus_{p \geq 0} \: \biguplus_{q \geq 0} G(p, q) \end{equation} be a bigraded set of generators and $\mathcal{F}(G)$ be the free PRO generated by $G$ (see [1] for a net ...
6
votes
0answers
121 views

“Double convolution” with the Mobius function on a poset

Let $f$ and $g$ be arbitrary (say integer-valued) functions on some poset $P$, and say $\mu$ is the Mobius function of $P$. I'm studying a quantity that's a sort of "double convolution" of $f$ and $g$ ...
4
votes
0answers
117 views

Reference request: enumeration under group action

Is there a reference for the following lemma (which is useful in counting unlabeled k-trees)? It seems to me that it should be known, but I haven't been able to find it anywhere. Let $G$ be a finite ...
11
votes
0answers
317 views

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...
3
votes
2answers
225 views

Formalization (and background) of a formula, concering the integral points of a polygon.

I have recently become aware of the following neat statement. Consider a convex polygon $P$ in the real plane with integral vertices. If we associate with every integral point $(a,b)$ the monomial ...