MSMoE12
Extremal Combinatorics, Probabilistic Combinatorics, and their applications  Part II of III
For Part I, see MSMoD12
For Part III, see MSTuD12
Date: August 10
Time: 16:0018:00
Room: 208B
(Note: Click title to show the abstract.)
Organizer:
Ma, Jie (Univ. of Sci. & Tech. of China)
Huang, Hao (Inst. for Mathematics & its Applications, Univ. of Minnesota)
Chen, Guantao (Georgia State Univ.)
Abstract: Combinatorics is a fundamental discipline of modern mathematics which studies discrete objects and their properties. This minisymposium we propose will focus on the subfield of extremal and probabilistic combinatorics, which has witnessed an exciting development over the past decades, and also has many striking practical applications in mathematical optimization, computer science, statistical physics and voting society. We aim to bring the top researchers to the minisymposium, where they will present the recent progress, discuss open challenges, exchange research ideas, and initiate new collaborations. We expect a minisymposium of this nature to have a lasting impact on the future of the subject.
MSMoE121
16:0016:30
Minimum degree and cycles of specific lengths
Liu, ChunHung (Princeton Univ.)
Ma, Jie (Univ. of Sci. & Tech. of China)
Abstract: We prove that every graph of minimum degree at least k+1 contains at least (k1)/2 cycles with consecutive even lengths. In addition, we prove that every graph of minimum degree at least k+4 contains k cycles of either consecutive lengths, or consecutive even lengths, or consecutive odd lengths. It confirms one of Thomassen's conjecture when k is even and provides the best known result for this conjecture when k is odd.
MSMoE122
16:3017:00
Permutation codes, secure codes and hash families related to extremal and probabilistic combinatorics
Ge, Gennian (Capital Normal Univ.)
Abstract: A code can be regarded as a subset of its underlying base set
satisfying some restrictions. In this talk, we will discuss the bounds and
constructions for several classes of combinatorial codes, which are closely
related to extremal and probabilistic combinatorics. These codes include:
permutation codes, separable codes, frameproof codes and some related hash
families for security protection. For the lower bounds, by regarding a code
as an independent set of a graph or a hypergraph, we are able to improve
the known lower bounds for permutation codes, 3perfect hash families, 2
frameproof codes and 2separable codes. In addition, we extend the construc
tions for separable codes and frameproof codes by applying the probabilistic
method. Particularly, we obtain asymptotically optimal 2separable codes
by the deletion method. For the upper bounds, by considering some typical
configurations of codes and applying combinatorial counting skills, we are
able to improve the known upper bounds for separable codes and frameproof
codes. Furthermore, using a result of Erdos and Gallai on hypergraph match
ing, we approve partially a wellknown conjecture on an old problem of the
disjunctive code theory.
MSMoE123
17:0017:30
Maximum matchings in 3partite 3uniform hypergraphs
Yu, Xingxing (Georgia Inst. of Tech.)
Abstract: For a hypergraph $H$, let $\delta_1(H)$ denote the minimum number of edges of $H$ containing a given vertex, and $\nu(H)$ denote the
maximum size of a matching in $H$. For integers $n\ge m\ge 1$, let
\[d_3(n,m)=\left\{\begin{array}{ll} n^2(n\lfloor m/3\rfloor)(n\lfloor (m+1)/3\rfloor) &\text{if}\
m\ne 1 \pmod 3, \\[5pt]
n^2(n(m1)/3)^2 +1 &\text{if } m=1 \pmod 3.\\[5pt]
\end{array}\right.\]
Lo and Markstr\"om proved that if $H$ is a 3partite 3uniform hypergraph with $n\ge 3^7m$ vertices in each partition class and $\delta_1(H)>d_3(n,m)$
then $\nu(H)>m$, and asked if the condition $n\ge 3^7m$ can be replaced by $n>m$. In this paper, we show that
there exists a positive integer $n_0$ such that if $H$ is a 3partite 3uniform hypergraph with $n\ge n_0$
vertices in each partition class and if $n>m$ and $\delta_1(H)>d_3(n,m)$, then $\nu(H)>m$.
MSMoE124
17:3018:00
The threshold probability for long cycles
Naves, Humberto (IMA  Inst. for Mathematics & its Applications)
Abstract: For a given graph $G$ of minimum degree at least $k$, let
$G_p$ denote the random spanning subgraph of $G$ obtained by
retaining each edge independently with probability $p=p(k)$.
In this talk, we prove that if $p \ge \frac{\log k + \log \log k +
\omega_k(1)}{k}$,
where $\omega_k(1)$ is any function tending to infinity with $k$,
then $G_p$ asymptotically almost surely contains a cycle
of length at least $k+1$. When $G$ is the complete
graph
Return
Footnote: Code: TypeDateTimeRoom No.
Type : IL=Invited Lecture, SL=Special Lectures, MS=Minisymposia, IM=Industrial Minisymposia, CP=Contributed Papers, PP=Posters
Date: Mo=Monday, Tu=Tuesday, We=Wednesday, Th=Thursday, Fr=Friday
Time : A=8:309:30, B=10:0011:00, C=11:1012:10, BC=10:0012:10, D=13:3015:30, E=16:0018:00, F=19:0020:00, G=12:1013:30, H=15:3016:00
Room No.: TBA
