Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraver degrees are not polynomially bounded by true circuit degrees
363
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $I_A$ be a toric ideal. We prove that the degrees of the elements of the Graver basis of $I_A$ are not polynomially bounded by the true degrees of the circuits of $I_A$.
rate research
Read More
A computable structure A is x-computably categorical for some Turing degree x, if for every computable structure B isomorphic to A there is an isomorphism f:B -> A with f computable in x. A degree x is a degree of categoricity if there is a computable A such that A is x-computably categorical, and for all y, if A is y-computably categorical then y computes x. We construct a Sigma_2 set whose degree is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity.
A grounded L-graph is the intersection graph of a collection of L shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omega^4$. This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $chi$-bounded. We also survey $chi$-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.
We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including that it is strictly increasing and order preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0 iff X is omega-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.
In this paper, a random graph process ${G(t)}_{tgeq 1}$ is studied and its degree sequence is analyzed. Let $(W_t)_{tgeq 1}$ be an i.i.d. sequence. The graph process is defined so that, at each integer time $t$, a new vertex, with $W_t$ edges attached to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on $G(t-1)$, the probability that a given edge is connected to vertex i is proportional to $d_i(t-1)+delta$, where $d_i(t-1)$ is the degree of vertex $i$ at time $t-1$, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent $tau=min{tau_{W}, tau_{P}}$, where $tau_{W}$ is the power-law exponent of the initial degrees $(W_t)_{tgeq 1}$ and $tau_{P}$ the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze, which is surveyed.
Cake-cutting protocols aim at dividing a ``cake (i.e., a divisible resource) and assigning the resulting portions to several players in a way that each of the players feels to have received a ``fair amount of the cake. An important notion of fairness is envy-freeness: No player wishes to switch the portion of the cake received with another players portion. Despite intense efforts in the past, it is still an open question whether there is a emph{finite bounded} envy-free cake-cutting protocol for an arbitrary number of players, and even for four players. We introduce the notion of degree of guaranteed envy-freeness (DGEF) as a measure of how good a cake-cutting protocol can approximate the ideal of envy-freeness while keeping the protocol finite bounded (trading being disregarded). We propose a new finite bounded proportional protocol for any number n geq 3 of players, and show that this protocol has a DGEF of 1 + lceil (n^2)/2 rceil. This is the currently best DGEF among known finite bounded cake-cutting protocols for an arbitrary number of players. We will make the case that improving the DGEF even further is a tough challenge, and determine, for comparison, the DGEF of selected known finite bounded cake-cutting protocols.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
