0
votes
0answers
24 views

Introductory material on discrepancy theory

I'm interested in learning about discrepancy theory. By this I mean material such as http://math.mit.edu/classes/18.095/lect6/notes.pdf . However, I've been unable to get much from "Chazelle, ...
3
votes
2answers
104 views
+50

A conjecture relating Multiple Zeta Values and the Polya Enumeration Theorem

Let me state my motivation. I believe that the Polya Enumeration Theorem and Multiple Zeta Values (the classic being the Basel problem and the values of the Riemann zeta function at the even ...
1
vote
0answers
14 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 ...
6
votes
6answers
351 views

Book on combinatorial identities

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
2
votes
1answer
105 views

Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
1
vote
0answers
16 views

Non-Intersecting up-right lattice paths and standard Young Tableaux

Consider the Lattice $\mathbb{Z}^2$ and an initial set of points with coordinates $(0,u_1)$, $(0,u_2)$, $\cdots$ $(0,u_n)$, final set of points $(m,v_1),(m,v_2),\cdots,(m,v_n)$, where $v_i,u_i$ are ...
0
votes
2answers
28 views

Alternative reference for number of restricted partitions

I am looking for the number of partitions of some number $n$ into $k$ parts. Following the Wikipedia article on partitions, I ended up with Andrew's book [1]. Judging by Google's preview Chapter 3 ...
0
votes
1answer
18 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
6
votes
1answer
63 views

Gowers' proof of Szemerdi's theorem

Are there any good books or other resources (expository notes) which explains Gowers' proof of Szemerdi's theorem in detail?
0
votes
0answers
26 views

A game of repeatedly taking the union of sets

Suppose that I have the set family $\mathcal{A}_1 = \{A_1, \dots, A_k\}$. We play the following game, which consists of a sequence of iterations. In the first iteration, we choose an arbitrary ...
0
votes
0answers
65 views

Describing the sequence A224239.

I've been trying to describe mathematically the $n$th term $a_n$ of the sequence A224239. We get $a_n$ by counting the distinct ways to fill an $n\times n$ grid with squares of smaller integer size, ...
1
vote
0answers
48 views

Monoid on ordered partitions of a natural number

Fix a natural number $n$, and let $O_n$ be the set of ordered partitions of $n$. For example $O_3=\{1+1+1,1+2,2+1,3\}$ which can also be written as $\{1|2|3,1|23,12|3,123\}$. We can define two ...
2
votes
0answers
38 views

References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph ...
0
votes
0answers
17 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
0
votes
1answer
114 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
5
votes
2answers
102 views

What can we say about the kernel of $\phi: F_n \rightarrow S_k$

Let $F_n$ denote the free group on $n$ generators and let $S_k$ denote the symmetric group on the integers $\{1,\dots, k\}$, and the action of homomorphism $\phi$ (as given in the title) on the ...
1
vote
1answer
51 views

Articles on matchstick puzzles

There are many ingenious puzzles involving matchsticks that are arranged as squares, rectangles or triangles, and can be moved under some restrictions (for a lot of examples see ...
2
votes
1answer
72 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...
0
votes
0answers
26 views

Variants of sudoku that require very little give aways

Consider the following generalization of sudoku (it might already exist under a different name, any reference is welcome): Let $n$ be a natural number. By a generalized sudoku I understand a ...
8
votes
2answers
164 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
4
votes
2answers
102 views

Maximum edges in a square free graph

Square free graph : Graphs with minimum cycle length greater than 4. Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order ...
0
votes
0answers
60 views

Ham Sandwich theorem used in combinatorics problem involving beads on a necklace

Ok, so according to a friend of mine you can use the ham sandwich to prove the following theorem: Suppose there is a necklace with $m$ types of beads and $2n_1,2n_2...2n_m$ beads of each colors. So ...
1
vote
0answers
13 views

Online Encyclopedia of Error-Correcting Codes

Is there some kind person on the internet who is making an exhaustive collection of error-correcting codes? I'm looking for something analogous to the OEIS. I want to ask questions like "what is this ...
5
votes
1answer
115 views

Are there mathematical (combinatorial) objects to represent such set systems?

Background: This is a problem arising from my study on computer science. In its appearance, it involves set systems. A set system $\mathcal{S} = \{S_1, S_2, \ldots, S_m \}$ is a collection of ...
5
votes
3answers
185 views

Symmetries of combinatorial structures.

Studying the automorphism groups of graphs/finite geometries/designs has been quite useful and important for both group theory and combinatorics. I know of the following books which cover the ideas ...
0
votes
0answers
42 views

A Survey on Rota's Conjecture

I am looking for a survey on Rota's Conjecture (1970). I am more interested in geometric aspects of the conjecture and any geometric content related to the conjecture. Any reference would be helpful. ...
1
vote
0answers
49 views

How many Hamiltonian loop are there in a big rectangle?

Suppose I have some big rectangle made of $n \times m$ squares, and I want to place tiles on it in a manner that makes a picture of a hamiltonian loop. I can transform this problem into a problem ...
2
votes
0answers
60 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is ...
1
vote
1answer
36 views

Counting Self-dual posets

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow ...
1
vote
2answers
61 views

Does there exist a branch of mathematics that specifically study the number of lattices enclosed by a region?

I have seen that sometimes, in particular in number theory and combinatorial commutative algebra, our questions are somehow related to finding the number of points with integer components in a ...
2
votes
0answers
40 views

Does the notion of graph 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 ...
1
vote
2answers
84 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
3answers
85 views

Books to understand Szemeredi's regularity lemma?

I want to understand the Szemeredi theorem and read on the thoery relating to it. Which books should I pick up to do this? Regards
0
votes
1answer
43 views

Let $G$ be bipartite, what is $\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$

Let $G$ be a bipartite graph. Let $X,Y$ be the two partite sets of $G$. Suppose further that $N(X)=Y$. Consider the problem of finding: $$\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$$ What are some ...
2
votes
2answers
206 views

Books in Combinatorial optimization

I wrote Combinatorial optimization in the title , but I am not sure if this is what I am looking for. Recently, I was getting more interested in Koing's theorem, Hall marriage theorem . I am ...
2
votes
2answers
103 views

Combinatorics, permutations. Books

I want to study about combinatorics, permutations. I don't need for complicated things, I only want to understand this notions very well and only the to try to study more complicated notions. Can ...
1
vote
0answers
38 views

Average number of draws to repeat a random number?

In a random sequence of equiprobable integer numbers between [1,n], how can I find the average number of draws needed for a single integer to repeat? Please recomment a good book.
1
vote
1answer
120 views

pigeonhole principle exercises

I have an exam in combinatorics on friday and the Pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions in this material? than you ...
1
vote
1answer
65 views

Number non self avoiding closed walks surrounding some point

While studying some Peierls-like arguments in statistical physics I thought about the following problem: We have some 2d-integer lattice like this, for simplicity infinite in all directions. Now fix ...
0
votes
1answer
94 views

What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it? [closed]

What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it? When I was reading about Ramsey theory in some reviews on some books, many people mentioned this ...
4
votes
0answers
62 views

What's the name for this unimodal sequence?

Let $a_0, a_1, \ldots, a_n$ be an increasing sequence of positive numbers, and consider the sequence $s_1,\ldots,s_n$, where $$ s_k \;=\; \frac{a_0+\cdots + a_k}{k}. $$ So $$ s_1 \;=\; a_0+a_1,\quad ...
1
vote
1answer
49 views

How to find instances when $d(a,b) = p^2$ for $p$ a prime.

Suppose I have a dimension formula (for a Lie algebra representation) given by $\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for ...
-1
votes
3answers
225 views

Good books on combinatorics

I have a math Ph.D. but my knowledge of combinatorics sucks and I simply don't know how to compute anything more complicated, i.e. what happens when we put restrictions on the allowed configurations ...
2
votes
2answers
255 views

Looking for combinatorial identity: $\sum\limits_{j=0}^k{n \choose k-j}{m \choose j}$ [duplicate]

Is there a nicer closed form expression for the following expression? $$\sum_{j=0}^k{n \choose k-j}{m \choose j}$$
3
votes
2answers
124 views

Learning Combinatorial Species.

I have been reading the book conceptual mathematics(first edition) and I'm also about halfway through Diestel's Graph theory(4th edition) I was wondering if I was able to start learning combinatorial ...
13
votes
3answers
663 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
4
votes
2answers
85 views

The Dinitz problem

I would like to ask if someone knows about good books or online articles about The Dinitz problem or maybe someone can explain the problem a little. Consider $n^2$ cells arranged in an $( n \times ...
7
votes
0answers
177 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
19
votes
1answer
483 views

A Combinatorial Proof of Dixon's Identity

Dixon's Identity states: $$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c} {a,b,c}$$ A bit of history: The case $a=b=c$ was proved by Dixon in 1891 using ...
2
votes
0answers
115 views

Combinatorics: Selecting non-adjacent subsets or objects arranged in a circle

Lets say you have a circular table that seats $n$ people and $b\lt n -1$ identitcal boys. If you were to divide the boys into $k$ teams of size $\geq 1$, how many ways are there to seat the boys so ...