0
votes
0answers
20 views

Sperner family intersection with chains.

Consider a maximal sperner family $F$ of subsets of $X = \{ 1,2,3 \ldots n \}$. I need to prove that this family intersects with each chain of subsets exactly once. Each chain is defined as : ...
0
votes
0answers
28 views

K- Regular families. Proof of existence.

A family F of subsets is regular if every point lies in a constant number r of the elements of F. Theorem : Let $b,k,n,r$ be positive integer satisfying $bk = nr, k<n, b\leq $ $n\choose{k} $. Then ...
0
votes
1answer
33 views

Proof of De Bruijn-Erdos theorem

I am reading Cameron's Combinatorics and came across following part of the proof of De Bruijn-Erdos theorem which I am unable to follow. $F$ is the family of set such that any two sets in $F$ ...
4
votes
3answers
152 views

Biggest subset of $\{1, 2 … 1000\}$ such that difference between any pair of elements $\neq 4, 7$

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V ...
1
vote
1answer
69 views

total number of combinations?

Patient Age ---> Avg Visits / Year <1 year ---> 7.5 1-4 years ---> 3.0 5-14 years ---> 1.8 15-24 years ---> 1.7 25-44 years ...
1
vote
0answers
29 views

resilience of graphs question

The following is a definition of the resilience of a graph w.r.t to a property $\mathcal{P}$ (Local resilience) A property $\mathcal{P}$ is said to be monotone if the property is preserved under ...
8
votes
2answers
155 views

Tricky (extremal?) combinatorics problem

Apologies for being unsure the best way to express this problem. I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit ...
1
vote
1answer
42 views

maximum size of a $k$-intersecting antichain of $[n]$

What is the maximum size of an antichain of $[n]:=\{1,2,3,\dots,n\}$ (say $\mathcal{A}$) such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? By antichain, I mean ...
2
votes
2answers
141 views

maximum size of a $k$-intersecting family of $[n]$

What is the maximum size of a family of subsets of $[n]:=\{1,2,3,\dots,n\}$ say $\mathcal{A}$ such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? This not ...
1
vote
0answers
18 views

Szemeredi Trotter and additive combinatorics on A+AA

I am trying to get a lower bound on $|A+AA|$ where $A$ is a set, and $A+AA=\{a+bc: a,b,c \in A\}$ using Szemeredi Trotter. I would think we need to form lines of the form $y=ax+b$ where $a,b \in A$, ...
4
votes
1answer
158 views

Application of Erdős–Ko–Rado

Here is an interesting question. I believe you have to use the fact the Erdős–Ko–Rado Theorem tells you $A$ and $B$ are not intersecting, but I am unable to show it: Let $A,B \subset[n]^{(r)}$, ...
2
votes
1answer
78 views

Generalization of Erdős-Ko-Rado where intersections have cardinality in given set

Problem: Let $T\subseteq \{0,\ldots, k-1\}$ and let $\mathcal F\subseteq [n]^{(k)}$ (subsets of size $k$) such that $|A\cap B|\in T$ for $A,B\in \mathcal F$, $A\ne B$. Show that if $n\ge ...
3
votes
1answer
84 views

Number of edges in graphs having two disjoint cycles of equal length

The question is motivated by this and this two problems. The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the ...
2
votes
3answers
160 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
2
votes
0answers
30 views

Covering the square with “crosses”.

The problem concerns covering the unit square with translates of a specific figure, which I will refer to as a "cross", using as few translates as possible. The difficulty seems to result from the ...
2
votes
1answer
37 views

Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are ...
2
votes
0answers
28 views

Threshold function of the property Sperner set

Someone can to help me in the following problem about the threshold function of the property Sperner set? I don't know where to start. Let $\mathcal{F} \subseteq \mathcal{P}([n])$ be a random ...
2
votes
1answer
115 views

Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $ |f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...
1
vote
0answers
39 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
2
votes
1answer
36 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
2
votes
1answer
166 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
3
votes
1answer
54 views

Minimum boolean lattice containing all poset of fixed size

I need help with the following: What is the minimum $n$ such that the boolean lattice $2^{[n]}$ contains all posets of size $m$? I noticed that it should contain a chain of length $m$, and the ...
2
votes
1answer
135 views

LYM Inequality question

Suppose that $F ⊂ P(n)$ is a set system containing no chain with $k + 1$ sets. Prove that $\sum\limits_{r=1}^n \frac{|F_{r}|}{n \choose r} ≤ k$, where $F_{i} = F \cap [n]^{(i)}$ for each i. ...
1
vote
2answers
82 views

Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
1
vote
1answer
38 views

Balanced independent sets & independent domination number

