مقاله مرزهای کلی محکم برای اعداد ماتریس های 0-1

چکیده

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some $1$-entries with $0$-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted $\operatorname{ex}(n,A)$, is the maximum number of $1$-entries that an $n\times n$ zero-one matrix can have without containing $A$. The systematic study of this function for various patterns $A$ goes back to the work of Füredi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (that is, the case where $A$ is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if $A$ has at most $t$ $1$-entries in every row, then $\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$. This verifies a conjecture of Methuku and Tomon. Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number $2$, generalizing a celebrated result of Füredi, and Alon, Krivelevich and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree $t$ in one of the vertex classes.

چکیده به فارسی (ترجمه ماشینی)

گفته می شود که یک ماتریس $ $ m $ حاوی ماتریس صفر دیگری $ A $ باشد اگر بتوانیم برخی از ردیف ها و ستون های $ $ $ را حذف کنیم و حدود 1 دلار $ را با 0 $ $ جایگزین کنیم به گونه ای که ماتریس حاصل است$ $.تعداد افراطی $ A $ ، با مشخص شده \ \ operatorname {ex} (n ، a) $ ، حداکثر تعداد 1 $ $ است که یک ماتریس $ $ n $ n $ $ بدون داشتن یک $ $ می تواند داشته باشدبشرمطالعه سیستماتیک این عملکرد برای الگوهای مختلف $ A $ از سال 1992 به کار Füredi و Hajnal باز می گردد ، و این زمینه ارتباطات بسیاری با سایر زمینه های ریاضیات و علوم نظری کامپیوتر دارد.این مشکل به ویژه برای ماتریس های به اصطلاح acyclic مورد مطالعه قرار گرفته است ، اما در مورد مورد عمومی بسیار کمی شناخته شده است (یعنی موردی که $ $ لزوماً اسکالیک نیست).ما اولین نتیجه کلی بدون علامت محکم را با نشان دادن اینکه اگر $ $ حداکثر $ t $ 1 $ $ -entries در هر ردیف باشد ، اثبات می کنیم ، سپس $ \ operatorname {ex} (n ، a) \ leq n^{2-1/t+o (1)} $.این یک حدس از Methuku و Tomon را تأیید می کند.نتیجه ما همچنین اولین کلیدی محکم برای تعداد افراطی نمودارهای مرتب شده با راس با شماره کروماتیک فاصله 2 $ ، تعمیم نتیجه مشهور Füredi ، و Alon ، Krivelevich و Sudakov در مورد تعداد افراطی (بدون هماهنگ) نمودارهای دو طرفه با حداکثر ارائه می دهد.درجه $ t $ در یکی از کلاس های راس.