Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe matching number of tree and bipartite degree sequences
102
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale-Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale-Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals.
rate research
Read More
We explore the notion of degree of asymmetry for integer sequences and related combinatorial objects. The degree of asymmetry is a new combinatorial statistic that measures how far an object is from being symmetric. We define this notion for compositions, words, matchings, binary trees and permutations, we find generating functions enumerating these objects with respect to their degree of asymmetry, and we describe the limiting distribution of this statistic in each case.
In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree $Delta$ and with $n$ vertices on each side has a balanced independent set containing $(1-epsilon) frac{log Delta}{Delta} n$ vertices from each side for small $epsilon > 0$. Secondly, we prove that the vertex set of every sufficiently large balanced bipartite graph with maximum degree at most $Delta$ can be partitioned into $(1+epsilon)frac{Delta}{log Delta}$ balanced independent sets. Both of these results are algorithmic and best possible up to a factor of 2, which might be hard to improve as evidenced by the phenomenon known as `algorithmic barrier in the literature. The first result improves a recent theorem of Axenovich, Sereni, Snyder, and Weber in a slightly more general setting. The second result improves a theorem of Feige and Kogan about coloring balanced bipartite graphs.
A recent result of Condon, Kim, K{u}hn and Osthus implies that for any $rgeq (frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $alpha n$-regular graph $G$ with any $alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $alpha>0$ and an $n$-vertex almost $alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $Gcup mathbf{G}(n,O(frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Turan theory and the randomly perturbed graph model.
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. For the complete bipartite graph $K_{m,n}$, the lower bound $b(K_{m,n})gelceil{frac{mn+4}{2m+2n}}rceil$ from Eulers Formula is well known. We prove that equality holds.
We find an asymptotic enumeration formula for the number of simple $r$-uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$-uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$-uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