Let $G=(V,E)$ be a bipartite graph, with partition $V=A \cup B$. Recall that an independent set $I$ of $G$ is a set of vertices sharing no edges. The independent domination number $i(G)$ is defined ...
0
votes
0answers
67 views

Intersecting Set Systems

This a follow up question to an earlier question: "Intersecting set systems and Erdos-Ko-Rado Theorem " that was answered by Sean Eberhad. It asks, what is the largest intersecting family of r-sets ...
5
votes
1answer
128 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
9
votes
3answers
524 views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
1
vote
1answer
58 views

Has this variation of blocking set been studied before?

Given a collection of sets $F$, a set which intersects all sets in the $F$ in at least one element is called a blocking set (or hitting set). The blocking number $τ(F)$ of a family $F$ is the minimum ...
0
votes
0answers
48 views

An extremal combinatorial problem over Finite rings

Let $q$ be an odd number and $g_i = (g_{i1} g_{i2} \dots g_{ir}) \in \Bbb Z_q^r$ a list of vectors with $i\in\{1,\ldots,L\}$. Let each $g_i$ have $0 < k < r$ zero entries. What is the maximum ...
5
votes
1answer
135 views

Show there’s at most $n\choose \left \lfloor\frac{n}{2} \right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that ...
2
votes
1answer
783 views

Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). ...
2
votes
0answers
53 views

Difference Sets

suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
2
votes
1answer
257 views

Maximum number of pairwise intersections

Let $[n]=\{1,2,\ldots,n\}$ and let $S$ consist of subsets of $[n]$ of cardinality $2$. I would like to find the maximum number of pairwise intersections that $k$ distinct elements from $S$ can have. ...
1
vote
1answer
58 views

beads in a string with restrictions

Using the principle of inclusion and exclusion; let $p,q\in \mathbb{N}$, being $p$ odd, there are $pq$ beads of $q$ different colors, with $p$ beads in each color. If the beads of the same colour are ...
1
vote
1answer
39 views

Multiples of one number in base-$10$ [duplicate]

How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones? For example, let $n=3$ then, exists al least one number, the ...
3
votes
3answers
308 views

Demonstration using the Pigonhole principle

I was thinking about the following problem: Let $n\in\mathbb N$ be odd. If I have a symmetric matrix in $M_n(\mathbb{N})$, i.e. a square symmetric matrix of size $n$, for which each column and ...
0
votes
1answer
377 views

total number of different mixes

Patient Age Avg Visits / Year <1 year 7.5 1-4 years 3.0 5-14 years 1.8 15-24 years 1.7 25-44 years 2.6 45-64 years ...
0
votes
3answers
68 views

About ascending numbers

I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$ How can I find ...
0
votes
1answer
176 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
0answers
109 views

Problem involving set systems - combinatorics.

The question is as follows: $A \subset \mathbb{P}(X)$ is called a cross-cut if for every $B \subset X$ there exists $A' \in A$ with $B \subset A'$ or $A' \subset B$. Prove that every cross-cut ...
3
votes
1answer
262 views

Intersecting set systems and Erdos-Ko-Rado Theorem

Suppose you have an $n$-element set, where $n$ is finite, and you want to make an intersecting family of $r$-subsets of this set. Each subset has to intersecting each other subset. We may assume $r$ ...
6
votes
2answers
104 views

Two subsets and their union have same color

Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$. Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
0
votes
1answer
120 views

Walks on the Integer Grid

Consider the set of all walks with $2k$-many steps on the integer grid starting from the point $n \in \mathbb{Z}$ and turning back to this specific point. Let each walk is of lenght $\pm 2$ and do not ...
-2
votes
1answer
93 views

question challenge expert math

I have question. this question is need more explain can anyone do if we have $$k_n=a_n+a_{n-1}+a_{n-2}+ \dots+a_1+a_0$$ where $a_n=1$ only $n$ is a multiple of $5$, $0$ otherwise. So $$k_n= ...
0
votes
1answer
68 views

Question in discrete mathematics *

I have question. Can anyone able to explain to me this problem why if we have 5x the generating function $1+x^5+x^{10}+x^{15} + \ldots$ we have 5 is just constant and multiply with $x$ I know that $x$ ...
1
vote
1answer
76 views

question in discrete mathematics

I have questions. Can anyone help me to get the idea or figure out this problem. Find a recurrence relation. If an denote the number of words from the alphabet W={A,B,C} of length n with no two ...
4
votes
1answer
150 views

No induced ordered graph yields large clique/stable set in ordered graph

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
1
vote
1answer
300 views

Ramsey-type result for tournaments

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help. Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
4
votes
0answers
85 views

Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1] For ...