Maria Axenovich
Fork-forests in bi-colored complete bipartite graphs.
Fri, 01/13/2012 - 15:01 — SomNambulAuthors: Maria Axenovich, Marcus Krug, Georg Osang, Ignaz Rutter
Subjects: Discrete Mathematics
AbstractMotivated by the problem in [6], which studies the relative efficiency of
propositional proof systems, 2-edge colorings of complete bipartite graphs are
investigated. It is shown that if the edges of $G=K_{n,n}$ are colored with
black and white such that the number of black edges differs from the number of
white edges by at most 1, then there are at least $n(1-1/\sqrt{2})$
vertex-disjoint forks with centers in the same partite set of $G$. Here, a fork
is a graph formed by two adjacent edges of different colors. The bound is
sharp.A version of Szemer\'edi's regularity lemma for multicolored graphs and directed graphs that is suitable for induced graphs.
Thu, 06/16/2011 - 15:01 — SomNambulAuthors: Ryan Martin, Maria Axenovich
Subjects: Combinatorics
AbstractIn this manuscript we develop a version of Szemer\'edi's regularity lemma
that is suitable for analyzing multicolorings of complete graphs and directed
graphs. In this, we follow the proof of Alon, Fischer, Krivelevich and M.
Szegedy [\textit{Combinatorica} \textbf{20}(4) (2000) 451--476] who prove a
similar result for graphs.The purpose is to extend classical results on dense hereditary properties,
such as the speed of the property or edit distance, to the above-mentioned
combinatorial objects.Multicolor and directed edit distance.
Thu, 06/16/2011 - 15:01 — SomNambulAuthors: Ryan Martin, Maria Axenovich
Subjects: Combinatorics
AbstractThe editing of a combinatorial object is the alteration of some of its
elements such that the resulting object satisfies a certain fixed property. The
edit problem for graphs, when the edges are added or deleted, was first studied
independently by the authors and K\'ezdy [J. Graph Theory (2008), 58(2),
123--138] and by Alon and Stav [Random Structures Algorithms (2008), 33(1),
87--104].- Read more
- 9 comments
- login or register to post comments
$Q_2$-free families in the Boolean lattice.
Thu, 12/31/2009 - 16:01 — SomNambulAuthors: Ryan Martin, Maria Axenovich, Jacob Manske
Subjects: Combinatorics
AbstractFor a family $\mathcal{F}$ of subsets of [n]=\{1, 2, ..., n} ordered by
inclusion, and a partially ordered set P, we say that $\mathcal{F}$ is P-free
if it does not contain a subposet isomorphic to P. Let $ex(n, P)$ be the
largest size of a P-free family of subsets of [n]. Let $Q_2$ be the poset with
distinct elements a, b, c, d, a<b, c<d; i.e., the 2-dimensional Boolean
lattice. We show that $2N -o(N) \leq ex(n, Q_2)\leq 2.283261N +o(N), $ where $N
= \binom{n}{\lfloor n/2 \rfloor}$.
User login
